《数据结构chap7》由会员分享，可在线阅读，更多相关《数据结构chap7（116页珍藏版）》请在金锄头文库上搜索。
1、 7.1 抽象数据类型图的定义7.2 图的存储表示7.3 图的遍历7.4 最小生成树 7.5 重（双）连通图和关节点7.5 两点之间的最短路径问题7.6 拓扑排序7.7 关键路径图是由一个顶点集 V 和一个弧集 R构成的数据结构。Graph = (V, R ) 其中，VR| v,wV 且 P(v,w)表示从 v 到 w 的一条弧，并称 v 为 弧头，w 为弧尾。谓词 P(v,w) 定义了弧 的意义或信息。图的结构定义:由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。EACBD例如:G1 = (V1, VR1)其中 V1=A, B, C, D, E VR1=, , , , 若VR 必
2、有VR, 则称 (v,w) 为顶点 v 和顶点 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) 名词和术语网、子图 完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、简单路径、简单回路连通图、连通分量、 强连通图、强连通分量生成树、生成森林ABECFB BC设图G=(V,VR) 和 图 G=(V,VR), 且 VV, VRVR, 则称 G 为 G 的子图。159721113 2弧或
3、边带权的图分别称作“有向网” 或“无向网” 。AEFC假设图中有 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
4、.2 图的存储表示一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示Aij=0 (i,j)VR1 (i,j)VR一、图的数组(邻接矩阵)存储表示BACDFE定义:矩阵的元素为0 A 1B 2 C 3 D 4E 5F有向图的邻接矩阵 为非对称矩阵ABECF0A 1B2C 3F 4Etypedef struct ArcCell / 弧的定义VRType adj; / VRType是顶点关系类型。/ 对无权图，用1或0表示相邻否；/ 对带权图，则为权值类型。InfoType *info; / 该弧相关信息的指针 ArcCell, Adj
5、MatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct / 图的定义VertexType / 顶点信息vexsMAX_VERTEX_NUM; 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 4ABCFEABECF可见，在有向图的邻接表中不易找到指向该顶点的弧ABE
6、CD有向图的逆邻接表在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧A B C D E 303420012341typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置struct ArcNode *nextarc; / 指向下一条弧的指针int weight; / 权值，图的权值为0InfoType *info; / 该弧相关信息的指针 ArcNode;adjvex nextarc info弧的结点结构typedef struct VNode VertexType data; / 顶点信息ArcNode *firstarc; / 指向第一条依附该
7、顶点的弧 VNode, AdjListMAX_VERTEX_NUM;data 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; InfoTyp
8、e *info;struct ArcBox *hlink, *tlink; VexNode;tailvexheadvexhlink tlinkinfo顶点的结点结构顶点信息数据 指向该顶点的 第一条入弧指向该顶点的 第一条出弧typedef struct VexNode / 顶点的结构表示VertexType data;ArcBox *firstin, *firstout; VexNode;datafirstinfirstouttypedef struct VexNode xlistMAX_VERTEX_NUM; / 顶点结点(表头向量) int vexnum, arcnum;/有向图的当前顶
9、点数和弧数 OLGraph;有向图的结构表示(十字链表)ABCDA B C D0 12 10 20 33 1四、无向图的邻接多重表存储表示typedef struct Ebox VisitIf mark; / 访问标记int ivex, jvex;/该边依附的两个顶点的位置struct EBox *ilink, *jlink; InfoType *info; / 该边信息指针 EBox;边的结构表示typedef struct / 邻接多重表VexBox adjmulistMAX_VERTEX_NUM;int vexnum, edgenum; AMLGraph;顶点的结构表示typedef s
10、truct VexBox VertexType data;EBox *firstedge; / 指向第一条依附该顶点的边 VexBox;无向图的结构表示7.3 图的遍历对图中的每个顶点进行一次访问且使每个顶点仅被访问一次的过程。深度优先搜索广度优先搜索从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。一、深度优先搜索遍历图连通图的深度优先搜索遍历V0w1w3w2w4w5w6w8w7w10w9w11G1G2G3V0w1w3w2SG1SG2SG3W1、W2和W3 均为 V 的邻接点，SG1、SG2 和 S
11、G3 分别为含顶点 W1、W2和W3 的子图。访问顶点 V ; for (W1、W2、W3 )若该邻接点W未被访问，则从它出发进行深度优先搜索遍历。Vw1w3w2从上页的图解可见:1. 从深度优先搜索遍历连通图的过 程类似于树的先根遍历;解决的办法是:为每个顶点设立一个 “访问标志 visitedw”;2. 如何判别V的邻接点是否被访问？void DFS(Graph G, int v) / 从顶点v出发，深度优先搜索遍历连通图 Gvisitedv = TRUE; VisitFunc(v);for(w=FirstAdjVex(G, v);w!=0; w=NextAdjVex(G,v,w)if (
12、!visitedw) DFS(G, w); / 对v的尚未访问的邻接顶点w/ 递归调用DFS / DFS首先将图中每个顶点的访问标志设为 FALSE, 之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。非连通图的深度优先搜索遍历void DFSTraverse(Graph G, Status (*Visit)(int v) / 对图 G 作深度优先遍历。VisitFunc = Visit; for (v=0; vw1, V-w2, V-w8 的路径长度为1; V-w7, V-w3, V-w5的路径长度为2; V-w6, V-w4 的路径长度为3
13、。Vw8w7w6w1w2w3w4w5Vw1w2w8w7w3w5w6w4从图中的某个顶点V0出发，并在访问此 顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次 序依次访问它们的邻接点，直至图中所有 和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复 上述过程，直至图中所有顶点都被访问到 为止。void BFSTraverse(Graph G,Status (*Visit)(int v)for (v=0; vnext = Q.rear-next = NULL; void EnQueue( LinkQueuep-dat
14、a = e; p-next = NULL;p-priou = Q.front;Q.rear-next = p; Q.rear = p; void DeQueue( LinkQueue e = Q.front-data 7.4 (连通网的)最小生成树假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？问题：构造网的一棵最小生成树，即： 在 e 条带权的边中选取 n-1 条边（不构成 回路），使“权值之和”为最小。算法二：（克鲁斯卡尔算法）该问题等价于：算法一：（普里姆算法）取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。普里姆算法的基本思想:abcdegf195 14 182716821312 7例如:aedcbgf148531621所得生成树权值和 = 14+8+3+5+16+21 = 67在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的 顶点集
