数据结构高春晓71图

1、ABCDEABCDE 7.1 抽象数据类型图的定义抽象数据类型图的定义 7.2 图的存储表示图的存储表示 7.3 图的遍历图的遍历 7.4 最小生成树最小生成树 7.5 重（双）连通图和关节点重（双）连通图和关节点 7.6 两点之间的最短路径问题两点之间的最短路径问题 7.7 拓扑排序拓扑排序 7.8 关键路径关键路径 7.1.1 图的定义图的定义 图图(Graph)是由一个是由一个顶点顶点(Vertex)集集 V 和一个和一个弧弧(Arc)集集 R构成的数据结构。构成的数据结构。 Graph = (V , R ) 其中其中 R| v,wV 且且 P(v,w) 表示从表示从 v 到到 w 的一

2、条弧，并称的一条弧，并称 w 为弧头，为弧头，v 为弧尾。为弧尾。 谓词谓词 P(v,w) 定义了弧定义了弧 的意义或信息的意义或信息 有向图有向图(Digraph)：由于：由于“弧弧”是有方向的，因此称是有方向的，因此称由顶点集和弧集构成的图为有向图。由顶点集和弧集构成的图为有向图。 例如：例如：G1 = (V1, VR1) V1=A, B, C, D, E VR1=, , , , , , , ABCDE弧头弧头Initial Node弧尾弧尾Terminal Node 若若 VR 必有必有 VR, 则称则称 (v,w) 为顶点为顶点v 和顶点和顶点 w 之间存在一条之间存在一条“边边(ed

3、ge)”。 由顶点集和边集构成的图称作由顶点集和边集构成的图称作无向图无向图(Undiagrah)。例如：例如：G1 = (V1, VR1)V1=A, B, C, D, EVR1=, , , , , , ABCDE 1)网网(Network) 弧或边带权弧或边带权(Weight)的图分别称的图分别称有向网有向网和和无向网无向网ABCDE134142390661 2)子图子图 G=(V ,VR ) ，G =(V ,VR ),且且 VV, VRVR,则称则称 G 为为 G 的的子图子图(Subgraph)AABACD 假设图中有假设图中有 n 个顶点，个顶点，e 条边，则条边，则 3) 含有含有e

4、=n(n-1)/2 条边的条边的无向图无向图称作称作完全图完全图(Completed graph) 4) 含有含有e=n(n-1) 条弧的条弧的有向图有向图称作称作 有向完全图有向完全图 5) 若边或弧的个数若边或弧的个数 enlogn，则称作，则称作稀疏图稀疏图(Sparse graph)，否则称作否则称作稠密图稠密图(Dense graph).BADEC 6）假若顶点）假若顶点v 和顶点和顶点w 之间存在一条边，则称顶点之间存在一条边，则称顶点v 和和w 互为互为邻接点邻接点。 边边(v,w) 和顶点和顶点v 和和w 相相关联关联 7 7）和顶点）和顶点v 关联的边的数目定义为顶点的关联的

5、边的数目定义为顶点的度度 出度、入度出度、入度BADECBADEC 8) 从顶点从顶点u 到顶点到顶点w 之间存在一条之间存在一条路径路径(Path)，当，当 u=vi,0,vi,1, , vi,m=w中中， VR 1jm 路径上边的数目称作路径上边的数目称作路径长度路径长度 简单路径简单路径:序列中顶点不重复出现的路径序列中顶点不重复出现的路径 简单回路简单回路(Cycle):序列中第一个顶点和最后一个顶点序列中第一个顶点和最后一个顶点相同的路径相同的路径BADEC 9)若图若图G中任意两个顶点之间都有路径相通，则称此中任意两个顶点之间都有路径相通，则称此图为图为连通图连通图(Connect

6、ed graph)； 若无向图为非连通图，则图中各个极大连通子图称若无向图为非连通图，则图中各个极大连通子图称作此图的作此图的连通分量连通分量(Connected component);BADECBADEC 对有向图，若任意两个顶点之间都存在一条有向路对有向图，若任意两个顶点之间都存在一条有向路径，则称此有向图为径，则称此有向图为强连通图强连通图 否则，其各个强连通子图称作它的否则，其各个强连通子图称作它的强连通分量强连通分量ABCDEBADEC 结构的建立和销毁结构的建立和销毁 对顶点的访问操作对顶点的访问操作 对邻接点的操作对邻接点的操作 插入或删除顶点插入或删除顶点 插入和删除弧插入和删

7、除弧 遍历遍历 CreatGraph(&G, V, VR): 按定义按定义(V, VR) 构造图构造图 DestroyGraph(&G): 销毁图销毁图 LocateVex(G, u); 若若G中存在顶点中存在顶点u，则返回该顶点在图中，则返回该顶点在图中“位置位置” ； 否则返回其它信息否则返回其它信息 GetVex(G, v); 返回返回 v 的值的值 PutVex(&G, v, value); 对对 v 赋值赋值value FirstAdjVex(G, v); 返回返回 v 的的“第一个邻接点第一个邻接点” 。 若该顶点在若该顶点在 G 中没有邻接点，则返回中没有

8、邻接点，则返回“空空” NextAdjVex(G, v, w); 返回返回 v 的（相对于的（相对于 w 的）的） “下一个邻接点下一个邻接点”。 若若 w 是是 v 的最后一个邻接点，则返回的最后一个邻接点，则返回“空空”。 InsertVex(&G, v); 在图在图G中增添新顶点中增添新顶点v DeleteVex(&G, v); 删除删除G中顶点中顶点v及其相关的弧及其相关的弧 DeleteVex(&G, v); 删除删除G中顶点中顶点v及其相关的弧及其相关的弧 DeleteArc(&G, v, w); 在在G中删除弧中删除弧 若若G是无向的，则还删除对称

9、弧是无向的，则还删除对称弧 DFSTraverse(G, v, Visit(); 从顶点从顶点v起起深度优先深度优先遍历图遍历图G 并对每个顶点调用函数并对每个顶点调用函数Visit一次且仅一次一次且仅一次 BFSTraverse(G, v, Visit(); 从顶点从顶点v起起广度优先广度优先遍历图遍历图G， 并对每个顶点调用函数并对每个顶点调用函数Visit一次且仅一次一次且仅一次 7.2.1 图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示 7.2.2 图的邻接表存储表示图的邻接表存储表示 7.2.3 有向图的十字链表存储表示有向图的十字链表存储表示 7.2.4 无向图的邻接多重表存

10、储表示无向图的邻接多重表存储表示 定义定义:矩阵的元素为矩阵的元素为BACDFEVRjiVRjiAij),( 1),(0顶点顶点i 的度？的度？第第 i 行行 (列列) 1 的个数。的个数。有向图的邻接矩阵为非对称矩阵有向图的邻接矩阵为非对称矩阵ABECD0 1 0 0 10 0 1 0 00 0 0 1 01 1 0 0 00 0 1 0 0typedef struct ArcCell / 弧的定义弧的定义 VRType adj; / VRType是顶点关系类型。是顶点关系类型。 / 对无权图，用对无权图，用1或或0表示相邻否；表示相邻否； / 对带权图，则为权值类型。对带权图，则为权值类型

11、。 InfoType *info; / 该弧相关信息的指针该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;typedef struct / 图的定义图的定义 VertexType / 顶点信息顶点信息 vexsMAX_VERTEX_NUM; AdjMatrix arcs; / 弧的信息弧的信息 int vexnum, arcnum; / 顶点数，弧数顶点数，弧数 GraphKind kind; / 图的种类标志图的种类标志 MGraph;BACDFE0A1B2C3D4E5F14045352501123顶点顶点i 的度？的度？顶

12、点顶点 i 边表长度边表长度无向图的邻接表无向图的邻接表共有多少边节点？共有多少边节点？2e。ABECD0A1B2C3D4E14201有向图的邻接表有向图的邻接表32出边表出边表顶点顶点 i 的出度的出度?顶点顶点 i 的出边表长度的出边表长度共有多少边节点？共有多少边节点？e。ABECD有向图的逆邻接表有向图的逆邻接表30240入边表入边表0A1B2C3D4E3顶点顶点 i 的入度的入度?顶点顶点 i 的入边表长度的入边表长度共有多少边节点？共有多少边节点？e。adjvex nextarc info弧的结点结构弧的结点结构typedef struct ArcNode int adjvex;

13、/ 该弧所指向的顶点的位置该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针该弧相关信息的指针 ArcNode;顶点顶点的结点结构的结点结构 data firstarctypedef struct VNode VertexType data; / 顶点信息顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM;图的图的结构定义结构定义typedef struct AdjLi

14、st vertices;/顶点列表顶点列表 int vexnum, arcnum; /顶点数，边数顶点数，边数 int kind; / 图的种类标志图的种类标志 ALGraph;vertices vexnumarcnumkindTypedef enum DG, DN, UDG, UDN Graphkind;ALGraph G;vertices vexnumarcnumkinddatafirstarc0A1B2C3D4E5FGadjvex-1infonextarc4 infonull0 info5 info4 infonullBACDFEV1V2V3V4v1v2v3v42001023132302

15、30123如何求顶点如何求顶点 i 的入度的入度?如何求如何求顶点顶点 i 的出度的出度?tailvex headvex hlinktlinkinfodatafirstin firstout弧的结点结构弧的结点结构弧尾顶点位置弧尾顶点位置 弧头顶点位置弧头顶点位置 弧的相关信息弧的相关信息指向下一个有相有相同弧尾同弧尾的结点指向下一个有相有相同弧头同弧头的结点typedef struct ArcBox / 弧弧的结构表示的结构表示 int tailvex, headvex; InfoType *info; struct ArcBox *hlink, *tlink; VexNode;顶点的结点结

16、构顶点的结点结构顶点信息数据顶点信息数据 指向该顶点的第一条入弧第一条入弧指向该顶点的第一条出弧第一条出弧typedef struct VexNode / 顶点的结构表示顶点的结构表示 VertexType data; ArcBox *firstin, *firstout; VexNode;typedef struct VexNode xlistMAX_VERTEX_NUM; / 顶点结点顶点结点(表头向量表头向量) int vexnum, arcnum; /有向图的当前顶点数和弧数有向图的当前顶点数和弧数 OLGraph;有向图的结构表示有向图的结构表示(十字链表十字链表)V1V2V4V5V

17、30V11V22V33V44V5010321234124mark ivex ilink jvex jlink info顶点顶点 i 的度的度?多少边节点多少边节点?typedef struct Ebox VisitIf mark; / 访问标记访问标记 int ivex, jvex; /该边依附的两个顶点的位置该边依附的两个顶点的位置 struct EBox *ilink, *jlink; InfoType *info; / 该边信息指针该边信息指针 EBox;边的结构表示边的结构表示mark ivex ilink jvex jlink infotypedef struct / 邻接多重表邻接

18、多重表 VexBox adjmulistMAX_VERTEX_NUM; int vexnum, edgenum; AMLGraph;顶点的结构表示顶点的结构表示typedef struct VexBox VertexType data; EBox *firstedge; / 指向第一条依附的边指向第一条依附的边 VexBox;无向图的结构表示无向图的结构表示 图的遍历：从图中某个顶点出发游历图，访遍图中图的遍历：从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的其余顶点，并且使图中的每个顶点仅被访问一次的过程过程 由于图中可能有环，所以设置数组由于图中可能有环，所以

19、设置数组visited0,n 7.3.1 深度优先搜索深度优先搜索 7.3.2 广度优先搜索广度优先搜索 7.3.3 遍历应用举例遍历应用举例 连通图的遍历连通图的遍历 深度优先遍历连通图的过程类似于树的先根遍历深度优先遍历连通图的过程类似于树的先根遍历 从图中某个顶点从图中某个顶点V 出发，访问此顶点，然后出发，访问此顶点，然后依次从依次从V的各个未被访问的邻接点出发深度优先搜索遍历图的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和直至图中所有和V有路径相通的顶点都被访问到有路径相通的顶点都被访问到V1V2V3V4V5V6V7V8访问顶点访问顶点 V ：for (W1、W2、W3

20、 ) 若若该邻接点该邻接点Wi未被访问未被访问， 则则从它出发进行深度优先搜索遍历。从它出发进行深度优先搜索遍历。Vw1SG1SG2SG3w2w3w2void DFS(Graph G, int v, void (* visit)(VertexType) / 从顶点从顶点v出发，出发，深度优先搜索遍历连通图深度优先搜索遍历连通图 G / DFSvisitedv = TRUE; visit(v);for(w=FirstAdjVex(G, v); w!=-1; w=NextAdjVex(G,v,w) / 对对v的尚未访问的邻接顶点的尚未访问的邻接顶点w，递归调用递归调用DFS if (!visite

21、dw) DFS(G, w, visit); 非连通图的深度优先搜索遍历非连通图的深度优先搜索遍历 1) 将图中每个顶点的访问标志设为将图中每个顶点的访问标志设为 FALSE 2) 搜索图中每个顶点，如果未被访问，则以该顶点搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历为起始点，进行深度优先搜索遍历 否则继续检查下一顶点否则继续检查下一顶点void DFSTraverse(Graph G, void (*visit)(VertexType) / 对图对图 G 作深度优先遍历。作深度优先遍历。 / DFSTraversefor (v=0; vG.vexnum; +v) /

22、初始化标志数组初始化标志数组 visitedv = FALSE; / 对尚未访问的顶点调用对尚未访问的顶点调用DFSfor (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v, visit);v0v1v2v6v3v4v7v5v80263 574 18访问次序访问次序: : 类似树的广度优先遍历类似树的广度优先遍历 图中某顶点图中某顶点v出发：出发： 1）访问顶点）访问顶点v ； 2）访问）访问v所有未被访问的邻接点所有未被访问的邻接点w1,w2,wk； 3）依次从这些邻接点出发，访问其所有未被访问）依次从这些邻接点出发，访问其所有未被访问的邻接点。的邻接点

23、。 依此类推，直到图中所有访问过的顶点依此类推，直到图中所有访问过的顶点的邻接点都被访问的邻接点都被访问 借用队列暂存节点借用队列暂存节点V1V2V3V4V5V6V7V8void BFS(Graph G, VexIndex v, void (*visit)(VertexType) ) /从第从第v个顶点出发，广度优先遍历个顶点出发，广度优先遍历G,使用辅助队列使用辅助队列Q。 InitQueue(Q); /建空队列建空队列Q EnQueue(Q,v) /访问访问v,v入队入队/BFSwhile(!QueueEmpty(Q) DeQueue(Q,u); /队头元素出队队头元素出队,并赋值给并赋值

24、给u visit(u) ;visitedu=TRUE; /访问访问u for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w) if(!visitedw) EnQueue(Q,w); /whileQV1V1V2V2V3V3V4V4V8V8V5V5V6V6V7V7V2V2 V3V3 V4V4V1V1V8V8 V5V5 V6V6 V7V7 V1V1 V8V8 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2入队列入队列出出队队列列void BFSTraverse(Graph G, void (*visit)(VertexType) / 对图对图 G 作深度

25、优先遍历。作深度优先遍历。/ BFSTraversefor (v=0; vG.vexnum; +v) visitedv = FALSE; / 访问标志数组初始化访问标志数组初始化/ 对尚未访问的顶点调用对尚未访问的顶点调用DFSfor (v=0; vG.vexnum; +v) if (!visitedv) BFS(G, v, visit); 求一条从顶点求一条从顶点 i 到顶点到顶点 s 的简单路径的简单路径Status DFSearch(Graph G, VertexType v, VertexType s, SqList &PATH) /从从v开始深度优先搜索，找到开始深度优先搜索，找到s为止为止 v1 = LocateVex(G, v);/找到找到v if ( v1 = -1) return FALSE; for (i=0; iG.vexnum; +i) visitedi = FALSE; / 访问标志数组初始化访问标志数组初始化 InitList_Sq(PATH); return _DFSearch(G, v1