数据结构__图的基本知识点

1、第第8章图章图2022年3月17日第第8章图章图一、一、现实中的图现实中的图8.1 8.1 图的基本概念图的基本概念 图最常见的应用是在交通运输和通信网络中找出造价图最常见的应用是在交通运输和通信网络中找出造价最低的方案。通信网络示例如下图所示：最低的方案。通信网络示例如下图所示： 图图G是由一个是由一个顶点集顶点集V和一个和一个边边集集E构成的数据结构。构成的数据结构。记为二元组形式：记为二元组形式： G= (V, E)其中其中: V是由顶点构成的是由顶点构成的非空非空有限集合，记为：有限集合，记为：VV0, V1, V2, Vn-1 E是由是由V中顶点的对偶构成的有限集合，记为：中顶点的对

2、偶构成的有限集合，记为：E=(V0, V2), (V3, V4), ，若若E为空，则图中只有顶点而没有边为空，则图中只有顶点而没有边。其中对偶可以表示成：其中对偶可以表示成： (Vi, Vj)无序的对偶称为无序的对偶称为边边，即，即(Vi, Vj)=(Vj, Vi) ，其图称为，其图称为无向图无向图 有序的对偶称为有序的对偶称为弧弧，即，即 ，则称，则称Vi为弧尾为弧尾，称，称Vj为弧头为弧头，该图称为，该图称为有向图有向图二、二、图的定义图的定义有向图和无向图示例：有向图和无向图示例： 无向图无向图G1的二元组表示：的二元组表示：V(G1)=V1, V2, V3, V4E(G1)=(V1,

3、V2)，(V1, V3)，(V1, V4)，(V2, V3)，(V2, V4)，(V3, V4)有向图有向图G3的二元组表示：的二元组表示： V(G3)=V1, V2, V3 E(G3)=，l 在无向图中，若存在一条边（在无向图中，若存在一条边（Vi, Vj），则称），则称Vi和和Vj互为互为（Adjacent）l 在有向图中，若存在一条弧在有向图中，若存在一条弧，则称，则称Vi为此为此弧的弧的起点，起点，称称Vj为此弧的为此弧的终点，终点，称称Vi邻接到邻接到Vj，Vj邻接自邻接自Vi，Vi和和Vj互为邻接点互为邻接点。 2顶点的度、入度和出度顶点的度、入度和出度l 在无向图中，与顶点在无向

4、图中，与顶点v相邻接的边数称为相邻接的边数称为该顶点的该顶点的度度，记为，记为D(v)。l 在有向图中，顶点在有向图中，顶点v的度又分为的度又分为入度入度和和出度出度两种：两种：以顶点以顶点v为终点为终点(弧头弧头)的弧的数目称为顶点的弧的数目称为顶点v的的入度入度，记，记为为ID(v)；以顶点以顶点v为起点为起点(弧尾弧尾)的弧的数目称为顶点的弧的数目称为顶点v的的出度出度，记，记为为OD(v)；有向图顶点有向图顶点v的度为该顶点的入度和出度之和，即的度为该顶点的入度和出度之和，即 D(v)=ID(v)+OD(v)l 无论是有向图还是无向图，一个图的顶点数无论是有向图还是无向图，一个图的顶点

5、数n n、边、边( (弧弧) )数数e e和每个顶点的度和每个顶点的度d di i之间满足以下的关系式：之间满足以下的关系式：11()2niieD vl 即在有向图或无向图中：即在有向图或无向图中：所有顶点度数之和所有顶点度数之和 ：边数：边数 = 2 = 2 ：1 13完全图、稠密图和稀疏图完全图、稠密图和稀疏图l 在图在图G中：中：若若G为无向图，任意两个顶点之间都有一条边，称为无向图，任意两个顶点之间都有一条边，称G为为无无向完全图向完全图。顶点数为。顶点数为n，无向完全图的边数：，无向完全图的边数： e=Cn2 =n(n 1)/2若若G为有向图，任意两个顶点为有向图，任意两个顶点Vi,

6、 Vj之间都有弧之间都有弧 、 ，称，称G为为有向完全图有向完全图。如顶点数为。如顶点数为n，有向完全图，有向完全图的弧数：的弧数： e=Pn2 =n(n 1)l 例如，无向图例如，无向图G1就是就是4个顶点无向完全图。个顶点无向完全图。l 若一个图接近完全图，则称其为若一个图接近完全图，则称其为；反之，若一个图含；反之，若一个图含有很少条边或弧（即有很少条边或弧（即en2），则称其为），则称其为。l 若有图若有图G=(V, E)和和G=(V, E) l 且且V 是是V的子集，即的子集，即V V ， E是是E的子集，即的子集，即 E El 则称图则称图G为图为图G的子图。的子图。 5路径、回路

7、和路径长度路径、回路和路径长度l 在无向图在无向图G中，若存在一个顶点序列中，若存在一个顶点序列(Vp , Vi1 , Vi2 , , Vin , Vq)，使使(Vp, Vi1)，(Vi1, Vi2)，(Vin, Vq)均为图均为图G的边，则该称顶的边，则该称顶点的序列为顶点点的序列为顶点Vp到顶点到顶点Vq的的路径路径。若。若G是有向图，则路径是有向图，则路径是有向的。是有向的。l 路径长度路径长度定义为路径上的边数或者弧的数目。定义为路径上的边数或者弧的数目。l 若一条路径中不出现重复顶点，则称此路径为若一条路径中不出现重复顶点，则称此路径为简单路径简单路径。l 若一条路径的起点和终点相同

8、（若一条路径的起点和终点相同（Vp=Vq）称为）称为回路回路或或环环。l 除了起点和终点相同外，其余顶点不相同的回路，称为除了起点和终点相同外，其余顶点不相同的回路，称为简单简单回路回路或或简单环简单环。l 例如，在无向图例如，在无向图G1中：中：顶点序列（顶点序列（V1, V2, V3, V4）是一条从顶点）是一条从顶点V1到顶点到顶点V4，长度为，长度为3的的简单路径简单路径；顶点序列（顶点序列（V1, V2, V4, V1, V3）是一条从顶点）是一条从顶点V1到到顶点顶点V3，长度为，长度为4的的路径路径，但不是简单路径；，但不是简单路径；顶点序列（顶点序列（V1, V2, V3, V

9、1）是一条长度为）是一条长度为3的的简单简单回路回路。l 在有向图在有向图G3中：中：顶点序列（顶点序列（V2, V3, V2）是一个长度为）是一个长度为2的的有向简单有向简单环环。6连通、连通分量和连通图、生成树连通、连通分量和连通图、生成树l 在无向图在无向图G中：中：如果从顶点如果从顶点Vi 到顶点到顶点Vj至少有一条路径，则称至少有一条路径，则称Vi与与Vj是是连通连通的。的。如果图中任意两个顶点都连通，则称如果图中任意两个顶点都连通，则称G为为连通图连通图，否则称为，否则称为非连通图。非连通图。在非连通图在非连通图G中，任何一个中，任何一个极大连通子图极大连通子图称为称为G的的连通分

10、量连通分量。任何连通图的连通分量只有一个，即其自身，而非连通图有任何连通图的连通分量只有一个，即其自身，而非连通图有多个连通分量。多个连通分量。在一个连通图中，在一个连通图中，含有全部顶点的极小含有全部顶点的极小(边数最少边数最少)连通子图连通子图，称为该连通图的称为该连通图的生成树生成树。(包含图的所有包含图的所有 n 个结点，但只含个结点，但只含图的图的 n-1 条边。在生成树中添加一条边之后，必定会形成回条边。在生成树中添加一条边之后，必定会形成回路或环路或环)l 非连通图非连通图G4G4A AB BC CD DE EF FG GI IJ JK KA AB BC CD DE EI IJ

11、JK KF FG Gl 图图G1G1和和G2G2为连通图为连通图l 非连通图非连通图G4G4的三个连通分量的三个连通分量l 连通图连通图G5G5A AB BC CD Dl 连通图连通图G5G5的两棵生成树的两棵生成树A AB BC CD DA AB BC CD D7强连通、强连通分量和强连通图强连通、强连通分量和强连通图l 在有向图在有向图G中：中：存在从顶点存在从顶点Vi 到顶点到顶点Vj的路径，也存在从顶点的路径，也存在从顶点Vj 到顶点到顶点Vi的路径，则称的路径，则称Vi与与Vj是是强连通强连通的。的。如果图中任意两个顶点都是强连通，则称如果图中任意两个顶点都是强连通，则称G为为强连通

12、图强连通图，否则称为否则称为非强连通图。非强连通图。在非强连通图在非强连通图G中，任何一个中，任何一个极大强连通子图极大强连通子图称为称为G的的强连强连通分量通分量。任何强连通图的强连通分量只有一个，即其自身，而非强任何强连通图的强连通分量只有一个，即其自身，而非强连通图有多个强连通分量。连通图有多个强连通分量。有向图有向图G G和强连通分量示例：和强连通分量示例： 8权、带权图、有向网和无向网权、带权图、有向网和无向网l 在一个图中，各边在一个图中，各边(或弧或弧)上可以带一个数值，这个数值称为上可以带一个数值，这个数值称为权权。l 这种每条边都带权的图称为这种每条边都带权的图称为8.2 图

13、的基本存储结构图的基本存储结构 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 3a ij=0 vi与与vj无边无边1 vi与与vj有边有边a ij=0 vi到到vj无弧无弧1 vi到到vj有弧有弧a ij=或或0 vi与与vj无边（或无边（或vi到到vj无弧）无弧）w vi与与vj有边（或有边（或vi到到vj有弧）有弧）W 表示边上的权值；表示边上的权值； 0 表示表示vi与与vj是同一个顶点是同一个顶点 表示一个计算机允许的、大于所有边上权值的数。表示一个计算机允许的、大于所有边上权值的数。 邻接矩阵表示邻接矩阵表示

14、0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0V1V2 V4 V5 V3 V1V2 V4 V5 V3 254311邻接矩阵表示邻接矩阵表示0 2 4 2 0 1 5 1 0 3 1 4 3 0 5 1 0 V1V2V3V4V5V1V2V3V4V5V1V2V3V4V5V1V2V3V4V5V1V2 V3 V4 0 1 1 00 0 0 00 0 0 11 0 0 0邻接矩阵表示邻接矩阵表示V1V2V3V4V1V2V3V4 容易实现图的操作，如：求某顶点的度、判断顶点之间是否容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等

15、。有边（弧）、找顶点的邻接点等等。 n n个顶点需要个顶点需要n n* *n n个单元存储边个单元存储边( (弧弧););空间效率为空间效率为O(nO(n2 2) )。 对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。邻接矩阵法邻接矩阵法优点：优点：邻接矩阵法邻接矩阵法缺点：缺点：2、邻接矩阵法、邻接矩阵法特点特点# define MAX 100 /* MAX为图中顶点最多个数为图中顶点最多个数 */typedef int vextype; /* vextype为顶点的数据类型为顶点的数据类型 */typedef struct vextype vexMAX; /* 一维数组存储顶点信息一维

16、数组存储顶点信息 */ int arcMAXMAX; /*邻接矩阵存储边（弧）信息邻接矩阵存储边（弧）信息 */ int vn, en; /* vn顶点数和顶点数和en边数边数 */MGraph; /* 图类型图类型 */注：注：MGraph 既可以表示有向图、无向图，也可以表示有既可以表示有向图、无向图，也可以表示有整型权的网整型权的网例：建一个如图所示的无向图例：建一个如图所示的无向图013420 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0void CreateGraph(MGraph *g) int i, j, v, e; scanf(%d %

17、d, &g-vn, &g-en); /*输入顶点数和边数输入顶点数和边数*/ for(v=0;vvn;v+) scanf(%d, &g-vexv); /*顶点数据输入顶点数据输入*/ for(i=0;ivn;i+) for(j=0;jvn;j+) g-arcij=0; /*邻接矩阵的初始值都为邻接矩阵的初始值都为0*/ for(e=0;een;e+) /*共有共有g-en条边条边*/ scanf(%d %d, &i, &j); /*指明有边的两个顶点的序号指明有边的两个顶点的序号*/ g-arcij=1; /*有边赋值为有边赋值为1*/ g-arcji=

18、1; /*建有向图时此句不要建有向图时此句不要*/ 邻接表表示邻接表表示V1V2 V4 V5 V3 V1V2 V4 V5 V3 254311邻接表表示邻接表表示V1V2V3V4V501234130420212143V1V2V3V4V501234123402452111413304231521与顶点与顶点V1相邻接的顶点相邻接的顶点在数组中的下标在数组中的下标权值权值V1V2 V3 V4 邻接表表示邻接表表示12V1V2V3V4012330以顶点以顶点V1为始点的弧的终点为始点的弧的终点顶点在数组中的下标顶点在数组中的下标邻接表的邻接表的缺点：缺点：邻接表的邻接表的优点：优点：空间效率高；空间效

19、率高；容易寻找顶点的邻接点；容易寻找顶点的邻接点；判断任意两顶点间是否有边或弧，需搜判断任意两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵索两结点对应的单链表，没有邻接矩阵方便。方便。2、邻接表法、邻接表法特点特点adjvexnext表结点：表结点：adjvexnextw邻接点序号邻接点序号(下标下标)下一个邻接下一个邻接点地址点地址权值权值表结点类型表结点类型vertexfirstarc顶点结点：顶点结点：顶点信息顶点信息链表头指针链表头指针(指向第一个表结点指向第一个表结点)顶点结点类型顶点结点类型顶点结点所在数组顶点结点所在数组例：建一个如图所示的有向图例：建一个如图所示的

20、有向图01 2 3120123012330void CreateAGraph(ALGraph *g) int i, j, v, e; ArcNode* p; scanf(%d %d, &g-vn, &g-en); /*输入顶点数和边数输入顶点数和边数*/ for(v=0;vvn;v+) /*顶点数组元素值的获得顶点数组元素值的获得*/ scanf(%d,&g-adjlistv.vertex); /*顶点数据键盘输入顶点数据键盘输入*/ g-adjlistv.firstarc=NULL; for(e=0;een;e+) /*共有共有g-en条边条边*/ scanf(%d

21、%d, &i, &j); /*i j有弧，有弧，i、j为顶点序号为顶点序号*/ p=(ArcNode*)malloc(sizeof(ArcNode); p-adjvex=j; /*把值为把值为j的结点头插入到的结点头插入到i顶点的链表中顶点的链表中*/ p-next=g-adjlisti.firstarc; g-adjlisti.firstarc=p; 0 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3BACDFE补例：图的邻接表存储表示补例：图的邻接表存储表示有向图的邻接表有向图的邻接表1 4230 120 1 2 3 4 A B C

22、 D EABECD可见，在有向图的邻接表中不易找到指向该顶点的弧ABECD有向图的逆邻接表有向图的逆邻接表A B C D E 303420 01234在有向图的逆邻接表中，对每个顶点，链接的是指向该顶点的弧 8.3 图的遍历图的遍历 从图中某个顶点出发遍历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。图的遍历有两种方法： 深度优先搜索遍历（DFS） 广度优先搜索遍历（BFS）。它们对无向图和有向图都适用。 8.3.1 连通图的深度优先搜索遍历连通图的深度优先搜索遍历l 首先访问初始出发点首先访问初始出发点V V0 0，并将其标记设置为已访问；，并将其标记设置为已访问；l 然后任

23、选一个与然后任选一个与V V0 0相邻接且没有被访问的邻接点相邻接且没有被访问的邻接点V V1 1作为新的作为新的出发点，访问出发点，访问V V1 1之后，将其标记设置为已访问；之后，将其标记设置为已访问；l 再以再以V V1 1为新的出发点，继续进行深度优先搜索，访问与为新的出发点，继续进行深度优先搜索，访问与V V1 1相相邻接且没有被访问的任一个顶点邻接且没有被访问的任一个顶点V V2 2；l 重复上述过程，若遇到一个所有邻接点均被访问过的顶点，重复上述过程，若遇到一个所有邻接点均被访问过的顶点，则回到已访问顶点序列中最后一个还存在未被访问的邻接点则回到已访问顶点序列中最后一个还存在未被

24、访问的邻接点的顶点，再从该顶点出发继续进行深度优先搜索，直到图中的顶点，再从该顶点出发继续进行深度优先搜索，直到图中所有顶点都被访问过，搜索结束。所有顶点都被访问过，搜索结束。 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4例例l序列序列1： V0,V1,V3,V7,V4,V2,V5,V6l从从v0出发的出发的DFS序列为：序列为：由于没有规定由于没有规定访问邻接点的顺序，访问邻接点的顺序，DFSDFS序列不是唯一的序列不是唯一的l序列序列2： V0,V1,V4,V7,V3,V2,V

25、5,V6算法描述：算法描述： 访问开始顶点（如访问开始顶点（如 v）；）； 寻找寻找 v 顶点未被访问的第一个邻接顶点（如顶点未被访问的第一个邻接顶点（如 w）；）； 并把并把 w 作为开始顶点继续深度优先搜索遍历（递归思想）；作为开始顶点继续深度优先搜索遍历（递归思想）； 直到所有顶点被访问；直到所有顶点被访问； 其中处理：其中处理：（1）访问顶点：自定义访问函数）访问顶点：自定义访问函数 visit()（2）未被访问的邻接点：定义一个标记数组：）未被访问的邻接点：定义一个标记数组：int visitedMAX visitedi= 0 i号顶点号顶点未未被访问被访问 1 i号顶点号顶点已已被

26、访问被访问 注意：由于函数是递归的，数组定义成外部数组注意：由于函数是递归的，数组定义成外部数组 （3）第一个邻接点：按邻接距阵或邻接表中边存储的顺序）第一个邻接点：按邻接距阵或邻接表中边存储的顺序 函数实现：函数实现：形参：形参：图变量地址，开始顶点的序号（下标）图变量地址，开始顶点的序号（下标）返回值：返回值：无无void dfs(MGraph *g, int v) int j, w; visit(g, v); /*访问访问v号顶点号顶点*/ visitedv=1; /*v号顶点为已访问号顶点为已访问*/ for(j=0; jvn; j+) /*找所有的邻接顶点找所有的邻接顶点*/ if(

27、 g-arcvj=1 & visitedj=0) /*v号顶点与号顶点与j号顶点号顶点 间有边，且间有边，且j号顶点为被访问号顶点为被访问*/ w=j; dfs(g, w); 邻接距阵存储结构的图邻接距阵存储结构的图起始顶点的序号（下标）起始顶点的序号（下标）void visit (MGraph *g, int v) printf(n %d, g-vexv); 按算法实现的按算法实现的dfs遍历举例：遍历举例：V0顶点出发遍历结果（唯一）顶点出发遍历结果（唯一） ：V0、 V1、 V2、 V3、 V4V2顶点出发遍历结果（唯一）顶点出发遍历结果（唯一） ：V2、 V1、 V0、 V4、

28、 V3V0V1V2V3V4无向图：无向图：0101110110010101110110010邻接矩阵存储结构：邻接矩阵存储结构：V0V1V2V3V401234设计程序创建邻接矩阵的无向图，并用设计程序创建邻接矩阵的无向图，并用dfsdfs图中顶点图中顶点信息并输出：信息并输出：宏定义及数据类型：宏定义及数据类型：#include #define MAX 20 /*图顶点最多不超过图顶点最多不超过20*/typedef int vextype; /*图顶点为图顶点为int型型*/typedef struct vextype vexMAX; int arcMAXMAX; int vn, en; M

29、Graph; /*邻接矩阵图类型邻接矩阵图类型*/int visitedMAX; /*访问标记数组访问标记数组*/函数定义：函数定义：void CreateGraph(MGraph *g) /*创建无向图创建无向图*/ void visit(MGraph *g, int v) /*访问图中某个顶点访问图中某个顶点*/ void dfs(MGraph *g, int v) /*dfs遍历图遍历图*/ main() /*主函数主函数*/ MGraph mg; /*mg为图结构变量为图结构变量/ int i, start; /*start开始顶点序号开始顶点序号*/ CreateGraph(&

30、;mg); for(i=0; iadjlistw.firstarc; /*w号顶点的第一个邻接点地址号顶点的第一个邻接点地址*/ 邻接表存储结构的图邻接表存储结构的图起始顶点的序号（下标）起始顶点的序号（下标）while(p!=NULL) i=p-adjvex; /*i为邻接顶点的序号（下标）为邻接顶点的序号（下标）*/ if(visitedi=0) EnQueue(&Q, i); visitedi=1; p=p-next; /*找所有未访问的邻接点的循环找所有未访问的邻接点的循环*/ /*队列循环队列循环*/ /*函数结束函数结束*/按算法实现的按算法实现的bfs遍历举例：遍历举例：

31、V0顶点出发遍历结果（唯一）顶点出发遍历结果（唯一） ：V0、 V1、 V4、 V3、 V2V2顶点出发遍历结果（唯一）顶点出发遍历结果（唯一） ：V2、 V3、 V1、 V4、 V0V0V1V2V3V4无向图：无向图：邻接表存储结构：邻接表存储结构：V0V1V2V3V4012341403312403设计程序创建邻接表存储的无向图，并用设计程序创建邻接表存储的无向图，并用bfsbfs图中顶图中顶点信息并输出：点信息并输出：宏定义及数据类型：宏定义及数据类型：#include #include Queue.h /*循环队列相关操作的定义文件循环队列相关操作的定义文件*/#define MAX 2

32、0 /*图顶点最多不超过图顶点最多不超过20*/typedef int vextype; /*图顶点为图顶点为int型型*/typedef struct arcnode int adjvex; struct arcnode *next; ArcNode; /*表结点类型表结点类型*/typedef struct vexnode vextype vertex;ArcNode *firstarc; VexNode; /*顶点结点类型顶点结点类型*/typedef struct VexNode adjlistMAX; /*顶点结点所在数组顶点结点所在数组*/ int vn, en; ALGraph;

33、 /*邻接表存储的图类型邻接表存储的图类型*/int visitedMAX; /*访问标记数组访问标记数组*/函数定义：函数定义：void CreateGraph(ALGraph *g) /*创建图创建图*/ void visit(MGraph *g, int v) /*访问图中某个顶点访问图中某个顶点*/ void bfs(MGraph *g, int v) /*bfs遍历图遍历图*/ main() /*主函数主函数*/ ALGraph alg; /*mg为邻接表图结构变量为邻接表图结构变量/ int i, start; /*start开始顶点序号开始顶点序号*/ CreateGraph(&

34、amp;alg); for(i=0; ialg.vn; i+) /*访问标记数组置初值访问标记数组置初值0*/ visitedi=0; scanf(%d, &start); bfs(&alg, start);l关于遍历小结：关于遍历小结：若图是连通的或强连通的，则从图中某一个若图是连通的或强连通的，则从图中某一个顶点出发可以访问到图中所有顶点；顶点出发可以访问到图中所有顶点；若图是非连通的或非强连通图，则需从图中若图是非连通的或非强连通图，则需从图中多个顶点出发搜索访问，而每一次从一个新多个顶点出发搜索访问，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访的起始点出发进行

35、搜索过程中得到的顶点访问序列恰为每个连通分量中的顶点集。问序列恰为每个连通分量中的顶点集。问题：如何通过遍历算法，求一个非连通图的连问题：如何通过遍历算法，求一个非连通图的连同分量个数？同分量个数？int count (MGraph *g) int i, m=0; for(i=0; ivn; i+) if(visitedi=0) m+; dfs(g, i); return m; 生成树定义生成树定义l图的遍历过程中经过的图的遍历过程中经过的n个顶点个顶点n-1条边条边即为一即为一棵生成树。棵生成树。8.4 图的应用图的应用8.4.1 连通图的最小生成树连通图的最小生成树无向图的应用无向图的应用

36、在无向连通图在无向连通图G G中，其一个极小连通子图中，其一个极小连通子图( (无回无回路路) )是是G G的生成树，它含有图中全部的生成树，它含有图中全部n n个顶点个顶点，但，但只有只有n-1n-1条边条边，且不唯一。，且不唯一。深度优先生成树：按深度优先遍历生成的深度优先生成树：按深度优先遍历生成的生成树生成树c0c1c3c2c4c5例例c0c1c3c2c4c5c0c1c3c2c4c5c0c1c3c2c4c5广度优先生成树：按广度优先遍历生成的广度优先生成树：按广度优先遍历生成的生成树生成树非连通图的生成森林非连通图的生成森林V0V1V3V4V2V6V8V7V5V9（a）不连通的无向图）

37、不连通的无向图G12V0V1V3V4V2V8V7V9V6V5（c）图）图G12的一个的一个BFS生成森林生成森林V0V1V3V4V2V6V8V7V5V9（b）图）图G12的一个的一个DFS生成森林生成森林 要在要在 n 个城市间建立个城市间建立通讯网，如何在保证通讯网，如何在保证 n 个城市连通的前题下最节个城市连通的前题下最节省经费省经费? ABCDEF101015121287665无向网无向网G1ABCDEF10101276花费：花费：45ABCDEF1512865花费：花费：465ABCDEF107610花费：花费：38 要在要在 n 个城市间建立个城市间建立通讯网，如何在保证通讯网，如

38、何在保证 n 个城市连通的前题下最节个城市连通的前题下最节省经费省经费? ABCDEF101015121287665这个问题实际上是连通图的最小生成树问这个问题实际上是连通图的最小生成树问题。题。ABCDEF1010151212876655ABCDEF107610最小生成树的定义最小生成树的定义若图若图G G是带权的无向连通图（连通网），生成树上各是带权的无向连通图（连通网），生成树上各边权值之和称为生成树的代价，边权值之和称为生成树的代价，代价最小的生成树代价最小的生成树称为最小生成树；称为最小生成树；ln n个顶点、个顶点、n-1n-1条边、权值之和最小。条边、权值之和最小。1654327

39、131791812752410连通网：连通网：1654321397510生成树生成树1：1654327139724生成树生成树2：代价：代价：44代价：代价：60最小生成树最小生成树最小生成树的应用最小生成树的应用l集成电路布线集成电路布线l通讯线路布线通讯线路布线如何快速有效地构造如何快速有效地构造最小生成树最小生成树 构造最小生成树的准则：构造最小生成树的准则：l必须只使用该网络中的边来构造最小生成树；必须只使用该网络中的边来构造最小生成树；l必须使用且仅使用必须使用且仅使用n-1条边来联接网络中的条边来联接网络中的n个顶点个顶点一、一、Prim(普里姆普里姆)算法算法 1 1、算法思想、

40、算法思想 设原连通网设原连通网G=(V, E)G=(V, E)，生成的最小生成树，生成的最小生成树T=(U, T=(U, TE)TE)，则算法步骤如下：，则算法步骤如下：(1)(1)任选一个顶点任选一个顶点u u0 0放入放入U U中，即初始中，即初始U=uU=u0 0 ，TE= TE= (2)(2)找连接找连接U U与与V-UV-U集合的一条权值最小的边集合的一条权值最小的边即找即找顶点顶点uU,uU,顶点顶点vV-UvV-U的权值最小的一条边的权值最小的一条边(u,v)E(u,v)E；并把顶点并把顶点v v加入到加入到U U中，边中，边(u,v) (u,v) 加入到加入到TETE中，中，即

41、修改即修改U=U+v,TE=TE+(u,v)U=U+v,TE=TE+(u,v)(3)(3)转到（转到（2 2）重复执行，直到）重复执行，直到U=VU=V结束结束ABCDEF101015121287665（a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树BCE101512（b）求解过程）求解过程67ABCDEF1010151212865（a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树CDEF101512765（b）求解过程）求解过程ABCDEF101015121287665 （a）无向网）无向网G1算法演示算法演示:Pri

42、m算法求解最小生成树算法求解最小生成树CDEF1015765（b）求解过程）求解过程6ABCDEF10101512128765 （a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树CEF1015765（b）求解过程）求解过程6ABCDEF10101512128765 （a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树CEF10157665（b）求解过程）求解过程ABCDEF101015121287665 （a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树CE1015765（b）求解过程）求

43、解过程ABCDEF101015121287665 （a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树CE1015765（b）求解过程）求解过程86ABCDEF101015121287665 （a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树CE10101575（b）求解过程）求解过程6ABCDEF101015121287665 （a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树E101075（b）求解过程）求解过程1567ABCDEF101015121287665 （a）无向网）无向网G

44、1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树E1010125（b）求解过程）求解过程67ABCDEF101015121287665 （a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树最小生成树最小生成树E10105例1654326513566425131163141643142116432142516543214253Prim算法最小生成树生成过程事例算法最小生成树生成过程事例(从从1号顶点开始号顶点开始) 课堂练习：写出如下连通网的最小生成树过程课堂练习：写出如下连通网的最小生成树过程16543249610201451010616543

45、2495106最小生成树最小生成树1165432495106最小生成树最小生成树2最小生成树最小生成树不唯一！不唯一！i012345di.adj000000di.dist 01 58 定义一个结构数组：定义一个结构数组：struct cost int adj; int dist;d20;2 2、算法实现、算法实现 02315451839762说明：说明：i i数组下标，又是图中对应数组下标，又是图中对应顶点的序号顶点的序号di.adjdi.adj表示表示i i号顶点号顶点与生成树中顶点集合与生成树中顶点集合U U距离距离最小最小的的顶点顶点号（号（u u）di.distdi.dist表示表示i

46、 i号顶点号顶点与生成树中与生成树中adjadj顶点（顶点（u u号顶点号顶点）的）的距距离离，当，当dist=0dist=0时表示时表示i i号顶点已到生成树中。号顶点已到生成树中。生成树初始生成树初始 选选0号顶点号顶点2 2、算法实现、算法实现 i012345di.adj000000di.dist 01 58 02315451839762(1)(1)取取d d数组中数组中distdist0的最小值，则把的最小值，则把u=0, v=1,w=1送入生成树，送入生成树，其顶点集为：其顶点集为：0,1，并修改数组，并修改数组d的内容的内容i012345di.adj011000di.dist 00

47、2 58 生成树初始生成树初始 选选0号顶点号顶点uvw(2)(2)取取d d数组中数组中distdist0的最小值，则把的最小值，则把u=1, v=2,w=2送入生成树送入生成树，其顶点集为：其顶点集为：0,1,20,1,2，并修改数组并修改数组d的内容的内容i012345di.adj011000di.dist 002 58 i012345di.adj012202di.dist 0007 56 i012345di.adj012202di.dist 0007 56 (3)(3)取取d d数组中数组中distdist0的最小值，则把的最小值，则把u=0, v=4,w=5送入生成树送入生成树，其顶

48、点集为：其顶点集为：0,1,2,40,1,2,4，并修改数组并修改数组d的内容的内容i012345di.adj012442di.dist 0003 06 (4)(4)取取d d数组中数组中distdist0的最小值，则把的最小值，则把u=4, v=3,w=3送入生成树送入生成树，其顶点集为：其顶点集为：0,1,2,4,30,1,2,4,3，并修改数组并修改数组d的内容的内容i012345di.adj012442di.dist 0003 06 i012345di.adj012342di.dist 0000 06 i012345di.adj012342di.dist 0000 06 (5)(5)取

49、取d d数组中数组中distdist0的最小值，则把的最小值，则把u=2, v=5,w=6送入生成树送入生成树，其顶点集为：其顶点集为：0,1,2,4,3,50,1,2,4,3,5，并修改数组并修改数组d的内容的内容i012345di.adj012345di.dist 0000 00 无向网的建立：无向网的建立： #include #define INF 32767typedef struct int u, v, w; Tree; /*最小生成树顺序存储元素类型最小生成树顺序存储元素类型*/void CreateGraph(MGraph *g) int i, j, w, e; FILE *fp

50、; /*文件指针文件指针fp*/ fp=fopen(graph.dat, r); /*打开数据文件打开数据文件*/ /*图的顶点数和边数、顶点数据和边的信息从文件获取图的顶点数和边数、顶点数据和边的信息从文件获取*/ fscanf(fp,%d %d, &g-vn, &g-en); for(i=0;ivn;i+) /*邻接矩阵初始化邻接矩阵初始化*/ for(j=0;jvn;j+) /*对角线为对角线为0，其余为，其余为*/ if(i=j) g-arcij=0; else g-arcij=INF;02315451839762无向网的建立（续）：无向网的建立（续）： for(i=0

51、;ivn;i+) g-vexi=A+i; /*顶点数据为顶点数据为A、B、C*/ for(e=0;een;e+) /*从文件读取对应边信息，即有边的顶点序号及权值从文件读取对应边信息，即有边的顶点序号及权值*/ fscanf(fp, %d %d %d, &i,&j,&w)； g-arcij=w; g-arcji=w; fclose(fp); /*关闭文件关闭文件*/ /*结束函数结束函数*/0968035930767022018510文件文件graph.dat中中的内容为：的内容为：6 80 1 10 4 50 5 81 2 22 3 72 5 63 4 33 5 9无

52、向网邻接距阵的输出：无向网邻接距阵的输出： void OutGraph(MGraph *g) int i, j; printf(n-Graph-n); printf(n vn=%d t en=%d, g-vn, g-en); for(i=0;ivn;i+) for(j=0;jvn;j+) printf(%dt,g-arcij); printf(n); 0968035930767022018510输出：输出：-Graph-6 8primprim算法实现：算法实现： void Prim(MGraph *g, int v0, Tree E) int i,j, k, min; struct cost

53、int adj; int dist; d20; for(i=0;ivn;i+) /*d数组初始化数组初始化*/ di.adj=v0; di.dist=g-arcv0i; for(k=0; kvn-1; k+) /*求求vn-1条生成树的边条生成树的边*/ min=INF; j=-1; for(i=0; ivn; i+) /*找权值最小的边找权值最小的边*/ if(di.dist!=0 & di.distmin) j=i; min=di.dist; Ek.u=dj.adj; Ek.v=j; Ek.w=min; /*送入生成树送入生成树*/ dj.adj=j; dj.dist=0; /*修

54、改新送入生成树顶点的信息修改新送入生成树顶点的信息*/primprim算法实现（续）：算法实现（续）： for(i=0; ivn; i+) /*修改数组修改数组d中数组中数组*/ /*新加入到生成树的新加入到生成树的j顶点与顶点与i顶点边的权值更小，则修改顶点边的权值更小，则修改*/ if(di.dist!=0 & g-arcjiarcji; /*结束求生成树的结束求生成树的for */ /*结束函数结束函数 */最小生成树的输出：最小生成树的输出： void OutTree(Tree E, int k) int i; printf(n spaning treen); for(i=0;

55、 ik; i+) /*生成树生成树E数组中有数组中有k条边条边*/ printf(n%c-%c-%d, Ei.u, Ei.v, Ei.w ); 输出：输出：spaning tree0-1-1 1-2-2 0-4-5 4-3-32-5-6主函数：主函数： main( ) MGraph G; Tree E20; CreateGraph(&G); OutGraph(&G); Prim(&G,0,E); OutTree( E, G.vn-1 ); 二、二、 Kruskal（克鲁斯卡尔）算法（克鲁斯卡尔）算法 1 1、算法思想、算法思想 把图的所有边按其权值从小到大排成升序把图的

56、所有边按其权值从小到大排成升序先把权值最小的边加入生成树先把权值最小的边加入生成树依次选取后面的边，如该边加到生成树中，使生成依次选取后面的边，如该边加到生成树中，使生成树构成回路，则舍弃该边，否则该边加入到生成树树构成回路，则舍弃该边，否则该边加入到生成树中。中。重复上述过程，直到生成树中包含重复上述过程，直到生成树中包含n n 1 1条边为止，条边为止，此时即为最小生成树。此时即为最小生成树。例AFEDCB6314566425AFEDCB13254Kruskal算法最小生成树生成过程事例：算法最小生成树生成过程事例： AC10DF21AD32CF43BE44CD55BC56AB67CE68

57、EF69KruskalKruskal算法练习算法练习: :abcdegf195141827168213ae12dcbgf71485316217121819abcdegf195141827168213ae12dcbgf7148531621最小生成树代价= 14+8+3+5+16+21 = 67 PrimPrim算法练习算法练习: :8.4.2 拓扑排序拓扑排序有向无环图及其应用有向无环图及其应用1、AOV网概念网概念在一个有向图中，若用顶点表示活动，有向边表示活动间在一个有向图中，若用顶点表示活动，有向边表示活动间先后关系，称该有向图叫做顶点活动网络，简称为先后关系，称该有向图叫做顶点活动网络，简称为AOV网。网。l 用用AOV网表示各门课程之间先后关系的实例网表示各门课程之间先后关系的实例C1C2C3C4C6C5C1C2C3C4C6C52、拓扑排序概念、拓扑排序概念从一个从一个无环有向图无环有向图（无环（无环AOV网）中排出一个顶点的序列，网）中排出一个顶点的序列，要求满足：任何一个顶点的前驱在序列中都在其后继的前要求满足：任何一个顶点的前驱在序列中都在其后继的前面出现，则该序列为拓扑排序。面出现，则该序列为拓扑排序。l 以下有向图的拓扑序列为：以下有向图的拓扑序列为：（1）C1、C2、C4、C3、C5、C6（2）C2、C3、C1、C4、C5、C6有环有向图拓扑序列无效