《数据结构》课件第7章 图

1、第7章 图学习要点: 熟悉图的各种存储结构及其构造算法了解实际问题的求解效率与采用何种存储结构和算法的密切联系熟练掌握图的两种搜索路径的遍历：深度优先搜索和广度优先搜索应用图的遍历算法求解各种简单路径问题，如关键路径、最短路径等7.1 图的定义和基本术语7.1.1 图的定义图形结构：较线性表和树更为复杂的数据结构。结点之间的关系是任意的，图中任意两个数据元素都可能相关。图的结构定义：图：是由一个顶点集 V 和一个顶点间的关系集合组成的数据结构。Graph = (V , VR)其中，V = x | x 某个数据对象，是顶点的有穷非空集合；VR = (x, y) | x, y V 或 VR = |

2、 x, y V & Path (x, y) 是顶点之间关系的有穷集合，也叫做边(edge)或弧(Arc)集合。Path (x, y)表示从 x 到 y 的一条单向通路, 它是有方向的。“弧”是有方向的，称由顶点集和弧集构成的图为有向图。例如：G1 = (V1, VR1)是一个有向图。EACBD其中V1=A, B, C, D, EVR1=, , , , 弧尾弧头若VR 必有VR, 则称 (v,w) 为顶点v 和顶点 w 之间存在一条边。由顶点集和边集构成的图称作无向图。 例如： G2=(V2,VR2) 其中，V2=A, B, C, D, E, F VR2=, , , , , , B CA D F

3、 E抽象数据类型定义：ADT Graph 数据对象V：V是顶点集。 数据关系R：R=VR， VR=| v, wV且P(v, w)， 表示从v到w的弧，谓词P(v, w)定义了弧 的意义或信息 基本操作P：结构的建立和销毁对顶点的访问操作插入或删除顶点插入和删除对邻接点的操作遍历ADT Graph7.1.2 基本术语有(无)向网：弧(边)上带权的图。子图：设图G=(V,VR) 和图 G=(V,VR),且 VV, VRVR，则称 G 为 G 的子图。ABECF1597211132AEFBBC假设图中有n个顶点，e条边，则含有 e=n(n-1)/2条边的无向图称作完全图；含有 e=n(n-1)条弧的

4、有向图称作有向完全图；若边或弧的个数 enlogn，则称作稀疏图，否则称作稠密图。假若顶点v和顶点w之间存在一条边，则称顶点v和w互为邻接点；边(v,w)和顶点v及w相关联；和顶点v关联的边的数目定义为顶点的度(TD)。例如： TD(A) = 2 TD(B) = 3ACDFEB对有向图来说，顶点的出度(OD): 以顶点v为弧尾的弧的数目；顶点的入度(ID): 以顶点v为弧头的弧的数目。顶点的度(TD)=出度(OD)+入度(ID)例如：OD(B) = 1 ID(B) = 2 TD(B) = 3设图G=(V,VR)中的一个顶点序列 u=vi,0,vi,1, , vi,m=w中，(vi,j-1,vi

5、,j)VR，1jm，则称从顶点u 到顶点w 之间存在一条路径。ABECF有n个顶点，e条边或弧的图，满足：路径上边的数目称作路径长度。例如：从A到F且长度为3的路径为： A,B,C,F，A,E,C,F简单路径：序列中顶点不重复出现 的路径。简单回路：序列中只有第一个顶点和最后 一个顶点相同的回路。如，A,B,C,F,A若图G中任意两个顶点之间都有路径相通，则称此图为连通图；若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。ABECF对有向图来说，若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。否则，其各个强连通子图称作它的强连通分量。BACDFEBACDFEABECF

6、ABECF假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。对非连通图，则称各个连通分量的生成树的集合为此非连通图的生成森林。BACDFEABEFCDABECDF比较：连通分量和生成树！非连通图的极大连通子图连通图的极小连通子图7.2.1 图的数组(邻接矩阵)存储表示邻接矩阵 (Adjacency Matrix)顶点信息：记录各个顶点信息的顶点表。边或弧信息：各个顶点之间关系的邻接矩阵。设图 A = (V, E)是一个有 n 个顶点的图，则图的邻接矩阵是一个二维数组 A.edgenn，定义：无向图的邻接矩阵是对称

7、的，有向图的邻接矩阵可能是不对称的。7.2 图的存储结构无向图：有向图：BACDFEABECFABCDEF012345ABCDE01234C语言形式描述：typedef enumDG, DN, UDG, UDN GraphKind;typedef struct ArcCell / 边/弧的定义 VRType adj; / VRType是顶点关系类型。 / 对无权图，用1或0表示相邻否；对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针ArcCell, AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;typedef struct / 图

8、的定义 VertexType vexsMAX_VERTEX_NUM; / 顶点信息 AdjMatrix arcs; / 边/弧的信息 (关系的邻接矩阵) int vexnum, arcnum; / 顶点数，边/弧数 GraphKind kind; / 图的种类标志 MGraph;借助于邻接矩阵容易求得顶点的度：在无向图中,统计第i行(列)1的个数可得顶点i的度。即：在有向图中统计第i行1的个数可得顶点i的出度;统计第j列1的个数可得顶点j的入度。TD(v1)=2TD(v6)=3OD(v1)=2ID(v1)=1则，TD(v1)=2+1=3网的邻接矩阵：Status createUDN(Mgrap

9、h &G) /采用邻接矩阵表示法, 构造无向网 scanf(&G.vexnum,&G.arcnum,&IncInfo); /读入顶点数、边 /数和相关信息 for (i=0;iG.vexnum;+i scanf(&G.vexsi); /构造顶点表 for (i=0;iG.vexnum;+i) for (j=0;jG.vexnum;+j) G.arcsij=INFINITY,NULL; /初始化邻接矩阵 for (k=0;kG.arcnum;+k) /构造邻接矩阵 Sacnf(&v1,&v2,&w); /输入一条边依附的顶点及权值 i=LocateVex(G, v1); j=LocateVex(

10、G, v2); /确定v1和v2在G中的位置 G.arcsij.adj=w; /弧的权值 If (IncInfo) Input(*G.); G.arcsji=G.arcsij; /置对称弧 Return OK;7.2.2 图的邻接表存储表示只存储图中已有的弧或边的信息：对图中的每个顶点都建立一个单链表来存储所有依附于该顶点的弧或边。无向图：第i个单链表中的结点表示依附于顶点vi的边。有向图：第i个单链表中的结点表示以顶点vi为尾的弧。对图中所有顶点使用一个一维数组来存放单链表中每个结点由三个域组成邻接点域(adjvex):指示与顶点vi邻接的点在图中的位置；链域(next

11、arc):指示下一条边或弧的结点；数据域(info):存储和边或弧相关的信息，如权值等。C语言类型描述：表(弧/边)结点：typedef struct ArcNode int adjvex; / 依附于该边的另一顶点(弧头)的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针 ArcNode;头结点：typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM

12、;adjvex nextarc info data firstarc图的结构定义：typedef struct AdjList vertices; int vexnum, arcnum; int kind; / 图的种类标志 ALGraph;0 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3BACDFE链表中结点的个数就是该顶点的度数！有向图：ABECD1 4230 120 1 2 3 4 A B C D E在有向图的邻接表中不易找到指向该顶点的弧。A B C D E 30342001234有向图的逆邻接表链表中结点的个数就是该顶点的 出度！7.2.3

13、 有向图的十字链表存储表示将有向图的邻接表和逆邻接表结合起来的一种链表。从横向上看是邻接表，从纵向上看是逆邻接表。ABCABC0 1 20 2 0 12 1 2 0 C语言类型描述：typedef struct ArcBox / 弧的结构表示 int tailvex, headvex; InfoType *info; struct ArcBox *hlink, *tlink; VexNode;弧的结点结构弧尾顶点位置 弧头顶点位置 弧的相关信息指向下一个有相同弧尾的结点指向下一个有相同弧头的结点typedef struct VexNode / 顶点的结构表示 VertexType data;

14、ArcBox *firstin, *firstout; VexNode;顶点的结点结构顶点信息数据 指向该顶点的第一条入弧指向该顶点的第一条出弧datafirstinfirstout有向图的结构表示(十字链表)：typedef struct VexNode xlistMAX_VERTEX_NUM; / 顶点结点(表头向量) int vexnum, arcnum; /有向图的当前顶点数和弧数 OLGraph;只要输入n个顶点的信息和e条弧的信息，便可建立该有向图的十字链表。Status CreateDG(OLGraph &G) /采用十字链表存储表示，构造有向图G（G.kind=DG). sca

15、nf(&G.vexnum,&G.arcnum,&IncInfo); /IncInfo为0则各弧不含其它信息。 for (I=0;IG.vexnum;+I) /构造表头向量 scanf(&G.xlistI.data); /输入顶点值 G.xlistI.firstin=NULL;G.xlistI.firstout=NULL; /初始化指针 for (k=0;kinfo); /若弧含有相关信息，则输入特点：容易求得顶点的出度和入度。建立十字链表的时间复杂度和建立邻接表是相同的。7.2.4 无向图的邻接多重表存储表示为了便于在搜索无向图的过程中对边进行操作，常采用无向图的邻接多重表作为存储结构。边的结

16、点结构：typedef struct Ebox VisitIf mark; / 访问标记 int ivex, jvex; /该边依附的两个顶点的位置 struct EBox *ilink, *jlink; InfoType *info; / 该边信息指针 EBox;Mark ivex ilink jvex jlink info顶点的结构表示：typedef struct VexBox VertexType data; EBox *firstedge; / 指向第一条依附该顶点的边 VexBox;无向图的结构表示：typedef struct / 邻接多重表 VexBox adjmulistMA

17、X_VERTEX_NUM; int vexnum, edgenum; AMLGraph;邻接多重表和邻接表的差别：同一条边在邻接表中用两个结点表示；在邻接多重表中只用一个结点。7.3 图的遍历从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。7.3.1 深度优先搜索连通图的深度优先搜索遍历： 从图中某个顶点v0出发，访问此顶点，然后依次从v0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v0有路径相通的顶点都被访问到。以某个顶点的邻接顶点数作为循环控制例如：W1、W2和W3均为V的邻接点，SG1、SG2和 SG3分别为含顶点W1、W2和W3的子图

18、。访问顶点 V; for (W1、W2、W3 ) 若该邻接点W未被访问， 则从它出发进行深度 优先搜索遍历。可见：深度优先搜索遍历连通图的过程类似于树的先根遍历；如何判别V的邻接点是否被访问？ 解决的办法是：为每个顶点设立一个“访问标志 visitedw”。Vw1SG1SG2SG3w2w3w2算法描述：void DFS(Graph G, int v) / 从顶点v出发，深度优先搜索遍历连通图 G visitedv = TRUE; VisitFunc(v); for(w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS

19、(G, w); / 对v的尚未访问的邻接顶点w递归调用DFS / DFS非连通图的深度优先搜索遍历： 首先，将图中每个顶点的访问标志设为 FALSE；然后，搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。算法描述：void DFSTraverse(Graph G, Status (*Visit)(int v) / 对非连通图 G 作深度优先遍历。 VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = FALSE; / 访问标志数组初始化 for (v=0; vw1, V-w2, V-w8 的

20、路径长度为1;V-w7, V-w3, V-w5 的路径长度为2;V-w6, V-w4 的路径长度为3。w1Vw2w7w6w3w8w5w4广度优先遍历图的实质：通过边或弧找邻接点的过程！ 从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。算法描述：void BFSTraverse(Graph G, Status (*Visit)(int v) for (v=0; vG.vexnum; +v) visitedv = FALSE; /初始化访问标志 InitQueue(Q

21、); / 置空的辅助队列Q for ( v=0; vG.vexnum; +v ) if ( !visitedv) / v 尚未访问 . / BFSTraverse说明：使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，因此，采用队列来存放已被访问过的顶点！visitedv = TRUE; Visit(v); / 访问vEnQueue(Q, v); / v入队列while (!QueueEmpty(Q) DeQueue(Q, u); / 队头元素出队并置为u for(w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G,u,w) if ( ! vis

22、itedw) visitedw=TRUE; Visit(w); EnQueue(Q, w); / 访问的顶点w入队列 / if / while课后作业P47：7.32. 假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到v的长度为1的所有简单路径。7.4 图的连通性问题7.4.1 无向图的连通分量和生成树对非连通图的遍历，需从多个顶点出发进行搜索。而每一次从一个新顶点出发搜索得到的顶点序列就是图的各个连通分量中的顶点集。例如：非连通图G3如下ABLMCFIDEGHJK按照P171图7.14所示的邻接表进行深度优先搜索：第一次调用DFS函数从A出发，得到序列： ALMJBFC第二次调用D

23、FS函数从D出发，得到序列： DE第三次调用DFS函数从G出发，得到序列： GKHIG3的三个连通分量：ABLMCFJIDEGHKABLMCFJIDEGHK以孩子兄弟链表作生成森林的存储结构，则可以形成非连通图的生成森林。void DFSForest(MGraph g, CSTree &T)/建立无向图G的深度优先生成森林的(最左)孩子(右)兄弟链表T。T = NULL;for(v = 0; v g.vexNum; v+)visitedv = FALSE;q = T;for(v=0; v data = GetVex(g, v); /给该结点赋值p-firstChild = NULL;p-nex

24、tSibling = NULL;if(!p) T = p; /是第一棵生成树的根(T的根)else q-nextSibling = p; /是其它生成树的根(前一棵的根的“兄弟”)q = p; /q指示当前生成树的根DFSTree(g, v, p); /建立以p为根的生成树void DFSTree(MGraph g, int v, CSTree *T) /从第V个顶点出发深度优先遍历图G,建立以T为根的生成树。visitedv = TRUE;first = TRUE; q = T;for(w = FirstAdjVex(g, v); w!=-1; w = NextAdjVex(g, v, w)

25、if(!visitedw). /* if */* for */p = (CSTree)malloc(sizeof(CSNode);p-data = GetVex(g, w);p-firstChild = NULL;p-nextSibling = NULL;if(first) /W是V的第一个未被访问的邻接顶点(*T)-firstChild = p; /是根的左孩子结点first = FALSE;else /W是V的其它未被访问的邻接顶点 q-nextSibling = p;q = p;DFSTree(g, w, q);/从第W个顶点出发深度优先遍历图G，建立子生成树q。对连通图进行搜索时，搜索

26、过程中经历的所有边和图中所有的顶点构成了连通图的一个极小连通子图，即连通图的生成树。深度优先生成树：广度优先生成树：134251342513425生成树的特点：n个顶点的连通子图的生成树是一个极小连通子图，它包含图中所有顶点和n-1条边(但有n-1条边的图不一定是生成树)。生成树中任意两个顶点间的路径是唯一的。注：边数n-1时，则形成环；边数n-1时则不连通。对于非连通图，其中的每一个连通分量都可以通过遍历得到一棵生成树，所有这些连通分量的生成树就构成了非连通图的生成森林。7.4.2 有向图的强连通分量深度优先搜索求有向图G的强连通分量步骤：在G上，从某个顶点出发沿以该顶点为尾的弧进行深度优先

27、搜索遍历，并按其所有邻接点的搜索都完成的顺序将顶点排列起来。对DFSTraverse函数修改：在入口处加上count=0；在结束之前加上finished+count=v。在G上，从最后完成搜索的顶点(即finishedvexnum-1中的顶点)出发，沿着以该顶点为头的弧做逆向的深度优先搜索遍历，直至有向图中所有顶点都被访问为止。对DFSTraverse修改：第二个循环语句的边界条件改为v从finishedvexnum-1至finished0。则，每一次调用DFS作逆向深度优先遍历所访问到的顶点集就是有向图G中一个强连通分量的顶点集。例如：V1V2V3V4V1V2V3V4010220233031

28、320123finished：13201230 1 2 323V1：v1, v3, v4V2：v27.4.3 最小生成树问题： 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？该问题等价于： 构造网的一棵最小生成树，即：在e条带权的边中选取n-1条边(不构成回路)，使“权值之和”为最小。最小生成树(MST)性质： 假设N(V,E)是一个连通网，U是顶点集V的一个非空子集，若(u,v)是一条具有最小权值的边，其中uU, vV-U,则必存在一棵包含边(u,v)的最小生成树。普里姆算法：基本思想：第一步：取图中任意一个顶点

29、v 作为生成树的根；第二步：往生成树上添加新的顶点w。顶点w和已经在生成树上的顶点v之间必定存在一条边，并且该边的权值在所有连通顶点v和w之间的边中取值最小；第三步：继续往生成树上添加顶点，直至生成树上含有 n 个顶点为止。MST性质例如：abcdegf195141827168213127aedcbgf148531621所得生成树权值和= 14+8+3+5+16+21 = 67图解构造算法：123456123456165123456165575412345615554626515754263U=1, V-U=2, 3, 4, 5, 6U=1, 3, V-U=2, 4, 5, 6U=1, 3,

30、6, V-U=2, 4, 5123456155546212345615546212345615546212345615546233U=1, 3, 6, V-U=2, 4, 5U=1, 3, 6, 4, V-U=2, 5U=1, 3, 6, 4, 5, V-U=2U=1, 3, 6, 4, 2, V-U=5由上述图解算法的过程知，构造的最小生成树不一定唯一，但最小生成树的权值之和一定是相同的。12345615421234561542331234566515754263添加的顶点应满足下列条件：在生成树的构造过程中，图中n个顶点分属两个集合：已落在生成树上的顶点集 U；尚未落在生成树上的顶点集V-U。应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。UV-U设置一个辅助数组closedge，对当前V-U集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边：struct VertexType adjvex; / U集中的顶点序号 VRType l