数据结构第06章图_c1

1、2022-3-212022-3-22 在在线性结构线性结构中，结点之间的关系是中，结点之间的关系是线性关系线性关系，除开始结点和，除开始结点和终端结点外，终端结点外，每个结点每个结点只有只有一个直接前趋一个直接前趋和和直接后继直接后继； 在在树形结构树形结构中，结点之间的关系实质上是中，结点之间的关系实质上是层次关系层次关系，同层上，同层上的每个结点可以和下一层的零个或多个结点（即的每个结点可以和下一层的零个或多个结点（即孩子孩子）相关，但）相关，但只能和上一层的一个结点（即只能和上一层的一个结点（即双亲双亲）相关（根结点除外）；）相关（根结点除外）； 图图（GraphGraph）是一种较线性

2、表和树更为复杂的是一种较线性表和树更为复杂的非线性结构非线性结构。是。是对结点的对结点的前趋和后继个数不加限制前趋和后继个数不加限制的数据结构，用来描述元素之的数据结构，用来描述元素之间间“多对多多对多”的关系的关系( (即结点之间的关系是任意的即结点之间的关系是任意的) )。2022-3-23 (1) (1)了解图的定义和术语了解图的定义和术语 (2) (2)掌握图的各种存储结构掌握图的各种存储结构邻接矩阵、邻接表、邻接矩阵、邻接表、十字链表、邻接多重链表十字链表、邻接多重链表 (3) (3)掌握图的深度优先搜索和广度优先搜索遍历算法掌握图的深度优先搜索和广度优先搜索遍历算法 (4) (4)

3、理解理解最小生成树、最短路径、拓扑排序、关键路径最小生成树、最短路径、拓扑排序、关键路径等等图的常用算法图的常用算法 图的应用的主要算法，主要包括：图的应用的主要算法，主要包括：最小生成树、最短路径、最小生成树、最短路径、拓扑排序、关键路径拓扑排序、关键路径等图的常用算法等图的常用算法2022-3-24顶点（顶点（vertexvertex）边（边（edgeedge）2022-3-251 1、有向图（有向图（digraphdigraph）directed graphdirected grapharcarctailtailheadhead1234G12022-3-262、无向图无向图1234G22

4、022-3-27V（G1）=1，2，3，4 E（G1）=，V V（G2G2）=1=1，2 2，3 3，44E E（G2G2）=（1 1，2 2），（），（1 1，3 3），（），（1 1，4 4），（），（2 2，3 3），（），（2 2，4 4），（），（3 3，4 4） V（G3）=A，B，C，D，E E（G3）=（A，B），（），（A，C），（），（B，D），（），（C，E）2022-3-28如果图如果图G = （V，E）为）为无向图无向图，若存在一条边（，若存在一条边（v，v）E（G），则称点），则称点v和和v互为邻接点互为邻接点，即，即v和和v相邻接，边相邻接，边（v，v）依附于顶点

5、）依附于顶点v和和v，或者说（，或者说（v，v）和顶点）和顶点v和和v相关联相关联。如果图如果图G = （V，E）为）为有向图有向图，若存在一条弧，若存在一条弧 E（G），则称），则称顶点顶点v邻接到顶点邻接到顶点v，顶点顶点v邻接自顶邻接自顶点点v，弧，弧 和顶点和顶点v和和v相关联相关联。VV、V互为邻接点互为邻接点VV 是的邻接点是的邻接点2022-3-29 4、顶点的度、顶点的度在在无向图无向图中，顶点中，顶点v的的度度指指与顶点与顶点v相关联的边的数目相关联的边的数目；在在有向图有向图中，中，顶点顶点v的的出度出度指以顶点指以顶点v为弧尾的弧的数目；为弧尾的弧的数目；顶点顶点v的的入

6、度入度指以顶点指以顶点v为弧头的弧的数目；为弧头的弧的数目；顶点顶点v的出度与入度之和称为的出度与入度之和称为顶点顶点v的度的度。 1234G11234G22022-3-210无向完全图：若一个无向完全图：若一个无向图无向图有有n n个顶点，每个顶点个顶点，每个顶点与其他与其他n-1n-1个顶点都有边相连，这样的图称为个顶点都有边相连，这样的图称为无向完无向完全图全图，共有，共有n(n-1)/2n(n-1)/2条边；条边；有向完全图：在具有有向完全图：在具有n n个顶点的个顶点的有向图有向图中，如有中，如有n(n-1)n(n-1)条弧，即任意两个顶点之间都有方向相反的两条弧，即任意两个顶点之间

7、都有方向相反的两条弧连接，则称这样的图为条弧连接，则称这样的图为有向完全图有向完全图。 1234G2G412342022-3-211 6、路径和回路、路径和回路在图在图G 中，如果存在一个顶点序列中，如果存在一个顶点序列（1，2，3，N），使得（），使得（i，i+1）E（G），），1 i N，则称这个，则称这个顶点序列为顶点顶点序列为顶点1到顶点到顶点N的一条的一条路径路径（path）。这条这条路径的长（路径的长（length）是路径上的是路径上的边数，它等于边数，它等于N1。对于有向图，其路径也是有向的，对于有向图，其路径也是有向的，路径由弧组成。路径由弧组成。 2022-3-212 如果一

8、条路径上所有顶点除如果一条路径上所有顶点除起始点起始点和和终止终止点点外彼此外彼此是不同是不同的，则称该路径是的，则称该路径是简单路径简单路径。在一条路径中，如果其在一条路径中，如果其起始点起始点和和终止点终止点是是同一顶点同一顶点，则称其为，则称其为回路回路或或环（环（circlecircle）。简。简单路径相应的回路称为单路径相应的回路称为简单回路简单回路。无向图的回路，组成回路的边是互异的。无向图的回路，组成回路的边是互异的。无向图中的路径无向图中的路径u u，v v，u u不应被认为是回路不应被认为是回路，因，因为（为（u u，v v）和（）和（v v，u u）是同一条边。而有向图）是

9、同一条边。而有向图中中uv，vu是两条不同的边，因此是两条不同的边，因此有向有向图中的路径图中的路径u u，v v，u u是一条回路是一条回路。如果一个有向图没有回路，则称其为如果一个有向图没有回路，则称其为无环无环的的（acyclicacyclic），一个），一个有向无环图有向无环图有时也简称为有时也简称为DAGDAG（Direct Acyclic GraphDirect Acyclic Graph）。）。2022-3-213 设有两个图设有两个图 G(V, E) 和和 G(V, E)。若若 V V 且且 E E, 则称则称 图图G 是是 图图G 的的子图子图。2022-3-214在图在图G

10、中，若从中，若从vi到到vj（ij）有路径，则称）有路径，则称vi到到vj是连是连通的通的。如果图。如果图G中任意两个不同的顶点中任意两个不同的顶点vi和和vj都连通都连通(即有即有路径），则称路径），则称G 为为连通图连通图。在在无向图无向图中，极大的连通子图称为中，极大的连通子图称为它的它的连通分量连通分量。图图6-2中中G4不是连通的，但有两个连通分量。不是连通的，但有两个连通分量。任何任何连通图连通图的连通分量只有一个，即其自身，而非的连通分量只有一个，即其自身，而非连通图有多个连通分量。连通图有多个连通分量。2022-3-215在在有向图有向图中，若对于图中的每一对不同的顶点中，若对

11、于图中的每一对不同的顶点v vi i、v vj j，都存，都存在从在从v vi i到到v vj j及及v vj j到到v vi i的路径，则称该有向图是的路径，则称该有向图是强连通图强连通图。有向图。有向图中极大的强连通子图称为它的中极大的强连通子图称为它的强连通分量强连通分量。图。图6-16-1中的中的G G1 1不是强不是强连通图，但它有三个强连通分量，如图连通图，但它有三个强连通分量，如图6-36-3所示。所示。强连通图强连通图只有一个强连通分量，即其自身，而非强连只有一个强连通分量，即其自身，而非强连通图有多个连通分量。通图有多个连通分量。2022-3-216 (a) 无向网 (b)有

12、向网 无向带权图和有向带权图 5 3 1 2 4 4 1 6 7 2 3 5 8 A B C 2 1 5 3 4 权可以代表一个顶点到另一个顶点的距离、耗费等。权可以代表一个顶点到另一个顶点的距离、耗费等。称为称为如下图所示如下图所示 若若无向图无向图G G中每一条边都有一个对应的数，则称中每一条边都有一个对应的数，则称G G为为带带权图或网权图或网。类似的，边上带权的有向图称为。类似的，边上带权的有向图称为有向网有向网。 2022-3-217 非连通图非连通图的生成树则组成一个的生成树则组成一个生成森林生成森林。若图中有。若图中有n n个顶点，个顶点，m m个连通分量，则生成森林中有个连通分

13、量，则生成森林中有n-mn-m条边。条边。2022-3-218 图的基本运算也包括查找、插入和删除。图的基本运算也包括查找、插入和删除。（1 1）顶点定位运算）顶点定位运算 确定顶点确定顶点v v在图中的位置；在图中的位置；（2 2）取顶点运算）取顶点运算 求取图中第求取图中第i i个顶点；个顶点；（3 3）求第一个邻接点运算）求第一个邻接点运算 求图中顶点求图中顶点v v的第一个邻接点；的第一个邻接点；（4 4）求下一个邻接点运算）求下一个邻接点运算 已知已知w w为图中顶点为图中顶点v v的某个邻接点，求的某个邻接点，求顶点顶点w w的下一个邻接点；的下一个邻接点；（5 5）插入顶点运算）

14、插入顶点运算 在图中增添一个顶点在图中增添一个顶点v v作为图的第作为图的第n+1n+1个顶点，个顶点，其中其中n n为插入该顶点前图的顶点个数；为插入该顶点前图的顶点个数；（6 6）插入弧运算）插入弧运算 在图中增添一条从顶点在图中增添一条从顶点v v到顶点到顶点w w的弧。的弧。（7 7）删除顶点运算）删除顶点运算 从图中删除顶点从图中删除顶点v v以及所有与顶点以及所有与顶点v v相关联的相关联的弧。弧。（8 8）删除弧运算）删除弧运算 从图中删除一条从顶点从图中删除一条从顶点v v到顶点到顶点w w的弧。的弧。2022-3-219 邻接矩阵邻接矩阵(Adjacency Matrix)是

15、是用一维数组存储图中顶点的信息，用矩阵（即二维数组）表示图中各顶点之间的邻接关系。设设G(V，E)是具有是具有n个顶点的图，则以邻接矩阵表示这个图时，个顶点的图，则以邻接矩阵表示这个图时，需要存放需要存放n个顶点的信息以及个顶点的信息以及n2个边（或弧）的信息。其形式描述个边（或弧）的信息。其形式描述如下：如下： 根据图的定义，图的存储需要考虑两方面的信息的存储，即顶点的信息和边（或弧）的信息。 本节重点介绍图的邻接矩阵和邻接表两种存储结构。2022-3-220 图的邻接矩阵图的邻接矩阵(Adjacency Matrix)表示的类型，其表示的类型，其 形式描述如下：形式描述如下：#define

16、 MaxVertexNum 100 /*最大顶点数设为最大顶点数设为100*/typedef char VertexType; /*顶点类型设为字符型顶点类型设为字符型*/typedef int EdgeType; /*边的权值设为整型边的权值设为整型*/typedef struct VertexType vexsMaxVertexNum; /*顶点表顶点表*/EdgeType edgesMaxVertexNumMaxVertexNum; /*邻接矩阵，即边表邻接矩阵，即边表*/ int n,e; /*顶点数和边数顶点数和边数*/MGraph; /*Maragh是以邻接矩阵存储的图类型是以邻接

17、矩阵存储的图类型*/2022-3-221对于对于 n 阶方阵数组阶方阵数组 edges ，有如下性质：，有如下性质：edges1，若（，若（i，j）或）或 E（G）0，其他，其他2022-3-2220 1 0 01 0 0 11 0 0 10 0 0 0A1 =0 1 1 11 0 1 11 1 0 11 1 1 0A2 =图图6-4 图的邻接矩阵图的邻接矩阵0 1 1 0 01 0 0 1 01 0 0 0 10 1 0 0 00 0 1 0 0A3 =(a) G1的邻接矩阵的邻接矩阵(b) G2的邻接矩阵的邻接矩阵(c) G3的邻接矩阵的邻接矩阵2022-3-223143200110000

18、10100101(a)(b)有向图及其邻接矩阵有向图及其邻接矩阵 154320010101011001001110010011(a)(b)无向图及其邻接矩阵无向图及其邻接矩阵1 2 3 4 512342022-3-224 对于无向图，（对于无向图，（vi，vj）和（和（vj，vi）表示同一条边，因表示同一条边，因此，在邻接矩阵中此，在邻接矩阵中Aij=Aji。 无向图的邻接矩阵是（关于主对角线）对称矩阵无向图的邻接矩阵是（关于主对角线）对称矩阵，可用，可用主对角线以上（或以下）的部分表示。主对角线以上（或以下）的部分表示。 对有向图，弧对有向图，弧和和表示方向不同的两条弧，表示方向不同的两条弧

19、，Aij和和Aji表示不同的弧，所以表示不同的弧，所以有向图的邻接矩阵一般不具有对有向图的邻接矩阵一般不具有对称性。称性。 邻接矩阵表示法适合于以顶点为主的运算邻接矩阵表示法适合于以顶点为主的运算。 根据根据邻接矩阵邻接矩阵很很容易判定任意两个顶点之间是否有边相容易判定任意两个顶点之间是否有边相连连，并容易求得，并容易求得各个顶点的度各个顶点的度。2022-3-225对于对于有向图有向图，顶点顶点v vi i的出度的出度OD (vOD (vi i) )等于等于邻接矩阵第邻接矩阵第i i行元行元素之和素之和；顶点顶点v vi i的入度的入度ID (vID (vi i) )等于等于邻接矩阵第邻接矩

20、阵第i i列元素之和列元素之和，即即 ： 对于对于无向图无向图，顶点顶点v vi i的度的度等于等于邻接矩阵第邻接矩阵第i i行的元素之和行的元素之和或或第第i i列元素之和列元素之和，即：，即： njjiA1,njijA1,njjiA1,TDTD（v vi i）= =njijA1,= =2022-3-226 建立图的邻接矩阵算法如下：建立图的邻接矩阵算法如下：void CreateMGraph(MGraph *G) int i, j, k; printf(请输入顶点数和边数请输入顶点数和边数(输入格式为输入格式为:顶点数顶点数,边数边数):n); scanf(%d,%d,&(G-n)

21、,&(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(请输入每条边对应的两个顶点的序号请输入每条边对应的两个顶点的序号(输入格式为输入格式为:i,j):n); for (k=0;ke;k+) scanf(%d,%d,&i,&j); /*输入e条边

22、，建立邻接矩阵*/G-edgesij=1; /*若此处加入G-edgesji=1;，则为无向图的邻接矩阵存储建立*/ 2022-3-227 带权图的邻接矩阵，为了能够存储边的权值，带权图的邻接矩阵，为了能够存储边的权值，对于对于n n阶方阵数组阶方阵数组edgesedges，有如下性质：，有如下性质： 邻接矩阵的优点是实现简单，但是它的空间复杂度是O(n2)。如果图是稠密的，则用邻接矩阵是合适的存储方法，但是如果图是稀疏的，那么这种表示代价就太大了，更好的方法是采用邻接表存储。 edgesWi,j，若（，若（i，j）或）或 E（G），其他，其他2022-3-228 图的邻接表的存储结构是一种图

23、的邻接表的存储结构是一种顺序分配顺序分配和和链式分配相结合链式分配相结合的的存储结构，包括两个部分，一部分是存储结构，包括两个部分，一部分是数组数组，一部分是，一部分是链表图的链链表图的链式式存储结构。存储结构。 1）以一个数组来存储图中所有的）以一个数组来存储图中所有的顶点信息顶点信息，数组中每个元，数组中每个元素表示图中一个顶点，素表示图中一个顶点，在邻接表中又称作表头结点在邻接表中又称作表头结点，表头结点的，表头结点的结构如图所示，结构如图所示，vertex域用来存储顶点自身的信息，域用来存储顶点自身的信息，firstedge域域是一个指针，指向一个链表（即与该顶点相关的边链表）。是一个

24、指针，指向一个链表（即与该顶点相关的边链表）。2022-3-229 2022-3-230typedef struct node/*表结点表结点*/ int adjvex; /*邻接点域邻接点域*/ struct node * next; /*指向下一个邻接点的指针域指向下一个邻接点的指针域*/ /* int info； 若要表示边上信息，则应增加一个数据域若要表示边上信息，则应增加一个数据域info*/EdgeNode; typedef struct vnode /*表头结点表头结点*/ VertexType vertex; /*顶点域顶点域*/ EdgeNode * firstedge; /

25、*边表头指针边表头指针*/VertexNode; typedef structVertexNode adjlistMaxVertexNum; /*邻接表邻接表*/int n, e; /*顶点数和边数顶点数和边数*/ALGraph; /*ALGraph是以邻接表方式存储的图类型是以邻接表方式存储的图类型*/图的邻接表的存储结构可以形式地描述如下：图的邻接表的存储结构可以形式地描述如下： 2022-3-2312022-3-2322022-3-233 建立一个有向图的邻接表存储的算法建立一个有向图的邻接表存储的算法void CreateALGraph(ALGraph *G) int i,j,k; E

26、dgeNode * s; printf(请输入顶点数和边数请输入顶点数和边数(输入格式为输入格式为:顶点数顶点数,边数边数)：n); scanf(%d, %d, &(G-n), &(G-e); /*读入顶点数和边数*/ printf(“n请输入顶点信息请输入顶点信息(输入格式为输入格式为: 顶点号顶点号)：n); for (i = 0; i n; i+) /*建立有n个顶点的顶点表*/ scanf(“n%c, &(G-adjlisti.vertex); /*读入顶点信息*/ G-adjlisti.firstedge = NULL; /*顶点的边表头指针设为空*/ 202

27、2-3-234 printf(“n请输入边的信息请输入边的信息(输入格式为输入格式为:i,j)：n); for (k=0; ke; k+) /*建立边表*/ scanf(%d, %d, &i, &j); /*读入边的顶点对应序号*/ s = (EdgeNode*)malloc(sizeof(EdgeNode); /*生成新边表结点s*/ s-adjvex = j; /*邻接点序号为j*/ s-next = G-adjlisti.firstedge;/*将新边表结点s用头插法插入到顶点Vi 的边表头部*/ G-adjlisti.firstedge = s; 2022-3-2352

28、022-3-2362022-3-237 若若无向图无向图中有中有n 个顶点个顶点、e条边条边，则它的，则它的邻接表邻接表需需n个个头结点头结点和和2e个表结点个表结点。显然，在。显然，在边稀疏边稀疏(en(n-1)/2)的的情况下，用情况下，用邻接表表示图比邻接矩阵节省存储空间邻接表表示图比邻接矩阵节省存储空间。 在邻接表上容易找到任一顶点的第一个邻接点和下一在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点，但要判定任意两个顶点（个邻接点，但要判定任意两个顶点（vi 和和vj）之间是否之间是否有边或弧相连，则需搜索第有边或弧相连，则需搜索第i个或第个或第j个链表，因此，不个链表，因此，不

29、及邻接矩阵方便。及邻接矩阵方便。 2022-3-238hlink指向弧头相同的下一条弧，指向弧头相同的下一条弧，tlink指向弧尾相同的下一指向弧尾相同的下一条弧。条弧。headvextailvexhlinktlinkinfofirstindatafirstout顶点结点顶点结点弧结点弧结点2022-3-23943213231201203010321V2V0V1V2V3V1V2V0V32022-3-2402022-3-241markivex ilinkjvexjlinkdatafirstedge2022-3-2422301154323441201304321图图6-9为图为图6-5 (a)无向

30、图的邻接多重表。无向图的邻接多重表。( (省略了边结点的省略了边结点的markmark域域) )V0V1V2V3V4V0V1V2V3V42022-3-2432022-3-244 为避免同一个顶点被访问多次，采用一个数组为避免同一个顶点被访问多次，采用一个数组visited，用以标志顶点是否被访问过。如果顶点用以标志顶点是否被访问过。如果顶点i已访问过，则已访问过，则visitedi=1，如果没被访问过，则，如果没被访问过，则visitedi为初始值为初始值0。图的遍历顺序有两种：图的遍历顺序有两种：对每种搜索顺序，访问各顶点的顺序也对每种搜索顺序，访问各顶点的顺序也不是唯一的。不是唯一的。20

31、22-3-2451 深度优先搜索思想深度优先搜索思想 假定给定图假定给定图G的初态是所有顶点均未被访问过，在的初态是所有顶点均未被访问过，在G中中任选一个顶点任选一个顶点i作为遍历的初始点访问，则深度优先搜索作为遍历的初始点访问，则深度优先搜索递递归调用包含以下操作：归调用包含以下操作：（1）访问顶点）访问顶点i的未被访问的邻接点的未被访问的邻接点之一（顶点之一（顶点j）；（2）将顶点）将顶点j的的visited数组元素值置数组元素值置1；（3）搜索顶点）搜索顶点j的未被访问的邻接点，若该邻接点存在，的未被访问的邻接点，若该邻接点存在，则访问该邻接点，将此邻接点作为新的顶点则访问该邻接点，将此

32、邻接点作为新的顶点i开始重复（开始重复（1）-（3）。）。 2022-3-246无向图的无向图的深度优先搜索遍历过程深度优先搜索遍历过程如下：如下： 首先访问指定的起始顶点首先访问指定的起始顶点，由，由 v 出发，访问它的任一邻接顶出发，访问它的任一邻接顶点点w1；再从再从 w1 出发，访问与出发，访问与 w1邻邻 接但还没有访问过的顶点接但还没有访问过的顶点 w2；然后再从然后再从 w2 出发，重复上述过程，直至到达一个所有邻接点都已出发，重复上述过程，直至到达一个所有邻接点都已经被访问过的顶点为止。经被访问过的顶点为止。接着，按刚才的访问顺序向前回溯一个顶点，看是否还有其它接着，按刚才的访

33、问顺序向前回溯一个顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到已访问过的顶点都再没有未被访问的邻接点。重复上述过程，直到已访问过的顶点都再没有未被访问的邻接点。 这时，若图中还有未被访问的顶点，则任选一个未被访问的顶这时，若图中还有未被访问的顶点，则任选一个未被访问的顶点访问，然后重复上述搜索过程，直到图中全部顶点都被访问过为点访问，然后重复上述搜索过程，直到图中全部

34、顶点都被访问过为止。这里的止。这里的搜索次序体现了优先向深度发展的趋势，故称为深度优搜索次序体现了优先向深度发展的趋势，故称为深度优先搜索（先搜索（DFS）。）。 2022-3-247深度优先搜索序列为：v0、v1、v3、v7、v4、v5、v2、v6。 从v0出发深度优先搜索的遍历序列为： v0、v2、v6、v7、v5、v4、v1、v3。 2022-3-2482022-3-24917823456(a)2022-3-250深度优先搜索深度优先搜索DFS(v0)可描述为：可描述为：（1）访问）访问v0顶点；顶点；（2）置）置 visitedv0=1；（3）搜索搜索v0未被访问的邻接点未被访问的邻接

35、点w，若存在邻接点若存在邻接点w，则则DFS(w)。 2022-3-251算法6-3给出了对以邻接表为存储结构的整个图G进行深度优先遍历算法的C语言描述，算法6-4实现了以vi为出发点对邻接表存储的图G进行DFS搜索。void DFSTraverseAL(ALGraph *G)/*算法6-3 */int i;for (i=0; in; i+)visitedi = FALSE; /*标志向量初始化*/for (i=0; in; i+) /*vi未访问过，从vi开始DFS搜索*/if (!visitedi) DFSAL(G, i); 2022-3-252void DFSAL(ALGraph *G,

36、 int i)/*算法6-4*/EdgeNode *p;printf(visit vertex:V%cn, G-adjlisti.vertex); /*访问顶点vi*/visitedi=TRUE; /*标记vi已访问*/p=G-adjlisti.firstedge; /*取vi边表的头指针*/while(p) /*依次搜索vi的邻接点vj */if (!visitedp-adjvex) /*若vj尚未访问，则以vj为出发点向纵深搜索*/ DFSAL(G,p-adjvex); p=p-next; /*找vi的下一个邻接点/ 设无向图设无向图G有有n个顶点、个顶点、e条边，由于对邻接表中条边，由于

37、对邻接表中的每个顶点最多检测一次，共有的每个顶点最多检测一次，共有2e个表结点，故完成个表结点，故完成搜索的搜索的时间复杂度为时间复杂度为O(e)。 2022-3-253 1 广度优先搜索思想广度优先搜索思想 广度优先搜索遍历类似于树的按层次遍历。广度优先搜索遍历类似于树的按层次遍历。 广度优先搜索是从图的某个顶点广度优先搜索是从图的某个顶点v出发，在访问出发，在访问v之后，依次搜之后，依次搜索访问索访问v的各个未被访问过的邻接点的各个未被访问过的邻接点w1，w2，。然后顺序搜索访。然后顺序搜索访问问w1的各未被访问过的邻接点，的各未被访问过的邻接点，w2的各未被访问过的邻接点，的各未被访问过

38、的邻接点，。即从即从v开始，由近至远，按层次依次访问与开始，由近至远，按层次依次访问与v有路径相通且路径长度有路径相通且路径长度分别为分别为1，2，的顶点，直至连通图中所有顶点都被访问一次。这的顶点，直至连通图中所有顶点都被访问一次。这时，若图中还有未被访问的顶点，则任选一个未被访问的顶点访问，时，若图中还有未被访问的顶点，则任选一个未被访问的顶点访问，然后重复上述搜索过程，直到图中全部顶点都被访问过为止。然后重复上述搜索过程，直到图中全部顶点都被访问过为止。 广度优先搜索的顺序不是唯一的，例如广度优先搜索的顺序不是唯一的，例如6-14中的无向图中的无向图G4为例为例。 2022-3-254从

39、v0出发遍历，其广度优先搜索序列可为： v0、v1、v2、v3、v4、v5、v6、v7。从v0出发广度优先搜索的遍历序列为： v0、v2、v1、v6、v5、v4、v3、v7。0000100001000001110010011001000010000100000010000110001111000110从v0出发广度优先搜索的遍历序列为： v0、v1、v2、v3、v4、v5、v6、v7。2022-3-2551 广度优先搜索思想广度优先搜索思想 设图设图G的初态是所有顶点均未访问，在的初态是所有顶点均未访问，在G 中任选一顶点中任选一顶点i作为初作为初始点，则广度优先搜索的基本思想是：始点，则广度

40、优先搜索的基本思想是： 并将其访问标志置为已并将其访问标志置为已被访问，即被访问，即visitedi=1； 依此类推，直到图中所有顶点都被访问完为止依此类推，直到图中所有顶点都被访问完为止 。2022-3-256广度优先搜索在搜索访问一层时，需要记住已被访问的顶点，广度优先搜索在搜索访问一层时，需要记住已被访问的顶点，以便在访问下层顶点时，从已被访问的顶点出发搜索访问其邻接以便在访问下层顶点时，从已被访问的顶点出发搜索访问其邻接点。所以在点。所以在广度优先搜索中需要设置一个队列广度优先搜索中需要设置一个队列Queue，使已被访使已被访问的顶点顺序由队尾进入队列。在搜索访问下层顶点时，先从队问的

41、顶点顺序由队尾进入队列。在搜索访问下层顶点时，先从队首取出一个已被访问的上层顶点，再从该顶点出发搜索访问它的首取出一个已被访问的上层顶点，再从该顶点出发搜索访问它的各个邻接点各个邻接点 2022-3-257算法算法6-5 广度优先遍历广度优先遍历以邻接矩阵存储的图以邻接矩阵存储的图Gvoid BFSTraverseAL(MGraph *G)int i; for (i=0; in; i+) visitedi = FALSE; /*标志向量初始化*/ for (i=0; in; i+)if (!visitedi) /* vi未访问过，从vi开始BFS搜索*/BFSM(G, i);2022-3-25

42、8算法算法6-6 以以vk为出发点，对为出发点，对邻接矩阵存储的邻接矩阵存储的图图G进行进行BFS搜索搜索void BFSM(MGraph *G,int k) int i, j; CirQueue *Q; InitQueue(Q); printf(visit vertex:V%cn, G-vexsk); /*访问原点vk*/ visitedk = TRUE; EnQueue(Q, k); /*原点vk入队列*/ while (!QueueEmpty(Q) i = DeQueue(Q); /*vi出队列*/ for (j=0; jn; j+) /*依次搜索vi的邻接点vj*/ if (G-edg

43、esij=1 & !visitedj) /*若vj未访问*/ printf(visit vertex:V%cn, G-vexsj); /*访问vj */ visitedj = TRUE; EnQueue(Q, j); /*访问过的vj入队列*/ 算法的算法的时间复杂度为时间复杂度为O(n2)。如果。如果采用邻接表采用邻接表作为存储结构，所需作为存储结构，所需时间复杂度为时间复杂度为O(n+e)。2022-3-259练习题 1. 连通分量是无向图中的极小连通子图。连通分量是无向图中的极小连通子图。( ) 2.强连通分量是有向图中的极大强连通子图。强连通分量是有向图中的极大强连通子图。(

44、) 3. N条边的无向图的邻接表的存储中，边表的个数有条边的无向图的邻接表的存储中，边表的个数有（ ）。）。 A）N B）2N C）N/2 D）N*N 4.对于如图所示的有向图，试给出对于如图所示的有向图，试给出 （1）每个顶点的入度和出度；）每个顶点的入度和出度； （2）邻接矩阵；）邻接矩阵； （3）邻接表；）邻接表； （4) 强连通分量强连通分量 2022-3-260 5.设无向图设无向图G如图所示如图所示 求求 （1）该图的邻接矩阵；）该图的邻接矩阵； （2）该图的邻接表；）该图的邻接表； （3）从）从V0出发的出发的“深度优先深度优先”遍历序列；遍历序列； （4）从）从V0出发的出发的

45、“广度优先广度优先”遍历序列。遍历序列。2022-3-26117823456(a)17823456(b)17823456(c)2022-3-262按照生成树的定义，按照生成树的定义，n 个顶点的连通网络的生成树有个顶点的连通网络的生成树有 n 个顶个顶点、点、n- -1 条边。条边。而所有包含而所有包含n-1 n-1 条边及条边及n n个顶点的连通图都个顶点的连通图都是无回路的树，所以是无回路的树，所以生成树是连通图中的极小连通子图生成树是连通图中的极小连通子图. . 由于使用不同的遍历图的方法，可以得到不同的生成树；从由于使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能

46、得到不同的生成树。如深度优先生成不同的顶点出发，也可能得到不同的生成树。如深度优先生成树、广度优先生成树树、广度优先生成树 在图论中，常常将树定义为一个无回路连通图。在图论中，常常将树定义为一个无回路连通图。 对于一个带权的无向连通图，其每个生成树所有边上的权对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把值之和可能不同，我们把所有边上权值之和最小的生成树所有边上权值之和最小的生成树称为称为图的图的最小生成树最小生成树。求图的最小生成树有很多实际应用。例如，。求图的最小生成树有很多实际应用。例如，通讯线路铺设造价最优问题就是一个最小生成树问题。通讯线路铺设造价最优问题就

47、是一个最小生成树问题。2022-3-263 假设把假设把n n个城市看作图的个城市看作图的n n个顶点，边表示两个城市之间的线个顶点，边表示两个城市之间的线路，每条边上的权值表示铺设该线路所需造价。铺设线路连接路，每条边上的权值表示铺设该线路所需造价。铺设线路连接n n个城市，但不形成回路，这实际上就是图的生成树，而以最少个城市，但不形成回路，这实际上就是图的生成树，而以最少的线路铺设造价连接各个城市，即求线路铺设造价最优问题，的线路铺设造价连接各个城市，即求线路铺设造价最优问题，实际上就是在图的生成树中选择权值之和最小的生成树。构造实际上就是在图的生成树中选择权值之和最小的生成树。构造最小生

48、成树的算法有很多，下面分别介绍克鲁斯卡尔最小生成树的算法有很多，下面分别介绍克鲁斯卡尔( (Kruskal)Kruskal)算法和普里姆算法和普里姆( (Prim)Prim)算法。算法。 克鲁斯卡尔算法是一种按权值递增的次序选择合适的边来构造最克鲁斯卡尔算法是一种按权值递增的次序选择合适的边来构造最小生成树的方法。小生成树的方法。2022-3-2642022-3-265 假设假设G=（V，E）是一个具有是一个具有n个顶点的带权无个顶点的带权无向连通图，向连通图，T= (U，TE)是是G的最小生成树，其中的最小生成树，其中U是是T的顶点集，的顶点集，TE是是T的边集，则构造最小生成树的过程如下：

49、的边集，则构造最小生成树的过程如下：(1) 置置U的初值等于的初值等于V，TE的初值为空集；的初值为空集；(2) 按权值从小到大的顺序依次选取图按权值从小到大的顺序依次选取图G中的边，若选取的边未使中的边，若选取的边未使生成树生成树T形成回路，则加入形成回路，则加入TE；若选取的边使生成树若选取的边使生成树T形成回路，形成回路，则将其舍弃。循环执行则将其舍弃。循环执行(2)，直到，直到TE中包含中包含(n-1)条边为止。条边为止。 2022-3-266为实现克鲁斯卡尔算法需要设置一维辅助数组为实现克鲁斯卡尔算法需要设置一维辅助数组E，按权值从小到大按权值从小到大的顺序存放图的边，数组的下标取值

50、从的顺序存放图的边，数组的下标取值从0到到e-1（e为图为图G边的数边的数目）。目）。 假设数组假设数组E存放图存放图G中的所有边，且边已按权值从小到大的顺序排中的所有边，且边已按权值从小到大的顺序排列。列。n为图为图G的顶点个数，的顶点个数，e为图为图G的边数。克鲁斯卡尔算法如下：的边数。克鲁斯卡尔算法如下：typedef struct int vex1; /边的起始顶点边的起始顶点int vex2; /边的终止顶点边的终止顶点int weight; /边的权值边的权值Edge; 2022-3-267 Void kruskal(Edge E,int n,int e) int i,j,m1,m

51、2,sn1,sn2,k; int vsetMAXV; /用于记录顶点是否属于同一集合的辅助数组用于记录顶点是否属于同一集合的辅助数组 for(i=0;in;i+) vseti=i; /初始化辅助数组初始化辅助数组 k=0; /表示当前构造最小生成树的第表示当前构造最小生成树的第k条边，初值为条边，初值为0 for(j=0;je;j+) /生成的边数小于生成的边数小于e时继续循环时继续循环 ml=Ej.vex1;m2=Ej.vex2; /取一条边的两个邻接点取一条边的两个邻接点 sn1=vsetm1;sn2=vsetm2; /分别得到两个顶点所属的集合编号分别得到两个顶点所属的集合编号 if(s

52、n1!=sn2) /两顶点分属于不同的集合，该边是最小生成树的一条边两顶点分属于不同的集合，该边是最小生成树的一条边 printf(“(%d，%d)：dn”,m1,m2,Ej.weight); k+; /生成边数增生成边数增l if(k=n-1) break; for(i=0;in;i+) if (vseti=sn1) vseti=sn2; /修改集合编号相同修改集合编号相同 2022-3-268 如果给定带权无向连通图如果给定带权无向连通图G有有e条边，且边已经条边，且边已经按权值递增的次序存放在数组按权值递增的次序存放在数组E中，则用克鲁斯卡尔中，则用克鲁斯卡尔算法构造最小生成树的时间复杂

53、度为算法构造最小生成树的时间复杂度为O (e)。克鲁斯卡克鲁斯卡尔算法的时间复杂度与边数尔算法的时间复杂度与边数e有关，该算法适合于求有关，该算法适合于求边数较少的带权无向连通图的最小生成树。边数较少的带权无向连通图的最小生成树。 2022-3-2692022-3-270Prim算法构造最小生成树的过程示意2022-3-271假设假设G=(VG=(V，E)E)是一个具有是一个具有n n个顶点的带权无向连通图，个顶点的带权无向连通图，T(UT(U，TE)TE)是是G G的最小生成树，其中的最小生成树，其中U U是是T T的顶点集，的顶点集，TETE是是T T的边集，则构造的边集，则构造G G的最

54、的最小生成树小生成树T T的步骤如下：的步骤如下： （1 1）初始状态，）初始状态，TETE为空，为空，U=vU=v0 0 ，v v0 0VV； （2 2）在所有在所有uUuU，vV-UvV-U的边的边( (u u，v) Ev) E中找一条代价最小的边中找一条代价最小的边( (uu，v)v)并入并入TETE，同时将同时将vv并入并入U U；重复执行步骤（重复执行步骤（2 2）n-1n-1次，直到次，直到U=VU=V为止。为止。 2022-3-27201234562413102758461structint adjvex;int lowcost; closedgeMAX_VERTEX_NUM;2

55、022-3-273 iclosedge123456adjvexlowcost0204012022-3-274 iclosedge123456UV-Ukadjvexlowcostv02v04v01v0v1,v2,v3,v4,v5,v63adjvexlowcostv02v320v37v38v34v0,v3v1,v2,v4,v5,v61adjvexlowcost0v320v37v38v34v0,v3,v1v2,v4,v5,v62adjvexlowcost000v37v25v34v0,v3,v1,v2 v4,v5,v66adjvexlowcost000v66v610v0,v3,v1,v2,v6 v4,

56、v5 5adjvexlowcost000v6600v0,v3,v1,v2,v6,v5 v4 4adjvexlowcost000000v0,v3,v1,v2,v6,v5,v4 42022-3-275structint adjvex;int lowcost; closedgeMAXVERTEXNUM;void Prim(MGraph G,int v) /*G为图的邻接矩阵存储，为图的邻接矩阵存储，v是第一个进入集合是第一个进入集合U中的顶点的序号中的顶点的序号*/int k,j,i,minCost;closedgev.lowcost=0;for (j=0;jG.n;j+) /*初始化初始化clos

57、edge数组数组*/ if (j!=v) closedgej.adjvex=v;closedgej.lowcost=G.edgesvj; 2022-3-276for (i=1;iG.n;i+) /*依次将顶点加入到集合依次将顶点加入到集合U中中*/ for(j=0;jG.n;j+) /*定位第一个没有加入到定位第一个没有加入到U中的顶点中的顶点*/ if(closedgej.lowcost!=0) k=j; break; /*定位定位V-U集合中集合中lowcost值最小的顶点值最小的顶点*/ minCost=closedgek.lowcost; for (j=0;jG.n;j+) /*查找权

58、值最小的边查找权值最小的边*/ if (closedgej.lowcost minCost & closedgej.lowcost!=0) minCost=closedgej.lowcost;k=j; 2022-3-277 /*输出新加入到树中的边输出新加入到树中的边*/ printf(%c,%c)n,closedgek.adjvex,G.vexsk); closedgek.lowcost=0; /*将该顶点加入到集合将该顶点加入到集合U*/for (j=0;jG.n;j+) /*更新更新closedge数组的内容数组的内容*/ if (G. edgeskjclosedgej.lowc

59、ost) closedgej.adjvex=G.vexsk;closedgej.lowcost=G.edgeskj; /*for循环执行完毕，所有顶点均加入最小生成树循环执行完毕，所有顶点均加入最小生成树*/ /*算法结束算法结束*/2022-3-278普里姆算法中的第二个普里姆算法中的第二个forfor循环语句频度为循环语句频度为n-n-1 1，其中包含的两个内循环频度也都为其中包含的两个内循环频度也都为n-1n-1，因此因此普里姆算法的时间复杂度为普里姆算法的时间复杂度为O(nO(n2 2) )。普里姆算法的普里姆算法的时间复杂度与边数时间复杂度与边数e e无关，该算法更适合于求边数无关，

60、该算法更适合于求边数较多的带权无向连通图的最小生成树。较多的带权无向连通图的最小生成树。 2022-3-279 交通网络中常常提出这样的问题：从甲地到乙地之间是否交通网络中常常提出这样的问题：从甲地到乙地之间是否有公路连通有公路连通? ? 在有多条通路的情况下，哪一条路最短在有多条通路的情况下，哪一条路最短? ? 交通网络可用带权图来表示交通网络可用带权图来表示。顶点顶点表示表示城市名称城市名称，边边表示表示两个两个城市有路连通城市有路连通，边上，边上权权值可表示值可表示两城市之间的距离两城市之间的距离、交通交通费费或途中或途中所花费的时间所花费的时间等。求等。求两个顶点之间的最短路径两个顶点之间的最短路径，不是，不是指路径上边数之和最少，而是指路径上边数之和最少，而是指路径上各