《数据结构课件 》由会员分享，可在线阅读，更多相关《数据结构课件 （98页珍藏版）》请在金锄头文库上搜索。
1、 7.1 图的定义和术语7.2 图的存储结构 7.3 图的遍历7.4 图的连通性7.5 拓扑排序和关键路径7.6 最短路径问题图是由一个顶点集 V 和一个弧集V R构成的数据结构。Graph = (V, VR ) 其中，VR| v,wV 且 P(v,w)表示从 v 到 w 的一条弧，并称 v 为弧尾，w 为弧头。谓词 P(v,w) 定义了弧 的意义或信息。7.1 图的定义和术语由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。EACBD例如:G1 = (V1, VR1)其中 V1=A, B, C, D, E VR1=, , , , 若VR 必有VR, 则称 (v,w) 为顶点 v 和
2、顶点 w 之间存在一条边。BCAFED由顶点集和边 集构成的图称作无向图。例如: G2=(V2,VR2) V2=A, B, C, D, E, F VR2=(A, B), (A, E),(B, E), (C, D), (D, F),(B, F), (C, F) 名词和术语网、子图 完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、简单路径、简单回路连通图、连通分量、 强连通图、强连通分量生成树、生成森林ABECFAEFBBC设图G=(V,VR) 和 图 G=(V,VR), 且 VV, VRVR, 则称 G 为 G 的子图。159721113 2弧或边带权的图分别称作有向网或 无向网。假
3、设图中有 n 个顶点，e 条边，则含有 e=n(n-1)/2 条边的无向图称作完全图;含有 e=n(n-1) 条弧的有向图称作 有向完全图;若边或弧的个数 e，若G是无向的，/则还增添对称弧。DeleteArc( /在G中删除弧，若G是无向的，/则还删除对称弧。遍 历DFSTraverse(G, v, Visit(); /从顶点v起深度优先遍历图G，并对每 /个顶点调用函数Visit一次且仅一次。BFSTraverse(G, v, Visit(); /从顶点v起广度优先遍历图G，并对每 /个顶点调用函数Visit一次且仅一次。7.2 图的存储结构一、图的数组(邻接矩阵)存储表示二、图的邻接表存
4、储表示三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示Aij=0 (i,j)VR1 (i,j)VR一、图的数组(邻接矩阵)存储表示BACDFE定义:矩阵的元素为有向图的邻接矩阵 为非对称矩阵ABECD#define MAXVERTEXNUM 20typedef enum DG,DN,UDG,UDN GraphKind;typedef struct ArcCell / 弧的定义VRType adj; / VRType是顶点关系类型。/ 对无权图，用1或0表示相邻否；/ 对带权图，则为权值类型。InfoType *info; / 该弧相关信息的指针 ArcCell,AdjMatrixM
5、AXVERTEXNUMMAXVERTEXNUM;typedef struct / 图的定义VertexType vexsMAXVERTEXNUM; / 顶点信息 AdjMatrix arcs; / 弧的信息 int vexnum, arcnum; / 顶点数，弧数 GraphKind kind; / 图的种类标志 MGraph;DBACFE二、图的邻接表存储表示A 1 4B 0 4 5C 3 5D 2 5E 0 1F 1 2 30 1 2 3 4 5有向图的邻接表1 4230 120 1 2 3 4ABCDEABECD可见，在有向图的邻接表中不易找到指向该顶点的弧ABECD有向图的逆邻接表在有
6、向图的逆邻接表中，对每个顶点，链接的是指向该顶点的弧01234A B C D E 3032041typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置struct ArcNode *nextarc; / 指向下一条弧的指针InfoType *info; / 该弧相关信息的指针 ArcNode;adjvex nextarc info弧的结点结构typedef struct VNode VertexType data; / 顶点信息ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAXVERTEXNUM;da
7、ta firstarc顶点的结点结构typedef struct AdjList vertices;int vexnum, arcnum; int kind; / 图的种类标志 ALGraph;图的结构定义(邻接表)三、有向图的十字链表存储表示 ABCABC0 1 20 2 0 12 1 2 0 弧的结点结构弧尾顶点位置 弧头顶点位置 弧的相关信息指向下一个 有相同弧尾 的结点指向下一个 有相同弧头 的结点typedef struct ArcBox / 弧的结构表示int tailvex, headvex; InfoType *info;struct ArcBox *hlink, *tlink
8、; ArcBox;tailvexheadvexhlink tlinkinfo顶点的结点结构顶点信息数据 指向该顶点的 第一条入弧指向该顶点的 第一条出弧typedef struct VexNode / 顶点的结构表示VertexType data;ArcBox *firstin, *firstout; VexNode;datafirstinfirstouttypedef struct VexNode xlistMAXVERTEXNUM; / 顶点结点(表头向量) int vexnum, arcnum;/有向图的当前顶点数和弧数 OLGraph;有向图的结构表示(十字链表)四、无向图的邻接多重表
9、存储表示typedef struct Ebox VisitIf mark; / 访问标记int ivex, jvex;/该边依附的两个顶点的位置struct EBox *ilink, *jlink; InfoType *info; / 该边信息指针 EBox;边的结构表示typedef struct / 邻接多重表VexBox adjmulistMAXVERTEXNUM;int vexnum, edgenum; AMLGraph;顶点的结构表示typedef struct VexBox VertexType data;EBox *firstedge; / 指向第一条依附该顶点的边 VexBox
10、;无向图的结构表示7.3 图的遍历从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点 仅被访问一次的过程。深度优先搜索广度优先搜索从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。一、深度优先搜索遍历图连通图的深度优先搜索遍历SG1SG2SG3W1、W2和W3 均为 V 的邻接点，SG1、SG2 和 SG3 分别为含顶点 W1、W2和W3 的子图。访问顶点 V ; for (W1、W2、W3 )若该邻接点W未被访问，则从它出发进行深度优先搜索遍历。Vw1w3w2从上页的图解可见:1. 从
11、深度优先搜索遍历连通图的过 程类似于树的先根遍历;解决的办法是:为每个顶点设立一个 “访问标志 visitedw”;2. 如何判别V的邻接点是否被访问？如图如图G4G4：深到底回退深到底V1V2V4V8V5（V2V8均已访问）深到底V3V6V7回退访问V1V2V3V4V5V6V7V8 visited0n-1visited0n-1是一个辅助数组，记载顶点是否被访问过是一个辅助数组，记载顶点是否被访问过visitedi=TRUE, 已访问过FALSE, 未访问过（初值）注意： DFS序列不唯一，它与算法、图的存储结构及初始出发点有关。深度优先搜索递归过程深度优先搜索递归过程 （采用邻接矩阵存储图）
12、：void DFS(MGraph G,int i) cout”;visitedi=TRUE;for(j=0;j”;visitedi=TRUE;p=G.verticesi.firstarc;while(p) if(!visitedp-adjvex) DFS(G,p- adjvex);p= p-nextarc; 首先将图中每个顶点的访问标志设为 FALSE, 之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。非连通图的深度优先搜索遍历void DFSTraverse(Graph G) / 对图 G 作深度优先遍历。for (v=0; vw1, V-
13、w2, V-w8 的路径长度为1; V-w7, V-w3, V-w5的路径长度为2; V-w6, V-w4 的路径长度为3。w1 Vw2w7w6w3w8w5w4从图中的某个顶点V0出发，并在访问此 顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次 序依次访问它们的邻接点，直至图中所有 和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复 上述过程，直至图中所有顶点都被访问到 为止。广度优先搜索（广度优先搜索（breadth-first-search)breadth-first-search)1)1) 首先访问指定首
14、先访问指定顶点顶点v0v0，将将v0v0作为当前顶点作为当前顶点; ;2)2) 访问当前顶点的访问当前顶点的所有未访问过的邻接点所有未访问过的邻接点，3)3) 并依次将访问的这些邻接点作为当前顶点并依次将访问的这些邻接点作为当前顶点; ;4)4) 重复重复2 2），）， 直到直到所有顶点所有顶点被访问为止。被访问为止。对右图广度优先搜索，访问顶点序列为：对右图广度优先搜索，访问顶点序列为：V1 V2 V3 V4 V5 V6 V7 V8V1 V2 V3 V4 V5 V6 V7 V8V8V1V2V3V4V5 V6V7注意： BFS序列不唯一，它与算法、图的存储结构及初始出发点有关。广度优先搜索算法（以邻接矩阵作存储结构）：广度优先搜索算法（以邻接矩阵作存储结构）：void BFSTraverse(MGraph G) for(i=0;iadjvex)coutadjvex.data;visitedp-adjvex=TRUE; EnQueue(Q,p-adjvex); p=p-nextarc; 7.4 7.4 图的连通性问题图的连通性问题一、无向图的连通分量和生成树一、无向图的连通分量和生成树 对连通图，
