-
以邻接矩阵作为存储结构实现图的创建与基本操作
2017-12-30 10:48:04以邻接矩阵作为存储结构实现图的创建与基本操作: typedef int Status; typedef int VRType; typedef char InfoType; typedef char VertexType; /*①图的邻接矩阵存储结构定义*/ typedef struct ArcCell {...以邻接矩阵作为存储结构实现图的创建与基本操作:
typedef int Status;
typedef int VRType;
typedef char InfoType;
typedef char VertexType;
/*①图的邻接矩阵存储结构定义*/
typedef struct ArcCell
{
//VRType是顶点的关系类型,对无权图用1或0表示是否相邻,对带权图(网)用权值
VRType adj;
InfoType *info; //该弧段相关信息的指针
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM]; //顶点向量
AdjMatrix arcs; //邻接矩阵
int vexnum,arcnum; //图的顶点数和边(弧)数
GraphKind kind; //图的种类标志
}MGraph;
#include<stdio.h> #include<stdlib.h> #include<string.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define INFINITY 0 //最大值无穷 #define MAX_VERTEX_NUM 20 //最大顶点数 typedef int Status; typedef int VRType; typedef char InfoType; typedef char VertexType[MAX_VERTEX_NUM]; typedef enum {DG,DN,UDG,UDN} GraphKind; //{0有向图、1有向网、2无向图、3无向网} /*①图的邻接矩阵存储结构定义*/ typedef struct ArcCell { VRType adj; //VRType是顶点的关系类型,对无权图用1或0表示是否相邻,对带权图(网)用权值 InfoType *info; //该弧段相关信息的指针 }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; //顶点向量 AdjMatrix arcs; //邻接矩阵 int vexnum,arcnum; //图的顶点数和边(弧)数 GraphKind kind; //图的种类标志 }MGraph; //构造有向图 Status CreateDG(MGraph &G); //构造有向网 Status CreateDN(MGraph &G); //构造无向图 Status CreateUDG(MGraph &G); //构造无向网 Status CreateUDN(MGraph &G); //1-创建图 Status CreateGraph(MGraph &G); //2-销毁图 Status DestroyGraph(MGraph &G); //3-获取顶点位置 Status LocateVex(MGraph G, VertexType u); //构造有向图 Status CreateDG(MGraph &G) { int i,j,k,IncInfo,w; VertexType v1,v2; printf("请输入有向图G的顶点数,边数,边是否含有其他信息(是:1,否:0):\n"); scanf("%d%d%d",&G.vexnum ,&G.arcnum,&IncInfo); printf("请输入顶点的值:\n"); for(i=0;i<G.vexnum;++i)//构造顶点向量 scanf("%s",G.vexs[i]); for(i=0;i<G.vexnum;++i)//初始化邻接矩阵 for(j=0;j<G.vexnum;++j) { G.arcs[i][j].adj=INFINITY; G.arcs[i][j].info=NULL; } for(k=0;k<G.arcnum;++k) { scanf("%s%s%d",&v1,&v2,&w); i=LocateVex(G,v1); //弧尾 j=LocateVex(G,v2); //弧头 G.arcs[i][j].adj=w; if(IncInfo) { printf("请输入该边的相关信息:"); gets(G.arcs[i][j].info); } } G.kind=DG; return OK; } //构造有向网 Status CreateDN(MGraph &G) { int i,j,k,w,IncInfo; VertexType v1,v2; printf("请输入有向网G的顶点数,边数,边是否含有其他信息(是:1,否:0):\n"); scanf("%d%d%d",&G.vexnum ,&G.arcnum,&IncInfo); for(i=0;i<G.vexnum;++i)//构造顶点向量 scanf("%s",G.vexs[i]); for(i=0;i<G.vexnum;++i)//初始化邻接矩阵 for(j=0;j<G.vexnum;++j) { G.arcs[i][j].adj=INFINITY; G.arcs[i][j].info=NULL; } printf("请输入%d条弧的弧尾 弧头 权值(以空格作为间隔):\n",G.arcnum); for(k=0;k<G.arcnum;++k) { scanf("%s%s%d%",&v1,&v2,&w); i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcs[i][j].adj=w;//有向网 if(IncInfo) { printf("请输入该边的相关信息:"); gets(G.arcs[i][j].info); } } G.kind=DN; return OK; } //构造无向图 Status CreateUDG(MGraph &G) { int i,j,k,IncInfo,w; VertexType v1,v2; printf("请输入无向图G的顶点数,边数,边是否含有其他信息(是:1,否:0):\n"); scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo); printf("请输入顶点的值:\n"); for(i=0;i<G.vexnum;i++)//构造顶点向量 scanf("%s",G.vexs[i]); for(i=0;i<G.vexnum;++i)//初始化邻接矩阵 for(j=0;j<G.vexnum;++j) { G.arcs[i][j].adj=INFINITY; G.arcs[i][j].info=NULL; } for(k=0;k<G.arcnum;++k) { scanf("%s%s%d",&v1,&v2,&w); i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcs[i][j].adj=w;//无向图 if(IncInfo) { printf("请输入该边的相关信息:"); gets(G.arcs[i][j].info); } G.arcs[j][i]=G.arcs[i][j]; } G.kind=UDG; return OK; } //构造无向网 Status CreateUDN(MGraph &G) { int i,j,k,IncInfo,w; VertexType v1,v2; printf("请输入无向网G的顶点数,边数,边是否含有其他信息(是:1,否:0):\n"); scanf("%d%d%d",&G.vexnum ,&G.arcnum,&IncInfo); printf("请输入顶点的值:\n"); for(i=0;i<G.vexnum;++i) scanf("%s",&G.vexs); for(i=0;i<G.vexnum;++i) for(j=0;j<G.vexnum;++j) { G.arcs[i][j].adj=INFINITY; G.arcs[i][j].info=NULL; } for(k=0;k<G.arcnum;++k) { scanf("%s%s%d",&v1,&v2,&w); i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcs[i][j].adj =w; if(IncInfo) { printf("请输入该边的相关信息:"); gets(G.arcs[i][j].info); } G.arcs[j][i]=G.arcs[i][j]; } G.kind=UDN; return OK; }//CreateUDN //1-创建图 Status CreateGraph(MGraph &G) { printf("***********图的创建与实现**************\n"); printf("1.有向图\n2.有向网\n3.无向图\n4.无向网\n请选择需要创建的图的类型:"); scanf("%d",&G.kind); switch (G.kind-1){ case DG:return CreateDG(G); case DN:return CreateDN(G); case UDG:return CreateUDG(G); case UDN:return CreateUDN(G); default:return ERROR; } }//CreateGraph //2-销毁图 Status DestroyGraph(MGraph &G) { int i,j; if(G.kind<2)//有向 { for(i=0;i<G.vexnum;i++)//释放相关信息(如果有) for(j=0;j<G.vexnum;j++) if(G.arcs[i][j].adj==1&&G.kind==0||G.arcs[i][j].adj!=INFINITY&&G.kind==1)//有向图的弧||有向网的弧 if(G.arcs[i][j].info)//有相关信息 { free(G.arcs[i][j].info); G.arcs[i][j].info=NULL; } } else//无向 { for(i=0;i<G.vexnum;i++)//释放相关信息(如果有) for(j=i+1;j<G.vexnum;j++) if(G.arcs[i][j].adj==1&&G.kind||G.arcs[i][j].adj!=INFINITY&&G.kind==3)//无向图的边||无向网的边 if(G.arcs[i][j].info)//有相关信息 { free(G.arcs[i][j].info); G.arcs[i][j].info=G.arcs[j][i].info=NULL; } } G.vexnum=0; G.arcnum=0; printf("图销毁成功!"); printf("\n\n"); return OK; } //3-获取顶点位置 Status LocateVex(MGraph G, VertexType u) { int i; for(i=0;i<G.vexnum;++i) if(strcmp(u,G.vexs[i])==0) return i; return FALSE; } void main() { MGraph G; CreateGraph(G); }
未完待更新。。。。。。 -
假设以邻接矩阵作为图的存储结构_图的存储
2020-12-03 22:19:16无向图的邻接矩阵有向图的邻接矩阵邻接表存储图看上图邻接矩阵的结构,可以得知邻接矩阵中的边数组中存在大量为零的空占位,浪费了大量空间,所以就自然而然想到利用链表来进行边的存储,这就是邻接表(Ad...因为图的结构特点,使得其在存储、遍历也相对复杂一些。
邻接矩阵存储图
最简单的方式就是将图的顶点用一维数组存储进来,然后将边信息存储在二维矩阵中,这两个数组合称为图的邻接矩阵(Adjacency Matrix)。
无向图的邻接矩阵 有向图的邻接矩阵 邻接表存储图
看上图邻接矩阵的结构,可以得知邻接矩阵中的边数组中存在大量为零的空占位,浪费了大量空间,所以就自然而然想到利用链表来进行边的存储,这就是邻接表(Adjacency List)。
无向图的邻接表 有向图的邻接表 有向图邻接表的边表为以弧尾为链表表头进行存储的,这样对于顶点的出度统计较为方便,而有向图逆邻接表则正好与邻接表相反,边表是以弧尾作为链表表头的。
有向图逆邻接表边表 网的邻接表 邻接多重表存储无向图
假如对无向图的邻接表进行删除某边操作时需要对相关结点进行遍历找到相应边然后进行删除,比较麻烦,故邻接多重表对其进行改良。
边表结构:
其中,ivex和jvex为某边依附的两顶点在顶点表中的下标,ilink指向依附顶点ivex的下一条边,同理jlink指向依附顶点jvex的下一条边。
邻接多重表结构 十字链表存储有向图
用邻接表存储有向图存在一个问题,对于某一顶点的弧统计还是很麻烦的,邻接表对于顶点作为弧头的弧统计很麻烦,逆邻接表对于顶点作为弧尾的弧统计很麻烦。所以为了对顶点更好的查询,便参考线索二叉树的设计思路,得到了十字链表(Orthogonal List)。
顶点表的结构为:
边表结构为:
其中,
tailvex
为弧尾在顶点表中的下标,headvex
为弧头在顶点表中的下标,headlink
指的是入边表指针域,指的是弧头相同的下一条边,taillink
指的是出边表指针域,指的是弧尾相同的下一边。十字链表存储示意 图中实线为邻接表,虚线为逆邻接表。
边集数组存储图
注意和邻接矩阵进行区别。
-
假设以邻接矩阵作为图的存储结构_【数据结构——图和图的存储结构】
2020-11-21 09:01:58目录一、图的定义和基本术语(Graph)(一)图的定义(二)图的基本术语一、图的存储结构(一)邻接矩阵(Adjacency Matrix)1、无向图的邻接矩阵2、有向图的邻接矩阵3、网(即有权图)的邻接矩阵4、邻接矩阵的存储表示5、采用...目录
一、图的定义和基本术语(Graph)
(一)图的定义
(二)图的基本术语
一、图的存储结构
(一)邻接矩阵(Adjacency Matrix)
1、无向图的邻接矩阵
2、有向图的邻接矩阵
3、网(即有权图)的邻接矩阵
4、邻接矩阵的存储表示
5、采用邻接矩阵表示法创建无向网
(二)邻接表(链式)表示法(Adjacency List)
1、无向图的邻接表表示
2、有向图的邻接表表示
3、图的邻接表的存储定义
4、采用邻接表表示法创建无向图
5、邻接矩阵与邻接表的比较
(三)十字链表(Orthogonal List)
1、弧结点的结构
2、顶点结点的结构
3、图的结构定义
4、实例
5、有向图G的十字链表
(四)邻接多重表(Adjacent MultiList)
1、边结点的结构
2、顶点结点的结构
3、图的结构定义
4、实例
4、练习:画出无向图G的邻接多重表
一、图的定义和基本术语(Graph)
(一)图的定义
图(Graph)是由一个顶点集V和一个边集E构成的数据结构。
G=(V,E)
V:顶点(数据元素)的又穷非空集合
E:边的又穷集合无向图:每条边都是没有方向的
有向图:每条边都是有方向的,边也称作弧(二)图的基本术语
设n表示图中顶点的数目,e表示边的数目完全图:任意两个点都有一条边相连
稀疏图:如果边或者弧的个数满足e
对无向图来说:邻接点:若顶点v和顶点w之间存在一条边a,则称顶点v和w互为邻接点。边a与顶点v和w相关联。
度:与顶点v关联的边的数目,记为TD(v)对有向图来说:1、为有向边(弧),x为有向边的起点(弧尾),y为有向边的终点(弧头)
2、顶点v的入度是以v为终点的有向边的条数,记作ID(v)
3、顶点v的出度是以v为始点的有向边的条数,记作OD(v)路径:连续的边构成的顶点序列路径长度:路径上边或者弧的数目简单路径:除路径起点和终点可以相同外,其余顶点均不相同的路径简单回路(简单环):除路径起点和终点相同外,其余顶点均不相同的路径。
一、图的存储结构
图的存储表示特点:
1、图没有顺序存储结构,但可以借助二维数组来表示图的元素之间的关系
2、以顶点为核心,建立邻接点和弧的关系;(一)邻接矩阵(Adjacency Matrix)
1、考虑到图是由两个顶点和边或弧两部分组成,合在一起比较困难,可以分为两个结构来存储
2、顶点因为不区分大小,主次,所以可以用一个一维数组来存储,记录各个顶点的信息
3、边或弧是顶点和顶点的关系,用邻接矩阵来存储,表示各个顶点之间的邻接关系。1、无向图的邻接矩阵
2、有向图的邻接矩阵
3、网(即有权图)的邻接矩阵
4、邻接矩阵的存储表示
/*图的邻接矩阵存储表示法*///用两个数组分别存储顶点表和邻接矩阵#define MaxInt 32767 //表示极大值,即无穷#define MVNum 100 //最大顶点数typedef char VerTexType; //假设顶点的数据类型为字符型typedef int ArcType; //假设边的权值类型为整型typedef struct{ VerTexType vexs[MVNum]; //顶点表 ArcType arcs[MVNum][MVNum]; //邻接矩阵 int vexnum, arcnum; //图的当前顶点数和边数}AMGraph;
5、采用邻接矩阵表示法创建无向网
【算法步骤】
1、输入总顶点数和边数
2、依次输入点的信息存入到顶点表中
3、初始化邻接矩阵,使每个权值初始化为极大值
4、构造邻接矩阵注意:
1、无向图需要为arcs[i][j]和arcs[j][i]赋值
2、有向图仅需为arcs[i][j]赋值算法描述:
/*采用邻接矩阵表示法创建无向网*/Status CreateUDN(AMGraph& G){ cin >> G.vexnum >> G.arcnum;//输入总顶点数和总边数 for (int i = 0;i < G.vexnum;++i) cin >> G.vexs[i];//依次输入顶点的信息 for (int i = 0;i < G.vexnum;++i)//初始化邻接矩阵,边的权值均置为极大值 for (int j = 0;j < G.vexnum;++j) G.arcs[i][j] = MaxInt; for (int k = 0;k < G.arcnum;++k) { cin >> v1 >> v2 >> w;//输入一条边依附的顶点和权值 i = LocateVex(G, v1);j = LocateVex(G, v2);//确定两个顶点v1和v2在G中的位置 G.arcs[i][j] = w;//边的权值置为w G.arcs[j][i] = G.arcs[i][j];//置边的对称点的权值也为w } return OK;}/*在图中查找顶点的位置LocateVex()函数*/int LocateVex(AMGraph G, VertexType u){//若在图中找到这个元素,则返回它的下标i,否则返回-1 int i; for (i = 0;i < G.vexnum;++i) if (u == G.vexs[i]) return i; return -1;}
(二)邻接表(链式)表示法(Adjacency List)
是图的链式存储结构,基本思想就是只存储图中存在的边的信息,对不相邻的顶点则不保留信息
对图中每个顶点vi建立一个带头结点的单链表,把与vi相邻接的顶点放在这个链表中,一个单链表对应邻接矩阵中的一行,称为边链表。1、无向图的邻接表表示
2、有向图的邻接表表示
3、图的邻接表的存储定义
分三部分:
1、图的结构定义
2、顶点的头结点结构
3、弧(边)的结点结构/*图的邻接表的存储定义*///弧的结点结构#define MVNum 100 //最大的顶点数typedef struct ArcNode{ int adjvex; //该边所指的顶点的位置 struct ArcNode* nextarc; //指向下一条边的指针 OtherInfo info; //和边相关的信息}ArcNode;//顶点的结点结构typedef struct VNode{ VertexType data;//顶点信息 ArcNode* firstarc;//指向第一条依附该顶点的边}VNode,AdjList[MVNum];//AdjList表示邻接表类型//AdjList v相当于VNode v[MVNum]//图的结构定义(邻接表)typedef struct{ AdjList vertices;//vertices是vertex的复数 int vexnum, arcnum;//图的当前顶点数和边数}ALGraph;/*说明*/ALGraph G;//定义了邻接表表示的图GG.vexnum = 5;G.arcnum = 6;//图G包含了5个顶点和6条边G.vertices[1].data = 'v2';//图G中第2个顶点是v2p = G.vertices[1].firstarc;//指针p指向顶点v2的第一个边结点p->adjvex = 4;//p指针所指边结点是到下标为4的结点的边
4、采用邻接表表示法创建无向图
【算法步骤】
1、输入总顶点数和总边数
2、建立顶点表1、依次输入点的信息存入顶点表中
2、使每个表头结点的指针域初始化为NULL3、创建邻接表
1、依次输入每条边依附的两个顶点
2、确定这两个顶点的序号i和j
3、将此边结点分别插入vi和vj对应的两个边链表的头部/*采用邻接表表示法创建无向图*/Status CreateUDG(ALGraph& G){//采用邻接表表示法,创建无向图G cin >> G.vexnum >> G.arcnum;//输入顶点数和弧数 for (int i = 0;i < G.vexnum;++i) { cin >> G.vertices[i].data;//输入顶点值 G.vertices[i].firstarc = NULL;//初始化表头结点的指针域为NULL } for (int k = 0;k < G.arcnum;++k)//输入各边,构造邻接表,头插法 { cin >> v1 >> v2;//输入一条边依附的两个顶点 i = LocateVex(G, v1);j = LocateVex(G.v2); p1 = new ArcNode;//生成一个新的边结点*p1 p1->adjvex = j;//邻结点序号为j p1->nextarc = G.vertices[i].firstarc;//firstarc为空,所以nextarc也指向空,即最后的一个结点 G.vertices[i].firstarc = p1;//将新结点*p1插入到顶点vi的边表头部 p2 = new ArcNode;//生成一个新的边结点*p2 p2->adjvex = i; p2->nextarc = G.vertices[j].firstarc;//插入弧结点到单链表 G.vertices[j].firstarc = p2;//将新结点*p2插入到顶点vi的边表头部 }//头插法 return OK;}
5、邻接矩阵与邻接表的比较
练习:画出有向图G的邻接矩阵、邻接表、逆邻接表
(三)十字链表(Orthogonal List)
十字链表是有向图的另一种链式存储结构,可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表
1、弧结点的结构
Tailvex:指示弧尾结点在图中的位置
headtex:指示弧头顶点在图中的位置
hlink:是指向弧头相同的下一条弧的指针
tlink:是指向弧尾相同的下一条弧的指针
Info:指向该弧的相关信息/*弧结点的结构*/typedef struct ArcBox{ int tailvex, headvex;//该弧的尾和头顶点的位置 struct ArcBox* hlink, * tlink;//分别为弧头相同和弧尾相同的弧的指针域 InfoType* info;//该弧相关信息的指针}ArcBox;
2、顶点结点的结构
每个顶点有一个结点,它相当于出边表和入边表的表头结点。数据成员data存放与该顶点的相关信息。链域firstin指示以该顶点为弧头的第一个弧结点。链域firstout指示以该结点为弧尾的第一个弧结点。
/*顶点结点的结构*/typedef struct VexNode{ VertexType data; ArcBox* firstin, * firstout;//分别指向该顶点第一条入弧和出弧}VexNode;//ArcBox为弧结点变量
3、图的结构定义
/*图的结构定义*/typedef struct{ VexNode xlist[MAX_VERTEX_NUM];//表头向量 int vexnum, arcnum;//有向图的当前顶点数和弧数}OLGraph;
4、实例
5、有向图G的十字链表
(四)邻接多重表(Adjacent MultiList)
邻接多重表是无向图的另一种链式存储结构,由于用邻接表存储无向图时,虽然容易求出顶点和边的各种信息,但在邻接表中每一条边有两个结点,分别在第i和j个链表中,给图的某些操作带来不便,在邻接多重表中,每一条边只有一个边结点,为有关的处理提供了方便。
1、边结点的结构
mark:为标志域,可用以标记该条边是否被搜索过
ivex和jvex为该边依附的两个顶点在图中的位置
ilink:指向下一条依附于顶点的ivex的边
jlink:指向下一条依附于顶点jvex的边
info:为指向和边相关的各种信息个指针域/*边结点结构*/typedef struct EBox{ VisitIf mark;//访问标志域 int ivex, jvex;//该边依附的两个顶点在表头数组中的位置 struct Ebox* ilink, * jlink;//分别指向依附于ivex和jvex的下一条边 InfoType* info;}EBox;
2、顶点结点的结构
/*顶点结点的结构*/typedef struct VexBox{ VertexType data;//存与顶点相关的信息 EBox* firstedge;//指向第一条依附于该顶点的边}VexBox;
3、图的结构定义
/*图的结构定义*/typedef struct{ VexBox adjmulist[MAX_VERTEX_NUM];//表头向量 int vexnum, edgenum;//无向图的当前顶点数和弧数}OLGraph;//VexNode为顶点结点变量
4、实例
4、练习:画出无向图G的邻接多重表
-
假设以邻接矩阵作为图的存储结构_数据结构|图的邻接矩阵与深度、广度优先搜索
2020-11-24 08:56:17由于图的结构比较复杂,任意两个顶点之间都可能存在联系,因此无法以数据元素在存储区中的物理位置来表示元素之间的关系,即图没有顺序存储结构,但可以借助二维表来表示元素之间的关系,一般称为邻接矩阵。...线性存储元素时,元素的关系也同时确定了。而非线性数据结构就不同了,需要同时考虑存储数据元素和数据元素的逻辑关系。例如,图这种数据结构的矩阵存储就是用一个顶点向量存储顶点元素,再用一个邻接矩阵存储元素关系。
由于图的结构比较复杂,任意两个顶点之间都可能存在联系,因此无法以数据元素在存储区中的物理位置来表示元素之间的关系,即图没有顺序存储结构,但可以借助二维表来表示元素之间的关系,一般称为邻接矩阵。另一方面,由于图的任意两个顶点间都可能存在关系,因此,用链式存储表示图结构是很自然的事,其中有代表性的一种链式存储称为邻接表。
在图的邻接矩阵表示法中,用邻接矩阵表示顶点间的相邻关系,而用一个顺序表来存储顶点信息。
图的邻接矩阵表示法适用范围广泛,可以用来描述有向图、有向表、无向图、无向表。
邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的矩阵。设G(V,E)是具有n个顶点的图,则G的邻接矩阵是具有如下性质的n阶方阵:
则上图的邻接矩阵可以表示为:
若是带权图(网),则G的邻接矩阵是具有如下性质的n阶方阵:
其邻接矩阵可以表示为:
邻接矩阵表示法表示图一般可抽象如下:
#define MaxInt 32767 // 表示极大值,即∞#define MVNum 100 // 最大顶点数typedef char VerTexType; // 假设顶点的数据类型为字符型typedef int ArcType; // 假设边的权值类型为整型typedef struct{ VerTexType vexs[MVNum]; // 顶点表 ArcType arcsMVNum][MVNum]; // 邻接矩阵 int vexnum,arcnum; // 图的当前顶点数和边数}AMGraph;
图遍历背后的关键思想是在我们第一次访问每个顶点时对其进行标记,并跟踪我们尚未完全探索的内容。尽管面包屑或解开的线被用来标记童话迷宫中参观过的地方,但我们将依赖布尔标志或枚举类型来进行。
每个顶点将以三种状态之一存在:
未发现-顶点处于原始状态。
已发现-顶点已找到,但尚未检查其所有入射边。
已处理–访问所有关联边后的顶点。
显然,一个顶点只有在我们发现它之后才能被处理,所以每个顶点的状态在遍历过程中从未发现到发现再到处理。
我们还必须维护一个包含我们已经发现但尚未完全处理的顶点的结构。最初,只有一个起始顶点被认为是被发现的。为了完全探索一个顶点v,我们必须计算每一条离开v的边。如果一条边转到一个未发现的顶点x,我们标记x 为“已发现”并将其添加到要做的工作列表中。我们要忽略处理过的顶点的边,因为进一步的探索不会告诉我们关于图的任何新的东西。我们还可以忽略到已发现但未处理的顶点的任何边,因为目标已位于要处理的顶点列表中。
BFS(Depth First Search--DFS)和DFS(Breadth First Search--BFS)结果的区别在于它们探索顶点的顺序。此顺序完全取决于用于存储已发现但未处理的顶点的容器数据结构。
Stack–通过将顶点存储在后进先出(last-in,first-out,LIFO)堆栈中,我们通过沿着路径一直前行、访问新邻居(如果有的话)和仅当我们被以前发现的顶点包围时才回退来探索新的顶点。因此,我们的探索很快偏离了起点,定义了深度优先搜索。
一旦发现一个顶点,它就被放置在栈(显式或隐式栈)中。由于我们按后入先出的顺序处理这些顶点,所以最新的顶点将首先展开,这些顶点正是最远离根的顶点。
队列-通过将顶点存储在先进先出(FIFO)队列中,我们首先探索最古老的未探索顶点。因此,我们的探索从起始顶点缓慢地向外辐射,定义了广度优先搜索。
一旦发现一个顶点,它就被放置在队列中。由于我们按先入先出的顺序处理这些顶点,所以最旧的顶点将首先展开,这些顶点正是最接近根的顶点。
深度优先搜索有一个简洁的递归实现,它消除了显式使用堆栈的需要。
我们需要能够对每个入口和出口分别采取行动。
深度优先搜索的另一个重要特性是它将无向图的边划分为两类:tree edges和back edges。tree edges发现新的顶点,并且是在parent关系中编码的顶点。back edges是那些其另一个端点是被展开顶点的ancestor的边,因此它们指向树中。
1 深度优先遍历(先孩子后上一辈的兄弟)
优先向深度探索,一直走到头才回头到路径的上一个相邻顶点,直到回溯到最开始顶点。
如上图的深度优先遍历的顺序:0 1 2 3 4 5 6 8 9 7
如果使用递归,则相当于使用了一个隐式的栈数据结构(编译器对函数递归调用的压栈和回归的出栈操作)。
如果使用抱定代,则需要显式使用一个栈数据结构。
2 广度优先遍历(先兄弟后孩子)
广度优先遍历,也就是从某一个顶点开始,优先访问全部的相邻顶点,按层次辐射,直到全部顶点访问完。
如上图使用广度优先遍历的顺序:0 1 3 2 4 5 6 7 8 9
广度优先遍历需显式使用一个队列的数据结构。广度优先搜索是一种分层的搜索过程,不像深度优先遍历那样有往回退的情况。因此,广度优先遍历不能递归实现,可以使用先进先出的队列来实现。
深度搜索与广度搜索的控制结构和产生系统很相似,唯一的区别在于对扩展节点选取上。由于其保留了所有的前继节点,所以在产生后继节点时可以去掉一部分重复的节点,从而提高了搜索效率。这两种算法每次都扩展一个节点的所有子节点,而不同的是,深度搜索下一次扩展的是本次扩展出来的子节点中的一个,而广度搜索扩展的则是本次扩展的节点的兄弟节点。也就是说,广度优先搜索会优先考虑最早被发现的顶点,也就是说离起点越近的顶点优先级越高。深度优先搜索会优先考虑最后被发现的顶点。
在20世纪50年代,广度优先搜索最早由Edward F. Moor在研究迷宫路径问题时发现,深度优先搜索在人工智能方面获得了广泛应用。
#include #include typedef int VertexType; // 顶点类型应由用户定义typedef int EdgeType; // 边上的权值类型应由用户定义#define MAXSIZE 15 // 存储空间初始分配量#define MAXEDGE 15#define MAXVEX 10#define INFINITY 65535/* 0-----1 | /| | 2 | | / | | / 4 5---8 |/ / / 3 7 6--9 */int arc[MAXVEX][MAXVEX]={ // 布尔数组{0,1,0,1,0,0,0,0,0,0},{1,0,1,0,1,0,0,0,0,0},{0,1,0,1,1,0,0,0,0,0},{1,0,1,0,0,0,0,0,0,0},{0,1,1,0,0,0,0,0,0,0},{0,0,0,0,0,0,1,1,1,0},{0,0,0,0,0,1,0,0,1,1},{0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,1,1,0,0,0},{0,0,0,0,0,0,1,0,0,0}};// 0的元素数目远远多于非0元素的数目,称为稀疏矩阵,用链式存储较节省空间typedef struct{ VertexType vexs[MAXVEX]; // 顶点表 EdgeType arc[MAXVEX][MAXVEX]; // 邻接矩阵,可看作边表 int numVertexes, numEdges; // 图中当前的顶点数和边数 }MGraph;typedef struct // 循环队列顺序存储结构{ int data[MAXSIZE]; int front; // 头指针 int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置}Queue;void CreateMGraph(MGraph *G){ int i,j; G->numEdges=15; G->numVertexes=10;for(i=0; inumVertexes; i++) // 建立顶点表G->vexs[i] = i; for (i = 0; i < G->numVertexes; i++) // 初始化图 { for (int j = 0; j < G->numVertexes; j++) { G->arc[i][j]=arc[i][j]; } }} bool visited[MAXVEX]; // 访问标志的数组void DFS(MGraph G, int i) // 邻接矩阵的深度优先递归算法{ visited[i] = true; printf("%d ", G.vexs[i]); // 打印顶点,也可以其它操作 for(int j=0; jfront=0; Q->rear=0; return true;}bool QueueEmpty(Queue Q){ if(Q.front==Q.rear) // 队列空的标志 return true; else return false;}bool EnQueue(Queue *Q,int e){ if ((Q->rear+1)%MAXSIZE == Q->front) // 队列满的判断 return false; Q->data[Q->rear]=e; // 将元素e赋值给队尾 Q->rear=(Q->rear+1)%MAXSIZE; // rear指针向后移一位置, // 若到最后则转到数组头部 return true;}bool DeQueue(Queue *Q,int *e) // 删除Q中队头元素,用e返回其值{ if (Q->front == Q->rear) // 队列空的判断 return false; *e=Q->data[Q->front]; // 将队头元素赋值给e Q->front=(Q->front+1)%MAXSIZE; // front指针向后移一位置, // 若到最后则转到数组头部 return true;}
无论那种搜索,都是通过对一个线性表进行处理,只不过是先处理头部还是尾部的问题罢了。处理头部优先的时候,也就是先加入的先探索,就是广度优先了,因为,头部的都是兄弟节点;而尾部的则是深度优先,因为放入尾部的都是刚刚生产出来的节点,后加入的先探索——也就是所谓一条路走到死。 同理可以联想到启发式搜索。启发式搜索就是先以你自定义的优先级处理,然后再以广度为优先级处理。 所以,归根结底,所谓的搜索,就是一种定义了优先级的枚举。
-End-
-
假设以邻接矩阵作为图的存储结构_最基础!图的基本概念 与 图的存储:邻接矩阵 邻接表
2020-11-24 10:36:06应用情况 (邻接矩阵只适用于没有重边(或重边可以忽略)的情况,一般情况下不用考虑) 邻接矩阵 空间复杂度高:为O(n^2) 查询一条边的存在情况快: O(1) 遍历一个点的所有出边 :O(n) 遍历整个图 :O(n^2) 邻接表 邻接... -
假设以邻接矩阵作为图的存储结构_学习数据结构第五章:图(图的存储方法)...
2020-12-03 17:59:24邻接矩阵法下面是一个无向图的表示,我们使用一个一维数组存放点集,使用一个二维数组存放边集二维数组表示边:行号表示其实端点,列号表示结束端点,值表示该边是否存在,以及该边的权重,我们称这种二维数组表示的... -
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以...
2012-12-21 21:55:35假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注:图中不存在顶点到自己的弧) -
数据结构 邻接矩阵深度/广度遍历 图
2020-04-26 10:01:50// 8.1 以邻接矩阵作为存储结构 /*****************************/ /* 图和函数定义 */ /*****************************/ #include"stdio.h" #include"stdlib.h" #define MaxVertexNum 100 //定义最大顶点数 ... -
再回首,数据结构——以邻接矩阵、邻接表表示的图的深度、广度优先搜索
2015-05-28 11:30:17最近在复习数据结构,顺便看看大一的时候写的代码,看完之后比当初有了...//以邻接矩阵作为图的存储结构的深度优先遍历算法 int visited[MaxSize]={0}; void DFS1(AdjMatrix *g, int i) { printf("%3c",g->vexs[i]) -
数据结构之以邻接矩阵实现图的基本操作(一)
2020-02-18 21:12:511.图的基本定义 此处使用了字符作为顶点表存储的数据类型,整型作为边表 数据类型 typedef struct{ VertexType Vex[MaxVertexNum]... //邻接矩阵,边表 int vexnum,arcnum; //当前顶点数和弧数 }MGraph; 2.... -
无向图的邻接矩阵转为对应邻接表
2020-12-11 17:52:47这道题是一道很有意思的题,作为最后一道大题,同时考察了对邻接矩阵和邻接表两种图的基本存储类型的掌握。 题目中没有给出邻接矩阵和邻接表的结构定义,所以这里在答案中均需自行给出。 第一个for循环初始化邻接表... -
图的存储结构之邻接表
2019-03-22 11:00:55邻接矩阵的缺点:边数相对顶点较少的图,极大地浪费了存储空间。 把数组与链表相结合的存储方法称为邻接表。(Adjacency List) 邻接表的处理办法: 顶点用一个一维数组存储(较容易读取顶点信息),每个数据元素... -
爱奇艺2019秋招Java方向笔试题(B)
2019-09-23 22:54:53爱奇艺2019秋招Java方向笔试题(B) 1. 已知一个由5个顶点8条边构成的有向图,... 若以邻接矩阵作为存储结构,矩阵中非0元素个数为16 解析: 8条边 <=> 8个入度、8个出度 2. 已知二叉树A(B(,D(F,H)),C(,E(G(... -
图的邻接表表示法及遍历
2017-06-11 14:05:16常用的是邻接矩阵和邻接表,这里邻接矩阵不做讲解,如下所有代码都是以邻接表作为存储结构,所以这里就只讲解下邻接表。那么什么是邻接表呢?如何构造呢? 邻接表是一种链式存储。就如上图,一共有四个顶点... -
Java实现图的遍历(深搜与广搜)
2017-04-26 09:50:39本文以邻接矩阵作为存储结构,用Java实现图的遍历,话不多说,先给出的图的结构,如下: 1、深度优先搜索遍历 思想: 沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过... -
数据结构习题解析与实验指导第六章(图)课后算法设计题
2020-09-02 23:17:491.分别以邻接矩阵和邻接表作为存储结构,实现以下图的基本操作: (1)增加一个新顶点vvv, InsertVex(G, v); (2)删除顶点vvv及其相关的边,DeleteVex(G, v); (3)增加一条边<v, w>,InsertArc(G, v, w); ... -
图的创建及相关操作
2020-01-31 15:33:53以邻接矩阵和邻接表作为图的存储结构,分别实现增加、删除边,增加、删除顶点,求各顶点的度(有向图包括入度和出度),存储结构之间的转换,判断图的连通性和输出连通分量的个数,给出顶点u和v,判断u到v是否存在... -
数据结构之图的应用
2016-11-14 20:34:03要求:分别以邻接矩阵和邻接表作为存储结构,以用户指定的顶点为起始点,实现无向连通图的深度优先及广度优先搜索遍历,并输出遍历的结点序列。 提示:首先,根据用户输入的顶点总数和边数,构造无向 -
图的应用
2010-10-02 10:22:07在做实验之前更多的是要知道程序的功能,以便设计更为人性化程序*//*该实验采用邻接矩阵作为存储结构首先建立以邻接矩阵为存储结构的图的抽象数据类型方法的实现:对建立的无向图,进行深度及广度优... -
第6章课后习题算法设计题(严蔚敏数据结构c语言版第2版)
2020-12-05 07:38:276-1 分别以邻接矩阵和邻接表作为存储结构,实现以下图的基本操作: ①增加一个新顶点v,InsertVex(G,v) ②删除顶点v及其相关的边,DeleteVex(G,v) ③增加一条边<v,w>,InsertArc(G,v,w) ④删除一条边<... -
数据结构之图
2018-07-02 16:36:06存储结构 邻接矩阵 邻接矩阵适合于点少边多的图,而对于边少的图,可以考虑用邻接表。 临接表 图的遍历 深度优先遍历的方法如下。类似于树的前序遍历。同样可以采用递归实现。 a) 假设初始状态是图中... -
图的最小生成树算法
2012-03-20 11:03:01采用邻接矩阵作为网的存储结构,使用prim算法实现最小生成树。 三、实验内容 1、 设计程序,完成无向网的邻接表的存储,构造网,用prim算法生成它的最小生成树。 2、 调试程序。设计一个无向网,以邻接表为... -
图的操作
2010-07-21 16:10:00实验四 图的操作 一、实验内容图的生成,图的遍历。 二、实验目的1. 掌握图的基本存储方法――邻接表和邻接矩阵。...以邻接矩阵或邻接表作为存储结构建立一个无向图。2.深度(或广度)优先搜索该无向图,输出遍历 -
VOL.1 图的创建与遍历
2020-11-04 18:27:47首先,采用邻接矩阵创建图,由于不需要考虑权值问题,因此在邻接矩阵中,0表示没有边,1表示有边,通过两层循环从矩阵转为邻接表的存储结构。邻接表中有两种节点类型,顶点节点按照序号顺序存储在一个数组中,包含... -
深度优先搜索
2019-09-19 22:58:03*以邻接矩阵作为图的存储结构 */ #include<stdio.h> #include<stdlib.h> #include<string.h> #define MAX 100 typedef struct Edge { struct Edge *nextEdge; int weight, sn... -
算法系列笔记7(有关图的算法一—搜索,拓扑排序和强连通分支)
2016-04-09 20:57:08邻接表表示法存在很强的适应性,但是也有潜在的不足,当要快速的确定图中边(u,v)是否存在,只能在顶点u的邻接表中搜索v,没有更快的方法,此时就可以使用邻接矩阵,但要以占用更多的存储空间作为代价;此外当图不是... -
严蔚敏:数据结构题集(C语言版)
2009-09-02 18:38:345.7.3 建立广义表的存储结构 第6章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 6.3.2 线索... -
Self-supervised Training of Graph Convolutional Networks
2020-06-30 16:51:54GCNs需要邻接矩阵作为输入来定义这些非网格数据之间的关系,这就导致所有的数据,包括训练数据、验证数据和测试数据,通常只形成一个用于训练的图结构数据。此外,邻接矩阵通常是预定义的且平稳的,这使得数据增强...