中国科学技术大学：《数据结构及其算法》课程教学资源（课件讲稿）第7章 图

邻接矩阵 邻接表 7.2图的存储结构-十字链表 无，艺cc1 2局同 。十字链表一有向图(P165) 无向网：G心s中值不为无向图网：图中表结点数目的 ,有向图 。邻接表-出边表，求入度不方便 统计边孤数 NFINITY的元货个数的一半， 有商器：我Gar1 。逆邻接表-入边表 有向图网：图中表结点的数目， ,十字纯表域瓢被孤的 弧尾相同的弧的能城 00 有向网：Gcs中值不为 弧站燕 NFINITY的元素个数 tailvexhead小a=rnrc 被顶店被顶点的幕一条出薰 结论：邻接矩阵适于密图的存情，邻接表适于等说图的存储： 项点结点 邻接表求有向图的项点的入度不方便，要追历各个顶点的接表。， data firstin firstout 31/106 回 32/106 图 7.2图的存储结构-十字链表 ■十字链表一有向图 2阳的在储结构-+字链我 ·十字链表一有向图 #define MAX_VERTEX_NUM 20 顶，点结点 typedef struct VexNodef ∥孤结，点 VertexType data; typedef struct ArcBox{ ArcBox *firstin,*firstout; int tailvex,headvex; VexNode: ∥十字链表 struct ArcBox *hlink,*tlink; typedef struct InfoType *info; VexNode xlist[MAX_VERTEX_NUM]: ArcBox; int vexnum,arcnum; 33/106 图 OLGraph; 图 7.2图的存储结构-邻接多重表 」7.2图的存储结构邻接多重表 邻接多重表一无向图(P166) 邻接多重表一无向图 ·无向图 #define MAX VERTEX NUM 20 。邻接表-每” 该边 指向下一条依附于 typedef enum {unvisited,visited)VisitIf; ·多重邻排 顶点ivex的边 ∥边结点 标 填原丁 边蛙 typedef struct EBox{ mark ivex ilink ivex linLlinto VisitIf mark; 第一条依附于顶点的边 int ivex,jvex; 顶点结点 struct EBox *ilink,*jlink; InfoType *info; data firstedge }EBox; 5/1oe 图 36/106 画

31/106 32/106 7.2 图的存储结构-十字链表 „ 十字链表—有向图 (P165) „ 有向图 „ 邻接表-出边表,求入度不方便 „ 逆邻接表-入边表 „ 十字链表— 弧结点数==弧数 tailvex headvex hlink tlink info 弧结点 顶点结点 data firstin firstout 该弧的尾顶点的位置 该弧的头顶点的位置 弧头相同的弧的链域 弧尾相同的弧的链域 该顶点的第一条入弧 该顶点的第一条出弧 33/106 7.2 图的存储结构-十字链表 „ 十字链表—有向图 #define MAX_VERTEX_NUM 20 // 弧结点 typedef struct ArcBox{ int tailvex, headvex; struct ArcBox *hlink, *tlink; InfoType *info; }ArcBox; 34/106 7.2 图的存储结构-十字链表 „ 十字链表—有向图 //顶点结点 typedef struct VexNode{ VertexType data; ArcBox *firstin, *firstout; }VexNode; // 十字链表 typedef struct{ VexNode xlist[MAX_VERTEX_NUM]; int vexnum, arcnum; }OLGraph; 35/106 7.2 图的存储结构-邻接多重表 „ 邻接多重表—无向图 (P166) „ 无向图 „ 邻接表-每条边对应2个表结点 „ 多重邻接表— 边结点数==边数 mark ivex ilink jvex jlink info 边结点 顶点结点 data firstedge 标记该边是否被搜索过 该边依附的一个顶点在 图中的位置 指向下一条依附于 顶点ivex的边 第一条依附于该顶点的边 36/106 7.2 图的存储结构-邻接多重表 „ 邻接多重表—无向图 #define MAX_VERTEX_NUM 20 typedef enum { unvisited, visited} VisitIf; // 边结点 typedef struct EBox{ VisitIf mark; int ivex, jvex; struct EBox *ilink, *jlink; InfoType *info; }EBox;

7.2图的存储结构-邻接多重表 7.3图的遍历(1) 邻接多重表一无向图 。图的遗历 ∥顶，点结点 顶点之间的邻接关系m:n typedef struct Vex Boxf VertexType data; 引入访问标志数组visited0.n-1],防止顶点多 EBox *firstedge; 次被访问 VexBox: 。图的遗历种类 川邻接多重表 。深度优先遍历：→树的先序遭历 typedef structf 从莱顶点出发，访问该顶点，然后依次从的来被访 Vex Box adjmulist[MAX_VERTEX_NUM]; 问的邮接点出发派度优先通历图，直至图中所有和有 int vexnum,edgenum; AMLGraph; 回 路径相通的顶燕虾被访问到： 38106 ☑图 7.3图的遍历(2) 7.3图的遍历(3) ·图的速历种类 ·广度优先遵历：)树的层次遭历 从某顶旅”出发，访问被顶点，然后依次访问v的所有 来曾访问过的你接点，再分别从这些邻接点出发依次 访问它们的怀接点，并使“先放拉问的顶点的邻接点 先于“后被过问的顶点的年接点”放黄问，直至用中所 有已被访问的项成的饰接点都被访问到： 生成树 。若困中还存在尚来访问过的顶点，则另选图中一个来 遍历序列 曹被访问的项点作起地点，继续重复上述过程 深度优先旋素(DS) 广度优先校素(BFS) 39/106 回 V V2 Vi VsVs VV V7 0H06 ViV2VaViVsVaV,Vs 图 基于ADT Graphe的DFS算法（算法7.4和7.5） 73图的遍4) Boolean visited[MAX VERTEX NUMI: void DFSTraverse(Graph G,Status (*Visit)(Graph G.int v)) DFSTraverse(G) for (v-0;v<G.vexnum;++v)visitedlv]=FALSE; ,基于ADT Graph for (v-0;v <G.vexnum;++v) if (!visited v) ·基于某种在储结构：邻接矩阵/邻接表/十字链 DFS(G,v,Visit); 表/邻接多重表 ■BFSTraverse(G) void DFS(Graph G,int v,Status (*Visit)(Graph G,int v)) ,基于ADT Graph visitedlv]=TRUE;Visit(G,v); ,基于某种存储结构：邻接矩阵/邻接表/十字链 for (w-FirstAdjVex(G,v);w;w-NextAdjVex(G,v,w)) 表/邻接多重表 if (visitedwl) DFS(G.w.Visit): 41/106 图 42/106

37/106 7.2 图的存储结构-邻接多重表 „ 邻接多重表—无向图 // 顶点结点 typedef struct VexBox{ VertexType data; EBox *firstedge; }VexBox; //邻接多重表 typedef struct{ VexBox adjmulist[MAX_VERTEX_NUM]; int vexnum, edgenum; }AMLGraph; 38/106 7.3 图的遍历(1) „ 图的遍历 顶点之间的邻接关系m : n 引入访问标志数组visited[0..n-1]，防止顶点多 次被访问 „ 图的遍历种类 „ 深度优先遍历：Æ 树的先序遍历 从某顶点v 出发，访问该顶点，然后依次从v 的未被访 问的邻接点出发深度优先遍历图，直至图中所有和v 有 路径相通的顶点都被访问到； 39/106 7.3 图的遍历(2) „ 图的遍历种类 „ 广度优先遍历：Æ 树的层次遍历 从某顶点v 出发，访问该顶点，然后依次访问v 的所有 未曾访问过的邻接点，再分别从这些邻接点出发依次 访问它们的邻接点，并使“先被访问的顶点的邻接点” 先于“后被访问的顶点的邻接点” 被访问，直至图中所 有已被访问的顶点的邻接点都被访问到； „ 若图中还存在尚未访问过的顶点，则另选图中一个未 曾被访问的顶点作起始点，继续重复上述过程 40/106 7.3 图的遍历(3) V1 V2 V3 V4 V5 V6 V7 V8 V1 V2 V3 V4 V5 V6 V7 V8 深度优先搜索(DFS) V1 V1 V2 V2 V4 V4 V8 V5 V8 V5 V3 V3 V6 V6 V7 V7 生成树 遍历序列 广度优先搜索(BFS) V1 V1 V2 V2 V3 V3 V4 V4 V5 V5 V6 V6 V7 V7 V8 V8 最短 路径! 41/106 7.3 图的遍历(4) „ DFSTraverse(G) „ 基于ADT Graph „ 基于某种存储结构：邻接矩阵/邻接表/十字链 表/邻接多重表 „ BFSTraverse(G) „ 基于ADT Graph „ 基于某种存储结构：邻接矩阵/邻接表/十字链 表/邻接多重表 42/106 基于ADT Graph的DFS算法(算法7.4和7.5) Boolean visited[MAX_VERTEX_NUM]; void DFSTraverse(Graph G, Status ( *Visit ) (Graph G, int v) ) { for ( v = 0; v < G.vexnum; ++v ) visited[v] = FALSE; for ( v = 0; v < G.vexnum; ++v ) if ( !visited[v] ) DFS(G, v, Visit); } void DFS(Graph G, int v, Status ( *Visit ) (Graph G, int v) ) { visited[v] = TRUE; Visit(G, v); for ( w = FirstAdjVex(G, v); w; w = NextAdjVex(G, v, w) ) if ( !visited[w] ) DFS(G, w, Visit); }