数据结构-图1

1、2021/8/61第七章 图 图形结构是一种比树形结构更复杂的非线性结构。在图形结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。就是说，图是一种多对多的结构关系，就是说，图是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个每个元素可以有零个或多个直接前趋；零个或多个直接后继。或多个直接后继。因此图形结构被用于描述各种复杂的数据对象。应用领域非常广泛。2021/8/62 内容提要内容提要 图的概念图的存储结构图的遍历方法求生成树找最短路径关键路径拓扑排序 2021/8/637.1图的定义与术语图的定义与术语l图（图（graph） 图是一种数据结构，它的形式化定义

2、为G=(V，E)，其中：V是一个非空有限集合，它的元素称为顶点(vertex)。顶点的偶对(x，y) (xV，yV)叫做边(edge)，E是边的集合。 2021/8/64图基本术语图基本术语l有向图有向图（ digraph ）：）：若图中代表一条边的顶点偶对是有序的，记作，称x为弧尾(tail)或初始点(initial node)，称y为弧头(head)或终端点(terminal node)，表示从x到y的一条弧(arc)，此时的图称为有向图。 l无向图无向图(undigraph) ：图中代表一条边的顶点偶对(x，y)是无序的，则称其为无向图。这时(x，y)，(y，x)是同一条边。2021/8

3、/6513542(a)(b)1243G1=(V1G1=(V1，E1) E1) 其中：其中：V1=v1，v2，v3，v4E1=，G2=(V2G2=(V2，E2) E2) 其中：其中：V2=v1，v2，v3，v4，v5E2=(v1，v2)，(v1，v4)，(v2，v3)，(v2，v5)，(v3，v4)，(v3，v5) 有向图G1 (b)无向图G2 图 6.1 图的示例图基本术语图基本术语(续续)无序对无序对(v(vi i,v,vj j) )：用连接顶点用连接顶点v vi i、v vj j的线段的线段表示，称为无向边。表示，称为无向边。有序对有序对v ：以以v vi i为起点、为起点、v vj j为

4、终点的为终点的有向线段表示，称为有向有向线段表示，称为有向边或弧。边或弧。2021/8/66图基本术语图基本术语(续续)l完全图完全图(completed graph) ：对于无向图，e的取值范围是0到n(n-1)/2，有n(n-1)/2条边的无向图称为完全图。 对于有向图，e的取值范围是0到n(n-1)。具有n(n-1)条弧的有向图称为有向完全图。 l邻接点邻接点(adjacent)(adjacent)：对于无向图G=(V，E)，如果边(v，v)E，则称顶点v和v互为邻接点，即v和v相邻接。边(v，v)依附(incident)于顶点v和v，或者说边(v，v)和顶点v，v相关联。例213213

5、有向完备图无向完备图2021/8/67l度：度：顶点v的度是和v相关联的边的数目。记作TD(V)。例如G2中顶点v3的度是3。l入度：入度：有向图中，以顶点v为头的弧的数目称为v的入度，记为ID(V)；l出度：出度：有向图中，以顶点v为尾的弧的数目称为v的出度，记为OD(v)；顶点顶点v的度为：的度为： TD(v)=ID(v)+OD(v)图基本术语图基本术语(续续)例157324G26顶点5的度：3顶点2的度：4例245136G1顶点2入度：1 出度：3顶点4入度：1 出度：02021/8/68图基本术语图基本术语(续续)l子图子图(subgraph)(subgraph)： 假设有两个图G=(

6、V，E)，G=(V，E)。如果V包含于V，E包含于E，则称G是G的子图。113431314212154125313542(a)(b)(a)G1的子图 (b)G2的子图图6.2 子图示例 13542(a)(b)1243356例245136图与子图2021/8/69l路径：路径：无向图G=(V，E)中从顶点v到顶点v的路径是一个顶点序列(v=vi0，vi1，vi2，.，vin=v)，其中(vi，j-1，vij)E，1jn。如果G是有向图，则路径也是有向的，顶点序列应满足E，1jn。l路径的长度：路径的长度：是指路径上的边的或弧的数目。图基本术语图基本术语(续续)2021/8/610 回路：回路：第

7、一个顶点和最后一个顶点相同的路径称为回路或环。l简单路径：简单路径：序列中顶点不重复出现的路径称为简单路径。l简单回路：简单回路：除了第一顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。 图基本术语图基本术语(续续)2021/8/611例157324G26例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，12021/8/612l连通：连通：在无向图G中

8、， 如果从顶点v到顶点v有路径，则称v和v是连通的。 l连通图连通图：如果对于图中任意两个顶点vi，vjV，vi，vj都是连通的，则称G是连通图。（图6.1中的G2句是一个连通图） 图基本术语图基本术语(续续)2021/8/613图基本术语图基本术语(续续) 连通分量连通分量：指的是无向图中的极大连通子图。 KJIHGFEDCMLB23456789101113（a）(b)AABCFLMJEDKIHG710(a)无向图G3 (b)G3的三个连通分量 图6.3 无向图及其连通分量2021/8/614l强连通图：强连通图： 在有向图G中，如果对于每一对V，vi!=vj，从vi到vj和从vj到vi都存

9、在路径，则称G是强连通图。 l强连通分量：强连通分量：有向图中的极大强连通子图称作有向图的强连通分量。图基本术语图基本术语(续续)2021/8/6151234图6.4 G1的两个强连通分量 图基本术语图基本术语(续续)13542(a)(b)12432021/8/616连通图例245136强连通图356例非连通图连通分量例2451362021/8/617图基本术语图基本术语(续续)l生成树生成树：一个连通图的生成树是一个极小连通子图。 它含有图中全部顶点，但只有足以构成一棵树的n-1条边。KJIHGFEDCMLB23456789101113（ a）(b)AABCFLMJEDKIHG710JFCM

10、LBA图6.5 G3的最大连通分量的一棵生成树 KJIHGFEDCMLB23456789101113（ a）(b)AABCFLMJEDKIHG7102021/8/618生成树说明生成树说明n一个图可以有许多棵不同的生成树n所有生成树具有以下共同特点：u生成树的顶点个数与图的顶点个数相同u生成树是图的极小连通子图u一个有n个顶点的连通图的生成树有n-1条边u生成树中任意两个顶点间的路径是唯一的u在生成树中再加一条边必然形成回路n含n个顶点n-1条边的图不一定是生成树2021/8/619l 生成森林生成森林(spanning forest)(spanning forest)： 如果一个有向图恰有一

11、个顶点的入度为0，其余顶点的入度均为1，则它是一棵有向树。一个有向图的生成森林由若干棵有向树组成， 它含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。如图6.6 所示。ADAEFCBEBFCD 图6.6 一个有向图及其生成森林 图基本术语图基本术语(续续)2021/8/620l权权(weight)(weight)：在图的每条边上加上一个数字作权。如果用顶点代表城市， 权可以表示两城市之间的距离或耗费。l网网(network):(network):称带权的图为网. 基本术语图基本术语(续续)2021/8/621 图的存储结构图的存储结构至少要保存两类信息：至少

12、要保存两类信息： 1)1)顶点的数据顶点的数据 2)2)顶点间的关系顶点间的关系 为了讨论方便，我们约定为了讨论方便，我们约定: : G=(V, E) G=(V, E)是图是图, V=v, V=v0 0,v,v1 1,v,v2 2, v, vn-1n-1 , ,顶点的顶点的角标角标为它的编号。为它的编号。 V V0 0 V V4 4 V V3 3 V V1 1 V V2 2 V V0 0 V V1 1 V V2 2 V V3 37.2图的存储结构图的存储结构 下面介绍两种最常用的图的存储结构：下面介绍两种最常用的图的存储结构：邻接矩阵和邻接表邻接矩阵和邻接表。2021/8/622邻接矩阵邻接矩

13、阵(数组表示法数组表示法)邻接矩阵是表示顶点间相邻关系的矩阵。若G是一个具有n顶点的图，则的邻接矩阵是如下定义的nn矩阵：1,10）是图的边）或（若（否则ijjivvvvija 无向图的邻接矩阵是对称的。无向图的邻接矩阵是对称的。2021/8/623例G12413例15324G200110001011101010101010100001100000000110图的存储结构图的存储结构邻接矩阵邻接矩阵2021/8/624l网络的邻接矩阵可定义为：网络的邻接矩阵可定义为：，其它0E(G)v,v或)v,(v若,jijiijjiA网络的邻接矩阵网络的邻接矩阵例145237531864206183602

14、401200784005307502021/8/625无向图的邻接矩阵对称，可压缩存储；有无向图的邻接矩阵对称，可压缩存储；有n n个个顶点的无向图需存储空间为顶点的无向图需存储空间为n(n+1)/2n(n+1)/2有向图邻接矩阵不一定对称；有有向图邻接矩阵不一定对称；有n n个顶点的有个顶点的有向图需存储空间为向图需存储空间为n n无向图中顶点无向图中顶点V Vi i的度的度TD(VTD(Vi i) )是邻接矩阵是邻接矩阵A A中第中第i i行元素之和行元素之和有向图中：有向图中：顶点Vi的出度是A中第i行元素之和顶点Vi的入度是A中第i列元素之和邻接矩阵特点邻接矩阵特点2021/8/626

15、用邻接矩阵法建立有向图算法存储结构的定义：#define MaxVertexNum 100/* 最大顶点数设为100 */typedef char VertexType;/* 顶点类型设为字符型 */typedef int EdgeType;/* 边的权值设为整型 */typedef struct VertexType vexsMaxVertexNum； /* 存放顶点信息 */ EdgeType edgesMaxVertexNum MaxVertexNum；/* 存放邻接关系 */ int n,e; /*顶点数和边数*/Mgraph;void CreateMGraph(Mgraph *G)

16、int i,j,k,w; char ch; printf(“请输入顶点数和边数请输入顶点数和边数(输入格式输入格式为为:顶点数顶点数,边数边数):n”) ; scanf(“%d,%d”,&(G-n),&(G-e); printf(“请输入顶点信息请输入顶点信息(输入格式为输入格式为:顶顶点号点号):n”); for(i=0;in;i+) scanf(“n%c”,&(G-vexsi); for(i=0;in;i+) for(j=0;jn;j+) G-edgesij=0; printf(“请输入两条边对应的两个顶点请输入两条边对应的两个顶点的序号的序号(输入格式为输入格式为

17、:i,j):n”); for(k=0;ke;k+) scanf(“n%d,%d”,&i,&j); G-edggsij=1; 该算法是建立有向图该算法是建立有向图G G的邻接矩阵存储。的邻接矩阵存储。 那么用这种方法，如何存储无向图、那么用这种方法，如何存储无向图、有向网图和无向网图？有向网图和无向网图？2021/8/627在邻接表中，对图中每个顶点建立一个单链表，顶点v的单链表中的结点是vi的所有邻接点，在有向图中，顶点vi单链表中的结点是以vi为弧尾的顶点。图的存储结构图的存储结构邻接表邻接表(类似于树的孩子链表法类似于树的孩子链表法)2021/8/628邻接表的结点结构邻接

18、表的结点结构每一个结点由三个域组成每一个结点由三个域组成: :邻接点域（adjvex）:指示与顶点vi邻接的点在图中的编号。链域（nextarc ）:指示下一条边或弧的结点；数据域(info):存储和边或弧相关的信息，如权值等。每一个链表上附设一个表头结点，在表头结点中设有：每一个链表上附设一个表头结点，在表头结点中设有：链域(firtarc):指向链表第一个结点。数据域(vexdata):存储vi的名或其它有关信息。adjvexnextarcintovexdatafirstarc2021/8/629例G1bdac例aecbdG21234acdbvexdata firstarc 3 2 4 1

19、adjvex next1234acdbvexdata firstarc 4 2 1 2adjvex next5e 4 3 5 1 5 3 2 32021/8/630例1423512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 22021/8/631V1V2V4V5V3V7V6V8例12341342vexdata firstarc 2 7 8 3adjvex next55 6 4 1 5 1 2 8 2678678 7 3 6 3 5 42021/8/632V1V2V4V5V3V7V6V8例12341342vexdata fi

20、rstarc 2 7 8 3adjvex next55 6 4 8 2678678 72021/8/633l无向图中顶点无向图中顶点ViVi的度为第的度为第i i个单链表中的结点数个单链表中的结点数l有向图中有向图中顶点Vi的出度为第i个单链表中的结点个数顶点Vi的入度为整个单链表中邻接点域值是i的结点个数l逆邻接表：逆邻接表：有向图中对每个结点建立以有向图中对每个结点建立以ViVi为头的弧的单链表为头的弧的单链表例G1bdac1234acdbvexdata firstarc 4 1 1 3adjvex next邻接表存储结构的特点邻接表存储结构的特点2021/8/634邻接表的类型定义和构造

21、算法邻接表的类型定义和构造算法#define max_vertex_num 20 /最大顶点数struct arcnodeint adjvex;struct arcnode *nextarc;infotype info;/ 和弧有关的其它信息typedef struct arcnode *arcptr;typedef struct vexnodevextype vexdata;/ 和顶点有关的信息arcptr firstarc;adjlistmax_vertex_num+1; 构造算法构造算法 ：2021/8/635用邻接表法建立有向图算法邻接表的存储结构描述：#define MaxVerNu

22、m 100typedef struct node int adjvex; struct node *next; EdgeNode;typedef struct vnode vertexType vertex; EdgeNode *firstedge; VertexNode;typedef VertexNode AdjListMaxVerNum；typedef struct AdjList adjlist; int n,e ; ALGraph;void CreateALGraph(ALGraph *G) int i,j,k; EdgeNode *s; printf(“请输入顶点数和边数请输入顶点

23、数和边数(输入格式为输入格式为: 顶点数顶点数,边数边数):n” ); scanf(“%d,%d”,&(G-n),&(G-e); printf(“请输入顶点信息请输入顶点信息(输入格式为输入格式为:顶点顶点 信息信息):n”); for(i=0;in;i+) scanf(“%c”,&(G-adjlisti.vertex); G-adjlisti.firstedge=NULL; printf(“请输入边的信息请输入边的信息(输入格式输入格式:i,j):n”); for(k=0;ke;k+) scanf(“%d,%d”,&i,&j); s=(EdgeNode

24、*)malloc(sizeof(EdgeNode); s-adjvex=j; s-next=G-adjlisti.firstedge; G-adjlisti.firstedge=s; 该算法是建立有向图的邻接表存储。该算法是建立有向图的邻接表存储。 那么用这种方法，如何存储有向网图、那么用这种方法，如何存储有向网图、无向图和无向网图？无向图和无向网图？2021/8/636十字链表十字链表十字链表十字链表(orthogonal list)(orthogonal list)：可以看成是将有向图的邻接表和逆邻接表结合起来得到的另一种链表。在十字链表中，对应于有向图中每一条弧有一个结点，对每一个顶点也

25、有一个结点。在弧结点中有四个域：尾域尾域(tailvex)(tailvex)和头域头域(headvex)(headvex)：分别指示弧尾和弧头这两个顶点在图中的编号，链域链域(hlink)(hlink)：指向弧头相同的下一条弧，链域链域(tlink)(tlink)：指向指向弧尾相同的下一条弧。tailvexheadvexhlinktlink2021/8/637图的存储结构图的存储结构十字链表十字链表 弧头相同的弧在同一链表上，弧尾相同的弧也是在同一链表上。它们的头结点即为顶点结点，它由三个域组成：datadata域：域：存储和顶点相关的信息；firstinfirstin域域和 firstout

26、firstout域：域：两个链域，分别指向以该顶点为弧头或弧尾的第一个弧结点。datafirstinfirstout2021/8/638十字链表的类型定义十字链表的类型定义struct arctype int tailvex，headvex; arctype hlink,tlink;typedef struct arctype *arclink;typedef struct vnode vertex data; arclink firstin，firstout;ortholistmax_vertex_num+1;2021/8/639十字链表的建立十字链表的建立1324(a )123412413

27、142433413(b )2021/8/640图的存储结构图的存储结构边集数组边集数组 是利用一维数组存储图中所有边的一种图的表示方法。该数组中所含元素的个数要大于等于图中的边数，每个元素用来存储一条边的起点、终点（对于无向图，可选定边的任一端点为起点或终点）和权（若有的话），各边在数组中的次序可任意安排，也可根据具体要求而定。边集数组只是存储图中所有边的信息，若需要存储顶点信息，同样需要一个具有n个元素的一维数组。2021/8/641边集数组的类型定义边集数组的类型定义struct edge /定义边集数组的元素类型 int fromvex;/边的起点域 int endvex;/边的终点域

28、int weight;/边的权值域，对应无权图可省去此域 typedef edge edgesetMaxedgenum;/定义edgeset为边集数组类型2021/8/642图的存储结构图的存储结构边集数组边集数组143222125454354543632fromvexendvexweight145234233652021/8/643边集数组的建立边集数组的建立l建立：建立：在边集数组中查找一条边或一个顶点的度都需要扫描整个数组，所以其时间复杂度为O(e)。边集数组适合那些对边依次进行处理的运算，不适合对顶点的运算和对任一条边的运算。边集数组表示的空间复杂度为O(e)。从空间复杂度上讲，边集数

29、组也适合表示稀疏图。2021/8/6447.3 7.3 图的遍历图的遍历 图的遍历：图的遍历：从图的某顶点出发，访问图中所有顶点，并且每从图的某顶点出发，访问图中所有顶点，并且每个顶点仅被访问一次。个顶点仅被访问一次。 在图中，访问部分顶点后，可能又沿着其它边回到已被访问在图中，访问部分顶点后，可能又沿着其它边回到已被访问过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标记，一般用一个辅助数组记，一般用一个辅助数组visitedvisitedMaxVerNum 作为对顶点的标记，作为对顶点的标记，当顶点当顶点v vi i未被访问，未

30、被访问，visitedivisitedi值为值为0 0；当；当v vi i已被访问，则已被访问，则visitedivisitedi值为值为1 1。 图的遍历图的遍历与树的遍历有什么不同与树的遍历有什么不同? 有两种遍历方法有两种遍历方法（它们对无向图，有向图都适用）它们对无向图，有向图都适用） 深度优先遍历深度优先遍历( (深度优先搜索）深度优先搜索） 广度优先遍历广度优先遍历( (广度优先搜索）广度优先搜索）2021/8/645 V7V7 V3V3 V1V1 V4V4 V5V5 V6V6 V2V2 V0V0 V V3 3 V V7 7 V V5 5 V V6 6 V V2 2 V V0 0

31、V V1 1 V V4 4从图中某顶点从图中某顶点v v出发：出发： 1 1）访问顶点）访问顶点v v；2 2）依次从）依次从v v的未被访问的邻接点出发，继续对图进行深度优先遍历。的未被访问的邻接点出发，继续对图进行深度优先遍历。 V V0 0,V,V1 1,V,V3 3,V,V7 7,V,V4 4,V,V2 2,V,V5 5,V,V6 6 由于没有规定由于没有规定访问邻接点的顺序，访问邻接点的顺序，深度优先序列不是唯一的深度优先序列不是唯一的这是序列（这是序列（1 1）在遍历过程中在遍历过程中所经过的路径所经过的路径例例求图求图G G以以V V0 0为起点的的深度优先序列为起点的的深度优先

32、序列： V V0 0,V,V1 1,V,V4 4,V,V7 7,V,V3 3,V,V2 2,V,V5 5,V,V6 67.3.1 7.3.1 图的深度优先遍历图的深度优先遍历（类似于树的先序遍历）（类似于树的先序遍历）显然，图的深度优先遍历是一个递归过程。显然，图的深度优先遍历是一个递归过程。2021/8/646void DFS( Graph G, int v)/*从第从第v个顶点出发，递归地深度优先遍历图个顶点出发，递归地深度优先遍历图G */ visitFunc(v); visitedv=1; /* 访问第访问第v个顶点个顶点 */ for (w=FisrAdjVex(G,v);w;w=N

33、extAdjVex(G,v,w) /* 取顶点取顶点v的邻接顶点的邻接顶点w */ if (!visitedw) DFS(G,w); /* 对对v的尚未访问的邻接顶点的尚未访问的邻接顶点w递归调用递归调用DFS */ 图的图的深度优先遍历算法深度优先遍历算法 NextAdjVex(G,v,w): NextAdjVex(G,v,w): 在图在图G G中，返回中，返回V V的（相对于的（相对于W W的）下一个邻接顶点。若的）下一个邻接顶点。若W W是是V V的最后一个邻接点，则返的最后一个邻接点，则返回回“空空”。2021/8/647图的深度优先遍历算法图的深度优先遍历算法( (续续) ) V V

34、0 0 V V7 7 V V6 6 V V5 5 V V4 4 V V3 3 V V2 2 V V1 10 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7V V0 0V V1 1V V2 2V V3 3V V4 4V V5 5V V6 6V V7 71 12 20 01 11 15 57 77 73 30 06 64 42 26 65 52 24 43 3void DFSTraveseAL( ALGraph *G) int i; for (i=0; in;i+) visitedi=0; /* 给每个顶点一个未访问过标记给每个顶点一个未访问过标记 */ for (i=0; in; i

35、+) if (!visitedi) DFSAL(G,i); /*若顶点若顶点vi未访问过未访问过,从从vi开始深度优先遍历图开始深度优先遍历图*/ /* 要特别注意非连通图的遍历要特别注意非连通图的遍历 */void DFSAL( ALGraph *G,int i) EdgeNode *p; printf( “%c”,G-adjlisti.vertex);/*访问顶点访问顶点vi*/ visitedi=1; /* 标记标记顶点顶点vi已被访问过已被访问过 */ p= G-adjlisti.firstedge; /*取取vi边表头指针边表头指针*/ while (p） /* 若若p存在存在 */

36、 if ( !visitedp-adjvex) /* 若若v p-adjvex未被未被访问过访问过 */ DFSAL(G, p-adjvex); /* 从从v p-adjvexi出发开始深度优先遍历图出发开始深度优先遍历图 */ p=p-next; /*找和找和vi 相邻的下一邻接顶点相邻的下一邻接顶点*/ 深度优先遍历结果：深度优先遍历结果：V V0 0,V,V1 1,V,V3 3,V,V7 7,V,V4 4,V,V2 2,V,V5 5,V,V6 6 p2021/8/648图的深度优先搜索遍历算法执行过程的理解图的深度优先搜索遍历算法执行过程的理解0 0 1 1 2 2 3 3 4 4 5

37、5 6 6 7 7V V0 0V V1 1V V2 2V V3 3V V4 4V V5 5V V6 6V V7 71 12 20 01 11 15 57 77 73 30 06 64 42 26 65 52 24 43 3 V V0 0 V V7 7 V V6 6 V V5 5 V V4 4 V V3 3 V V2 2 V V1 1调用调用DFSAL的执行过程为的执行过程为(从从V V0 0出发出发)： V0 visited0=1 V1 DFSAL(G,1) visited1=1 V3 DFSAL(G,0) DFSAL(G,3) visited3=1 V7 DFSAL(G,7) visited

38、7=1 DFSAL(G,3) V4 V2 visited4=1 DFSAL(G,2) visited2=1 V5 DFSAL(G,5) visited5=1 V6 DFSAL(G,6) visited6=1 深度优先遍历结果：深度优先遍历结果：V V0 0,V,V1 1,V,V3 3,V,V7 7,V,V4 4,V,V2 2,V,V5 5,V,V6 6DFSAL(G,4)DFSAL(G,6)DFSAL(G,0)DFSAL(G,2) DFSAL(G,7)DFSAL(G,4)DFSAL(G,0)DFSAL(G,1) DFSAL(G,1)DFSAL(G,5)DFSAL(G,2)2021/8/649图

39、的深度优先搜索遍历算法执行过程的理解图的深度优先搜索遍历算法执行过程的理解( (续续) )l 图的深度优先搜索遍历过程有回退操作，计算机执行时就要用到栈。比如在执行 DFSAL(G,1) 时需将 DFSAL(G,2) 保存起来（压入栈中）, 当执行完 DFSAL（G,1）时 再 将DFSAL(G,2) 弹出栈继续执行。计算机用栈的具体执行过程为： (1)建立空栈, 访问第一个顶点、标记、压栈。 (2)当栈不空时,若有与栈顶元素相邻且未被访问 的顶点, 则访问、标记、压栈；若无与栈顶元素相邻且未被访问的顶点, 则弹出栈顶元素, 直到栈空为止。 2021/8/650 V3V3 V1V1 V7V7

40、V5V5 V6V6 V2V2 V0V0 V4V4 V V3 3 V V7 7 V V2 2 V V6 6 V V5 5V V0 0 V V1 1 V V4 4从图中某未被访问过的顶点从图中某未被访问过的顶点v vi i出发：出发：1 1）访问顶点）访问顶点v vi i ；2 2）访问）访问 v vi i 的所有未被访问的邻接点的所有未被访问的邻接点w w1 1 ,w ,w2 2 , w, wk k ；3 3）依次从这些邻接点出发，访问它们的所有未被访问的邻接点）依次从这些邻接点出发，访问它们的所有未被访问的邻接点; ; 依此类推，直到图中所有访问过的顶点的邻接点都被访问。依此类推，直到图中所有

41、访问过的顶点的邻接点都被访问。这是序列（这是序列（1 1）在遍历过程中在遍历过程中所经过的路径所经过的路径由于没有规定由于没有规定访问邻接点的顺序，访问邻接点的顺序，广度优先序列不是唯一的广度优先序列不是唯一的例例求图求图G G的以的以V0V0为起点的的广度优先序列为起点的的广度优先序列 V V0 0,V,V1 1,V,V2 2,V,V3 3,V,V4 4,V,V5 5,V,V6 6,V,V7 77.3.2 7.3.2 图的广度优先遍历图的广度优先遍历（类似于树的层次遍历）（类似于树的层次遍历） V V0 0,V,V2 2,V,V1 1,V,V6 6,V,V5 5,V,V4 4,V,V3 3,

42、V,V7 72021/8/651从图中某顶点从图中某顶点v vi i出发：出发：1 1）访问顶点）访问顶点v vi i；（容易实现）；（容易实现）2 2）访问）访问v vi i 的所有未被访问的邻接点的所有未被访问的邻接点w w1 1 ,w ,w2 2 , w, wk k；（容易实现）；（容易实现）3 3）依次从这些邻接点）依次从这些邻接点( ( 在步骤在步骤2)2)中访问过的顶点中访问过的顶点 ）出发）出发, ,访问它访问它们的所有未被访问的邻接点们的所有未被访问的邻接点; ; 依此类推依此类推, ,直到图中所有访问过的顶直到图中所有访问过的顶点的邻接点都被访问。点的邻接点都被访问。 为实现

43、为实现 3 3），需要保存在步骤），需要保存在步骤 2 2）中访问过的顶点）中访问过的顶点, ,而且而且访问访问这些顶点这些顶点邻接点邻接点的顺序为：先保存的顶点，其邻接点先被访问。的顺序为：先保存的顶点，其邻接点先被访问。为了保证为了保证“先被访问的顶点其先被访问的顶点其邻接顶点也先被访问邻接顶点也先被访问”，在，在广度优先遍历广度优先遍历算法中，需设置一算法中，需设置一队列队列Q Q，保存已访问的，保存已访问的顶点，并控制遍历顶点的顺序。顶点，并控制遍历顶点的顺序。图的图的广度优先遍历算法广度优先遍历算法 V V0 0 V V7 7 V V6 6V V5 5 V V4 4V V3 3 V

44、V2 2 V V1 12021/8/652图的广度优先遍历算法图的广度优先遍历算法( (续续) ) 广度优先遍历算法的具体执行过程为： (1) 队列置空，访问开始顶点、标记、入队； (2) 当队不空时，取出队头元素，访问与队头元素相邻的所有未被访问的顶点,并依次标记、入队。 2021/8/653图的广度优先遍历算法图的广度优先遍历算法( (续续) ) V V0 0 V V7 7 V V6 6 V V5 5 V V4 4 V V3 3 V V2 2 V V1 1广度优先遍广度优先遍历结果：历结果： V V0 0,V,V1 1,V,V2 2,V,V3 3, ,V V4 4,V,V5 5,V,V6

45、6,V,V7 7void BFSTraverseAL(Mgraph void BFSTraverseAL(Mgraph * *G)G) int i; int i; for (i=0;in;i+) for (i=0;in;i+) visitedi=0; visitedi=0; / /* * 给所有顶点一个未被访问标记给所有顶点一个未被访问标记 * */ / for (i=0;in;i+) for (i=0;in;i+) if(!visitedi) BFSM(G,i); if(!visitedi) BFSM(G,i); /* 若若vi未被访问过未被访问过, ,从从vi 开始进行开始进行广度优先遍历

46、广度优先遍历 * */ / /* 要特别注意非连通图的遍历要特别注意非连通图的遍历 */void BFSM(MGraph void BFSM(MGraph * *G,int k) G,int k) / /* *从从vk出发，广度优先遍历图出发，广度优先遍历图G G* */ / int i,j; CirQueue Q; int i,j; CirQueue Q; InitQueue(&Q); InitQueue(&Q); printf(“%c”,G-vexsk); printf(“%c”,G-vexsk); visitedk=1; visitedk=1; EnQueue(&

47、Q,k); EnQueue(&Q,k); while(!QueueEmpty(&Q) while(!QueueEmpty(&Q) i=DeQueue(&Q); i=DeQueue(&Q); for (j=0;jn;j+) for (j=0;jn;j+) if(G-edgesij=1&!visitedj) if(G-edgesij=1&!visitedj) printf(“%c”,G-vexsj); printf(“%c”,G-vexsj); visitedj=1; visitedj=1; EnQueue(&Q,j); EnQueu

48、e(&Q,j); V V0 0V V1 1V V2 2V V4 4V V3 3V V5 5V V7 7V V6 6G.vexsG.vexs0 1 1 0 0 0 0 00 1 1 0 0 0 0 01 0 0 1 1 0 0 01 0 0 1 1 0 0 01 0 0 0 0 1 1 01 0 0 0 0 1 1 00 1 0 0 0 0 0 10 1 0 0 0 0 0 10 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 0

49、 0 00 0 0 1 1 0 0 0G.edgesG.edgesG.n=8G.n=8G.e=9G.e=92021/8/654图遍历小结图遍历小结n图的遍历是指按照图的结构访问图中的各顶点,不能不顾图本身的结构特点, 只按其存储结构（各顶点的存储顺序）访问各顶点。n在图中各个顶点编号唯一的情况下，图若用邻接矩阵法存储，图的遍历结果唯一；图若用邻接链表存储，图的遍历结果不唯一（这是因为边的输入次序不同，图的邻接链表就不同）。n图的深度优先搜索遍历要用栈,图的广度优先搜索遍历要用队列。 2021/8/655V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍历：V1 V2 V

50、4 V8 V5 V6 V3 V7深度遍历：V1 V2 V4 V8 V5 V6 V3 V7练习：练习：图的深度优先遍历（图的深度优先遍历（ DFS ）2021/8/656V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V3 V6 V7 V52021/8/657V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8图的广度优先搜索（图的广度优先搜索（BFS）2021/8/658V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V6 V7

51、 V8 V52021/8/6597.4 图的连通性图的连通性l7.4.1 无向图的连通分量：无向图的连通分量：在对无向图进行遍历时，对于连通无向图，从图中任一顶点出发，便可遍历图。对于非连通的无向图G来说，G中一顶点v出发遍历图，不能访问到G的所有顶点。而只能访问到包含该顶点v 的极大的连通子图，即G的一个连通分量中的所有顶点。 若从无向图的每个连通分量中的一个顶点出发遍历图，则可求得无向图的所有连通分量。 2021/8/660图的连通性图的连通性算法：算法：可以调用dfs或bfs来遍历图，只是要对图的每一个顶点进行检查，若被访问过，则该顶点落在图中已被求过的连通分量上，若未被访问过，则从该顶

52、点出发遍历图，便可求得图的另一个连通分量。 算法分析：算法分析：dfs(或bfs)所需时间O(e)，故求G 的所有连通分量的时间复杂度为O(n+e)。 2021/8/6617.4.2 连通无向图的生成树连通无向图的生成树 设设G=(VG=(V，E)E)是一个连通无向图，则从图是一个连通无向图，则从图中任一顶点出发，能将中任一顶点出发，能将E E分成两个集合分成两个集合T(G)T(G)和和B(G)B(G)，其中，其中T(G)T(G)是遍历图时所通过的边是遍历图时所通过的边集，集，B(G)B(G)是剩余的边集。显然，是剩余的边集。显然，T(G)T(G)或图或图G G 中所有顶点一起构成连通图中所有

53、顶点一起构成连通图G G的极大连通子的极大连通子图，按图，按7.17.1节的定义，它是连通图的一棵生节的定义，它是连通图的一棵生成树，成树，并且由并且由DFS DFS 得到的是深度优先生成得到的是深度优先生成树，由树，由BFSBFS得到的为广度优先生成树得到的为广度优先生成树。2021/8/662V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8

54、2021/8/663非连通图的生成树非连通图的生成树对于非连通图，每个连通分量中的顶点对于非连通图，每个连通分量中的顶点集和遍历时走过的边一起构成若干棵集和遍历时走过的边一起构成若干棵生成树，这些通分量的生成树组成非生成树，这些通分量的生成树组成非连通图的生成森林。连通图的生成森林。2021/8/664例ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林2021/8/665n生成树的概念生成树的概念 包含无向图包含无向图G 所有顶点的的极小连通子图称为所有顶点的的极小连通子图称为G 的生成树。即的生成树。即由具有由具有n个顶个顶点的连通图生成的一个具有点的连通图生成的一个具有

55、n个顶点、个顶点、n-1条边且无回路的连通图叫生成树。条边且无回路的连通图叫生成树。 若若T是是G 的生成树当且仅当的生成树当且仅当T 满足如下条件：满足如下条件： 1）T是是G 的连通子图的连通子图(即生成树是由一个连通图生成的另一个连通图即生成树是由一个连通图生成的另一个连通图)。 2）T包含包含G 的所有顶点的所有顶点,但边数比但边数比G中边数要少中边数要少,当且仅有当且仅有n-1条条(在在T中删除任中删除任何一条边何一条边, T不再连通不再连通)。 3）T中无回路。中无回路。 具有这三个条件的图才叫生成树。它是由一个连通图生成的具有这三个条件的图才叫生成树。它是由一个连通图生成的,它象

56、一棵树它象一棵树(没没有回路有回路)，所以叫生成树。，所以叫生成树。G1G1的生成树的生成树 V V0 0 V V4 4 V V3 3 V V1 1 V V2 2连通图连通图G1G1 V V0 0 V V4 4 V V3 3 V V1 1 V V2 27.4.3 7.4.3 生成树与最小生成树与最小生成树生成树由一个连通图可以生成若干个生成树。那么，什么叫最小生成树？由一个连通图可以生成若干个生成树。那么，什么叫最小生成树？ V V0 0 V V4 4 V V3 3 V V1 1 V V2 2G1G1的生成树的生成树2021/8/666n最小生成树的概念最小生成树的概念 要在要在 n n个城市

57、间建立交通网，要个城市间建立交通网，要考虑的问题是如何在保证考虑的问题是如何在保证 n n 点连通点连通的前提下最节省经费的前提下最节省经费? V2V2V0V0V3V3V5V5V4V4V1V13 36 65 52 21 16 65 55 54 46 6例例 求解求解: 连通连通6 6个城市且代价个城市且代价最小的交通线路最小的交通线路? 如何求连通图的如何求连通图的最小生成树最小生成树? 若有一个连通的无向图若有一个连通的无向图G,G,有有n n个顶点个顶点, ,并且它的边并且它的边是有权值的。在是有权值的。在G G上可以构造若干棵生成树。我们把上可以构造若干棵生成树。我们把所有所有n-1 n

58、-1 条边的权值之和最小的生成树叫最小生成条边的权值之和最小的生成树叫最小生成树。树。2021/8/667 普里姆算法基本步骤普里姆算法基本步骤设设G=（V，E）为一个具有）为一个具有n个顶点的带权的连通网络，个顶点的带权的连通网络，T=（U，TE）为构）为构造的生成树。造的生成树。（1）初始时，）初始时，U=u0，TE= 。（2）在所有）在所有u U 、v V-U 的边（的边（u,v）中选择一条权值最小的边，假定为）中选择一条权值最小的边，假定为（u,v)；将；将(u,v) 加入加入TE，同时将，同时将v 加入加入U。（3）重复）重复(2)n-1次（即使次（即使U=V时为止）。时为止）。n构

59、造最小生成树的普里姆构造最小生成树的普里姆(Prim)(Prim)算法算法 V2V2V0V0V3V3V5V5V4V4V1V13 36 65 52 21 16 65 55 54 46 62021/8/668U= V0,V2 U= V0,V2 V V2 2V V0 01U= V0,V2,V5U= V0,V2,V51V V2 2V V0 0V V5 54U= V0,V2,V5,V3 U= V0,V2,V5,V3 2V V2 2V V0 0V V3 3V V5 514U= V0,V2,V5,V3,V1 U= V0,V2,V5,V3,V1 2V V2 2V V0 0V V3 3V V5 5V V1 11

60、45U= V0,V2,V5,V3,V1,V4 U= V0,V2,V5,V3,V1,V4 2V V3 3V V0 0V V3 3V V5 5V V4 4V V1 11453普里姆普里姆(Prim)(Prim)算法构造算法构造最小生成树的过程最小生成树的过程V V2 2V V0 0V V3 3V V5 5V V4 4V V1= V0 U= V0 V V0 02021/8/669 有关数据的存储有关数据的存储 普里姆算法涉及的数据和操作：普里姆算法涉及的数据和操作： 数据：无向连通网络数据：无向连通网络 操作操作 : 选择权值最小的边（选择权值最小的边（u,v)，将，将(u,v)加入加入TE，v加入加入U 构造构造最小生成树最小生成树普里姆普里姆(Prim)(Prim)算法算法的实现的实现 数组数组LowcostLowcost：保存当前不在最小