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

第8章图8.1图的基本概念8.2图的基本存储结构8.2.1邻接距阵及其实现8.2.2邻接表及其实现8.3图的遍历8.3.1深度优先搜索遍历8.3.2广度优先搜索遍历8.4图的应用8.4.1连通图的最小生成树8.4.2拓扑排序数据结构--图的基本知识点全文共107页，当前为第1页。一、现实中的图8.1图的基本概念

图最常见的应用是在交通运输和通信网络中找出造价最低的方案。通信网络示例如下图所示：数据结构--图的基本知识点全文共107页，当前为第2页。

图G是由一个顶点集V和一个边集E构成的数据结构。记为二元组形式：G=(V,E)其中:

V是由顶点构成的非空有限集合，记为：V＝{V0,V1,V2,…Vn-1}

E是由V中顶点的对偶构成的有限集合，记为：E={(V0,V2),(V3,V4),…}，若E为空，则图中只有顶点而没有边。其中对偶可以表示成：

(Vi,Vj)—无序的对偶称为边，即(Vi,Vj)=(Vj,Vi)，其图称为无向图

<Vi,Vj>—有序的对偶称为弧，即<Vi,Vj>≠<Vj,Vi>，则称Vi为弧尾，称Vj为弧头，该图称为有向图二、图的定义数据结构--图的基本知识点全文共107页，当前为第3页。有向图和无向图示例：无向图G1的二元组表示：V(G1)={V1,V2,V3,V4}E(G1)={(V1,V2)，(V1,V3)，(V1,V4)，(V2,V3)，(V2,V4)，(V3,V4)}有向图G3的二元组表示：

V(G3)={V1,V2,V3}E(G3)={<V1,V2>，<V1,V3>，<V2,V3>，<V3,V2>}数据结构--图的基本知识点全文共107页，当前为第4页。在无向图中，若存在一条边（Vi,Vj），则称Vi和Vj互为邻接点（Adjacent）在有向图中，若存在一条弧<Vi,Vj>，则称Vi为此弧的起点，称Vj为此弧的终点，称Vi邻接到Vj，Vj邻接自Vi，Vi和Vj互为邻接点。1．邻接点

数据结构--图的基本知识点全文共107页，当前为第5页。2．顶点的度、入度和出度在无向图中，与顶点v相邻接的边数称为该顶点的度，记为D(v)。在有向图中，顶点v的度又分为入度和出度两种：以顶点v为终点(弧头)的弧的数目称为顶点v的入度，记为ID(v)；以顶点v为起点(弧尾)的弧的数目称为顶点v的出度，记为OD(v)；有向图顶点v的度为该顶点的入度和出度之和，即

D(v)=ID(v)+OD(v)

数据结构--图的基本知识点全文共107页，当前为第6页。无论是有向图还是无向图，一个图的顶点数n、边(弧)数e和每个顶点的度di之间满足以下的关系式：即在有向图或无向图中：所有顶点度数之和：边数=2：1数据结构--图的基本知识点全文共107页，当前为第7页。3．完全图、稠密图和稀疏图在图G中：若G为无向图，任意两个顶点之间都有一条边，称G为无向完全图。顶点数为n，无向完全图的边数：

e=Cn2=n(n1)/2若G为有向图，任意两个顶点Vi,Vj之间都有弧<Vi,Vj>、<Vj,Vi>

，称G为有向完全图。如顶点数为n，有向完全图的弧数：

e=Pn2=n(n1)例如，无向图G1就是4个顶点无向完全图。若一个图接近完全图，则称其为稠密图；反之，若一个图含有很少条边或弧（即e＜＜n2），则称其为稀疏图。数据结构--图的基本知识点全文共107页，当前为第8页。4．子图若有图G=(V,E)和G′=(V′,E′)且V′

是V的子集，即V′

V，E′是E的子集，即

E′

E则称图G′为图G的子图。数据结构--图的基本知识点全文共107页，当前为第9页。5．路径、回路和路径长度在无向图G中，若存在一个顶点序列(Vp

,Vi1,Vi2,…,Vin

,Vq)，使(Vp,Vi1)，(Vi1,Vi2)，…，(Vin,Vq)均为图G的边，则该称顶点的序列为顶点Vp到顶点Vq的路径。若G是有向图，则路径是有向的。路径长度定义为路径上的边数或者弧的数目。若一条路径中不出现重复顶点，则称此路径为简单路径。若一条路径的起点和终点相同（Vp=Vq）称为回路或环。除了起点和终点相同外，其余顶点不相同的回路，称为简单回路或简单环。数据结构--图的基本知识点全文共107页，当前为第10页。例如，在无向图G1中：顶点序列（V1,V2,V3,V4）是一条从顶点V1到顶点V4，长度为3的简单路径；顶点序列（V1,V2,V4,V1,V3）是一条从顶点V1到顶点V3，长度为4的路径，但不是简单路径；顶点序列（V1,V2,V3,V1）是一条长度为3的简单回路。在有向图G3中：顶点序列（V2,V3,V2）是一个长度为2的有向简单环。数据结构--图的基本知识点全文共107页，当前为第11页。6．连通、连通分量和连通图、生成树在无向图G中：如果从顶点Vi

到顶点Vj至少有一条路径，则称Vi与Vj是连通的。如果图中任意两个顶点都连通，则称G为连通图，否则称为非连通图。在非连通图G中，任何一个极大连通子图称为G的连通分量。任何连通图的连通分量只有一个，即其自身，而非连通图有多个连通分量。在一个连通图中，含有全部顶点的极小(边数最少)连通子图，称为该连通图的生成树。(包含图的所有n个结点，但只含图的n-1条边。在生成树中添加一条边之后，必定会形成回路或环)数据结构--图的基本知识点全文共107页，当前为第12页。非连通图G4ABCDEFGIJKABCDEIJKFG图G1和G2为连通图非连通图G4的三个连通分量连通图G5ABCD连通图G5的两棵生成树ABCDABCD数据结构--图的基本知识点全文共107页，当前为第13页。7．强连通、强连通分量和强连通图在有向图G中：存在从顶点Vi

到顶点Vj的路径，也存在从顶点Vj

到顶点Vi的路径，则称Vi与Vj是强连通的。如果图中任意两个顶点都是强连通，则称G为强连通图，否则称为非强连通图。在非强连通图G中，任何一个极大强连通子图称为G的强连通分量。任何强连通图的强连通分量只有一个，即其自身，而非强连通图有多个强连通分量。数据结构--图的基本知识点全文共107页，当前为第14页。有向图G和强连通分量示例：数据结构--图的基本知识点全文共107页，当前为第15页。

8．权、带权图、有向网和无向网在一个图中，各边(或弧)上可以带一个数值，这个数值称为权。这种每条边都带权的图称为带权图或网有向网：带权有向图无向网：带权无向图数据结构--图的基本知识点全文共107页，当前为第16页。8.2图的基本存储结构图需存储的信息：各顶点的数据各个边（弧）的信息，包括：哪两个顶点有边（弧）若有权要表示出来顶点数、边（弧）数

V0

V4

V3

V1

V2

V0

V1

V2

V3数据结构--图的基本知识点全文共107页，当前为第17页。a

[i][j]={0vi与vj无边1vi与vj有边8.2.1邻接矩阵及其实现顶点数据存储：一维数组（顺序存储）边（弧）信息的存储：邻接矩阵：图中n个顶点之间相邻关系的n阶方阵（即二维数组a[n][n]）邻接矩阵中元素值情况（规定自身无边、无弧）：无向图a

[i][j]={0vi到vj无弧1vi到vj有弧有向图a

[i][j]={∞或0vi与vj无边（或vi到vj无弧）wvi与vj有边（或vi到vj有弧）网W表示边上的权值；0表示vi与vj是同一个顶点∞表示一个计算机允许的、大于所有边上权值的数。数据结构--图的基本知识点全文共107页，当前为第18页。1、举例无向图邻接矩阵表示010101

0101010111010001100V1V2

V4

V5

V3

特点：对称行或列方向的非零元素（或1）的个数为此顶点的度无向网V1V2

V4

V5

V3

254311邻接矩阵表示02∞4∞

2

01∞5∞

10314∞30∞∞51∞0V1V2V3V4V5V1V2V3V4V5V1V2V3V4V5V1V2V3V4V5数据结构--图的基本知识点全文共107页，当前为第19页。1、举例有向图V1V2

V3

V4

0110000000011000邻接矩阵表示特点：不一定对称行方向的非零元素（或1）的个数为此顶点的出度列方向的非零元素（或1）的个数为此顶点的入度V1V2V3V4V1V2V3V4数据结构--图的基本知识点全文共107页，当前为第20页。

容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。

n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。对稀疏图而言尤其浪费空间。邻接矩阵法优点：邻接矩阵法缺点：2、邻接矩阵法特点数据结构--图的基本知识点全文共107页，当前为第21页。3、邻接矩阵存储的图类型定义#defineMAX100/*MAX为图中顶点最多个数*/typedefintvextype;/*vextype为顶点的数据类型*/typedefstruct{vextypevex[MAX];/*一维数组存储顶点信息*/intarc[MAX][MAX];/*邻接矩阵存储边（弧）信息*/intvn,en;/*vn顶点数和en边数*/}MGraph;/*图类型*/注：MGraph

既可以表示有向图、无向图，也可以表示有整型权的网数据结构--图的基本知识点全文共107页，当前为第22页。分析：各顶点信息：键盘输入各边信息：邻接矩阵，顶点间有边值为1，无边值为0顶点数、边数：键盘输入例：建一个如图所示的无向图013424、建图运算建图——就是完成图类型变量中各个成员值的创建过程。执行时输入数据：5601234010312142324010101

0101010111010001100数据结构--图的基本知识点全文共107页，当前为第23页。算法实现（无向图）voidCreateGraph(MGraph*g){inti,j,v,e;scanf("%d%d",&g->vn,&g->en);/*输入顶点数和边数*/for(v=0;v<g->vn;v++)scanf("%d",&g->vex[v]);/*顶点数据输入*/for(i=0;i<g->vn;i++)for(j=0;j<g->vn;j++)g->arc[i][j]=0;/*邻接矩阵的初始值都为0*/for(e=0;e<g->en;e++)/*共有g->en条边*/{scanf("%d%d",&i,&j);/*指明有边的两个顶点的序号*/g->arc[i][j]=1;/*有边赋值为1*/g->arc[j][i]=1;/*建有向图时此句不要*/}}数据结构--图的基本知识点全文共107页，当前为第24页。8.2.2邻接表及其实现是顺序与链接相结合的图的存储方式所有顶点组成一个数组，为每个顶点建立一个单链表有两部分组成：表头——顶点数组（存放顶点信息）表体——单链表（存放与顶点相关的边或弧的信息）数据结构--图的基本知识点全文共107页，当前为第25页。1、举例无向图邻接表表示V1V2

V4

V5

V3

顶点的度：该顶点所在单链表中表结点个数无向网V1V2

V4

V5

V3

254311邻接表表示V1V2V3V4V50123413∧04∧202∧12∧14∧3V1V2V3V4V501234123∧4024∧521114∧133042∧3152∧1与顶点V1相邻接的顶点在数组中的下标权值数据结构--图的基本知识点全文共107页，当前为第26页。1、举例有向图V1V2

V3

V4

邻接表表示12∧V1V2∧V3V401233∧0∧以顶点V1为始点的弧的终点顶点在数组中的下标顶点的出度该顶点所在单链表中表结点个数顶点的入度查询整个邻接表中的表结点，与该顶点的序号（数组下标）一致的表结点个数数据结构--图的基本知识点全文共107页，当前为第27页。邻接表的缺点：邻接表的优点：空间效率高；容易寻找顶点的邻接点；判断任意两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。2、邻接表法特点数据结构--图的基本知识点全文共107页，当前为第28页。3、邻接表存储的图类型定义（1）表(边)结点——表示边(或弧)信息的链表中结点adjvexnext表结点：adjvexnextw邻接点序号(下标)下一个邻接点地址权值typedefstructarcnode{intadjvex;structarcnode*next;}ArcNode,*Arc;表结点类型数据结构--图的基本知识点全文共107页，当前为第29页。3、邻接表存储的图类型定义（2）顶点结点类型vertexfirstarc顶点结点：顶点信息链表头指针(指向第一个表结点)typedefstructvexnode{vextypevertex;ArcNode*firstarc;}VexNode;顶点结点类型（3）图的邻接表类型typedefstruct{VexNodeadjlist[MAX];/*顶点结点所在数组*/intvn,en;}ALGraph;数据结构--图的基本知识点全文共107页，当前为第30页。分析：各顶点信息：顶点数据键盘输入各链表：若顶点有出度弧，创建表结点，头插入链表顶点数、边数：键盘输入例：建一个如图所示的有向图4、建图运算建图——就是完成图类型变量中各个成员值的创建过程。执行时输入数据：44012302012330012312∧01∧2301233∧0∧vertexfirstarcadjvexnext数据结构--图的基本知识点全文共107页，当前为第31页。算法实现（有向图）voidCreateAGraph(ALGraph*g){inti,j,v,e;ArcNode*p;scanf("%d%d",&g->vn,&g->en);/*输入顶点数和边数*/for(v=0;v<g->vn;v++)/*顶点数组元素值的获得*/{scanf("%d",&g->adjlist[v].vertex);/*顶点数据键盘输入*/

g->adjlist[v].firstarc=NULL;}for(e=0;e<g->en;e++)/*共有g->en条边*/{scanf("%d%d",&i,&j);/*ij有弧，i、j为顶点序号*/p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;

/*把值为j的结点头插入到i顶点的链表中*/

p->next=g->adjlist[i].firstarc;g->adjlist[i].firstarc=p;}}思考：建无向图如何修改？数据结构--图的基本知识点全文共107页，当前为第32页。0A141B0452C353D254E015F123BACDFE补例：图的邻接表存储表示数据结构--图的基本知识点全文共107页，当前为第33页。有向图的邻接表142301201234ABCDEABECD可见，在有向图的邻接表中不易找到指向该顶点的弧数据结构--图的基本知识点全文共107页，当前为第34页。ABECD有向图的逆邻接表ABCDE30342001234在有向图的逆邻接表中，对每个顶点，链接的是指向该顶点的弧数据结构--图的基本知识点全文共107页，当前为第35页。

8.3图的遍历

从图中某个顶点出发遍历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。图的遍历有两种方法：深度优先搜索遍历（DFS）广度优先搜索遍历（BFS）。它们对无向图和有向图都适用。

数据结构--图的基本知识点全文共107页，当前为第36页。8.3.1连通图的深度优先搜索遍历1．深度优先搜索(dfs)的基本思想首先访问初始出发点V0，并将其标记设置为已访问；然后任选一个与V0相邻接且没有被访问的邻接点V1作为新的出发点，访问V1之后，将其标记设置为已访问；再以V1为新的出发点，继续进行深度优先搜索，访问与V1相邻接且没有被访问的任一个顶点V2；重复上述过程，若遇到一个所有邻接点均被访问过的顶点，则回到已访问顶点序列中最后一个还存在未被访问的邻接点的顶点，再从该顶点出发继续进行深度优先搜索，直到图中所有顶点都被访问过，搜索结束。数据结构--图的基本知识点全文共107页，当前为第37页。

V0

V7

V6

V5

V4

V3

V2

V1

V0

V1

V3

V2

V7

V6

V5

V4例序列1：V0,V1,V3,V7,V4,V2,V5,V6从v0出发的DFS序列为：由于没有规定访问邻接点的顺序，DFS序列不是唯一的序列2：V0,V1,V4,V7,V3,V2,V5,V6数据结构--图的基本知识点全文共107页，当前为第38页。算法描述：访问开始顶点（如v）；寻找v顶点未被访问的第一个邻接顶点（如w）；并把w作为开始顶点继续深度优先搜索遍历（递归思想）；直到所有顶点被访问；

其中处理：（1）访问顶点：自定义访问函数visit()（2）未被访问的邻接点：定义一个标记数组：intvisited[MAX]visited[i]=0i号顶点未被访问

1i号顶点已被访问

注意：由于函数是递归的，数组定义成外部数组

（3）第一个邻接点：按邻接距阵或邻接表中边存储的顺序2．dfs递归算法实现数据结构--图的基本知识点全文共107页，当前为第39页。函数实现：形参：图变量地址，开始顶点的序号（下标）返回值：无voiddfs(MGraph*g,intv){intj,w;

visit(g,v);/*访问v号顶点*/visited[v]=1;/*v号顶点为已访问*/for(j=0;j<g->vn;j++)/*找所有的邻接顶点*/if(g->arc[v][j]==1&&visited[j]==0)/*v号顶点与j号顶点间有边，且j号顶点为被访问*/{w=j;dfs(g,w);}}2．dfs递归算法实现邻接距阵存储结构的图起始顶点的序号（下标）voidvisit(MGraph*g,intv){printf("\n%d",g->vex[v]);}数据结构--图的基本知识点全文共107页，当前为第40页。按算法实现的dfs遍历举例：V0顶点出发遍历结果（唯一）：V0、V1、V2、V3、V4V2顶点出发遍历结果（唯一）：V2、V1、V0、V4、V3V0V1V2V3V4无向图：邻接矩阵存储结构：V0V1V2V3V401234数据结构--图的基本知识点全文共107页，当前为第41页。设计程序创建邻接矩阵的无向图，并用dfs图中顶点信息并输出：宏定义及数据类型：#include<stdlib.h>#defineMAX20/*图顶点最多不超过20*/typedefintvextype;/*图顶点为int型*/typedefstruct{vextypevex[MAX];intarc[MAX][MAX];intvn,en;}MGraph;/*邻接矩阵图类型*/intvisited[MAX];/*访问标记数组*/数据结构--图的基本知识点全文共107页，当前为第42页。函数定义：voidCreateGraph(MGraph*g)/*创建无向图*/{……}voidvisit(MGraph*g,intv)/*访问图中某个顶点*/{……}voiddfs(MGraph*g,intv)/*dfs遍历图*/{……}main()/*主函数*/{MGraphmg;/*mg为图结构变量/inti,start;/*start开始顶点序号*/CreateGraph(&mg);for(i=0;i<mg.vn;i++)/*访问标记数组置初值0*/visited[i]=0;scanf("%d",&start);dfs(&mg,start);}数据结构--图的基本知识点全文共107页，当前为第43页。8.3.2连通图的广度优先搜索遍历

1．广度优先搜索(bfs)的基本思想从图G=(V,E)的某个起始点v0出发，首先访问起始点v0，接着依次访问v0所有邻接点;再找v0的第一个邻接顶点(如w1)，再依次访问w1顶点的所有未被访问的邻接顶点；再找v0的第二个邻接顶点(如w2)，再依次访问w2顶点的所有未被访问的邻接顶点；……直到图中所有顶点都被访问到为止。数据结构--图的基本知识点全文共107页，当前为第44页。

V0

V7

V6

V5

V4

V3

V2

V1V0

V1

V3

V2

V7

V6

V5

V4求图G的以V0起点的的广度优先序列:V0,V1,V2,V3,V4,V5,V6,V7例数据结构--图的基本知识点全文共107页，当前为第45页。c0c1c3c2c4c5从C0出发的BFS序列为：由于没有规定访问邻接点的顺序，BFS序列不是唯一的c0

c1

c2c3

c4

c5数据结构--图的基本知识点全文共107页，当前为第46页。从图中某顶点vi出发：1）访问顶点vi

；（容易实现）2）访问vi

的所有未被访问的邻接点w1,w2,…wk

；3）依次从这些邻接点（在步骤2）访问的顶点）出发，访问它们的所有未被访问的邻接点;依此类推，直到图中所有访问过的顶点的邻接点都被访问；为实现3），需要保存在步骤2）中访问的顶点，而且访问这些顶点邻接点的顺序为：“先被访问先出发”的原则。故用队列来管理邻接点出发的次序。在广度优先遍历算法中，需设置一队列Q，保存已访问的顶点，并控制遍历顶点的顺序。2．bfs算法实现数据结构--图的基本知识点全文共107页，当前为第47页。QUEUEV0V1V2V3V4V5V6V7V1V2V3V0V4V5V6V7

V0

V7

V6

V5

V4

V3

V2

V1数据结构：1）全局标记数组intvisited[MAX];visited[i]=0i号顶点未被访问

1i号顶点已被访问2）邻接表存储结构数据结构--图的基本知识点全文共107页，当前为第48页。算法描述：

(1)定义一个队列Q并初始化

(2)开始顶点（如v）入队，置访问标记为1；

(3)当队列不空时，反复做：(a)队头顶点出队→w，访问w；(b)寻找w的所有未被访问的邻接顶点入队，置访问标记为1；2．bfs算法实现数据结构--图的基本知识点全文共107页，当前为第49页。函数实现：形参：图变量地址，开始顶点的序号（下标）返回值：无voidbfs(ALGraph*g,intv){inti,w;ArcNode*p;SeqQueueQ;/*循环队列*/

InitQueue(&Q);/*初始化队列*/EnQueue(&Q,v);/*入队*/

visited[v]=1;/*置v号顶点访问标记为1*/while(!EmptyQueue(&Q))/*队列不空*/

{w=DeQueue(&Q);

/*出队*/

visit(g,w);

/*访问w号顶点,自定义函数*/p=g->adjlist[w].firstarc;/*w号顶点的第一个邻接点地址*/

2．bfs算法实现邻接表存储结构的图起始顶点的序号（下标）数据结构--图的基本知识点全文共107页，当前为第50页。while(p!=NULL){i=p->adjvex;/*i为邻接顶点的序号（下标）*/if(visited[i]==0){EnQueue(&Q,i);visited[i]=1;}p=p->next;}/*找所有未访问的邻接点的循环*/}/*队列循环*/}/*函数结束*/数据结构--图的基本知识点全文共107页，当前为第51页。按算法实现的bfs遍历举例：V0顶点出发遍历结果（唯一）：V0、V1、V4、V3、V2V2顶点出发遍历结果（唯一）：V2、V3、V1、V4、V0V0V1V2V3V4无向图：邻接表存储结构：V0V1V2V3V40123414∧03∧3∧124∧03∧数据结构--图的基本知识点全文共107页，当前为第52页。设计程序创建邻接表存储的无向图，并用bfs图中顶点信息并输出：宏定义及数据类型：#include<stdlib.h>#include"Queue.h"/*循环队列相关操作的定义文件*/#defineMAX20/*图顶点最多不超过20*/typedefintvextype;/*图顶点为int型*/typedefstructarcnode{intadjvex;structarcnode*next;}ArcNode;/*表结点类型*/数据结构--图的基本知识点全文共107页，当前为第53页。typedefstructvexnode{vextypevertex;

ArcNode*firstarc;}VexNode;/*顶点结点类型*/typedefstruct{VexNodeadjlist[MAX];/*顶点结点所在数组*/intvn,en;}ALGraph;/*邻接表存储的图类型*/intvisited[MAX];/*访问标记数组*/数据结构--图的基本知识点全文共107页，当前为第54页。函数定义：voidCreateGraph(ALGraph*g)/*创建图*/{……}voidvisit(MGraph*g,intv)/*访问图中某个顶点*/{……}voidbfs(MGraph*g,intv)/*bfs遍历图*/{……}main()/*主函数*/{ALGraphalg;/*mg为邻接表图结构变量/inti,start;/*start开始顶点序号*/CreateGraph(&alg);for(i=0;i<alg.vn;i++)/*访问标记数组置初值0*/visited[i]=0;scanf("%d",&start);bfs(&alg,start);}数据结构--图的基本知识点全文共107页，当前为第55页。关于遍历小结：若图是连通的或强连通的，则从图中某一个顶点出发可以访问到图中所有顶点；若图是非连通的或非强连通图，则需从图中多个顶点出发搜索访问，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为每个连通分量中的顶点集。数据结构--图的基本知识点全文共107页，当前为第56页。问题：如何通过遍历算法，求一个非连通图的连同分量个数？intcount(MGraph*g){inti,m=0;for(i=0;i<g->vn;i++)if(visited[i]==0){m++;dfs(g,i);}returnm;}数据结构--图的基本知识点全文共107页，当前为第57页。

生成树定义图的遍历过程中经过的n个顶点n-1条边即为一棵生成树。8.4图的应用8.4.1连通图的最小生成树——无向图的应用在无向连通图G中，其一个极小连通子图(无回路)是G的生成树，它含有图中全部n个顶点，但只有n-1条边，且不唯一。数据结构--图的基本知识点全文共107页，当前为第58页。深度优先生成树：按深度优先遍历生成的生成树c0c1c3c2c4c5例c0c1c3c2c4c5数据结构--图的基本知识点全文共107页，当前为第59页。c0c1c3c2c4c5例c0c1c3c2c4c5广度优先生成树：按广度优先遍历生成的生成树数据结构--图的基本知识点全文共107页，当前为第60页。非连通图的生成森林V0V1V3V4V2V6V8V7V5V9（a）不连通的无向图G12V0V1V3V4V2V8V7V9V6V5（c）图G12的一个BFS生成森林V0V1V3V4V2V6V8V7V5V9（b）图G12的一个DFS生成森林数据结构--图的基本知识点全文共107页，当前为第61页。例

要在n个城市间建立通讯网，如何在保证n个城市连通的前题下最节省经费?ABCDEF101015121287665无向网G1ABCDEF10101276花费：45ABCDEF1512865花费：465ABCDEF107610花费：38数据结构--图的基本知识点全文共107页，当前为第62页。例

要在n个城市间建立通讯网，如何在保证n个城市连通的前题下最节省经费?ABCDEF101015121287665无向网G1这个问题实际上是连通图的最小生成树问题。数据结构--图的基本知识点全文共107页，当前为第63页。ABCDEF1010151212876655ABCDEF107610最小生成树的定义若图G是带权的无向连通图（连通网），生成树上各边权值之和称为生成树的代价，代价最小的生成树称为最小生成树；n个顶点、n-1条边、权值之和最小。数据结构--图的基本知识点全文共107页，当前为第64页。1654327131791812752410连通网：1654321397510生成树1：1654327139724生成树2：代价：44代价：60最小生成树例数据结构--图的基本知识点全文共107页，当前为第65页。最小生成树的应用集成电路布线通讯线路布线数据结构--图的基本知识点全文共107页，当前为第66页。如何快速有效地构造最小生成树？数据结构--图的基本知识点全文共107页，当前为第67页。

构造最小生成树的准则：必须只使用该网络中的边来构造最小生成树；必须使用且仅使用n-1条边来联接网络中的n个顶点。数据结构--图的基本知识点全文共107页，当前为第68页。一、Prim(普里姆)算法1、算法思想设原连通网G=(V,E)，生成的最小生成树T=(U,TE)，则算法步骤如下：(1)任选一个顶点u0放入U中，即初始U={u0}，TE={}(2)找连接U与V-U集合的一条权值最小的边即找顶点u∈U,顶点v∈V-U的权值最小的一条边(u,v)∈E；并把顶点v加入到U中，边(u,v)加入到TE中，即修改U=U+{v},TE=TE+(u,v)(3)转到（2）重复执行，直到U=V结束数据结构--图的基本知识点全文共107页，当前为第69页。ABCDEF101015121287665

（a）无向网G1算法演示:Prim算法求解最小生成树ABCE101512（b）求解过程数据结构--图的基本知识点全文共107页，当前为第70页。67ABCDEF1010151212865

（a）无向网G1算法演示:Prim算法求解最小生成树ABCDEF101512765（b）求解过程数据结构--图的基本知识点全文共107页，当前为第71页。ABCDEF101015121287665

（a）无向网G1算法演示:Prim算法求解最小生成树ABCDEF1015765（b）求解过程数据结构--图的基本知识点全文共107页，当前为第72页。6ABCDEF10101512128765

（a）无向网G1算法演示:Prim算法求解最小生成树ABCDEF1015765（b）求解过程数据结构--图的基本知识点全文共107页，当前为第73页。6ABCDEF10101512128765

（a）无向网G1算法演示:Prim算法求解最小生成树ABCDEF10157665（b）求解过程数据结构--图的基本知识点全文共107页，当前为第74页。ABCDEF101015121287665

（a）无向网G1算法演示:Prim算法求解最小生成树ABCDEF1015765（b）求解过程数据结构--图的基本知识点全文共107页，当前为第75页。ABCDEF101015121287665

（a）无向网G1算法演示:Prim算法求解最小生成树ABCDEF1015765（b）求解过程数据结构--图的基本知识点全文共107页，当前为第76页。86ABCDEF101015121287665

（a）无向网G1算法演示:Prim算法求解最小生成树BCDEF10101575（b）求解过程A数据结构--图的基本知识点全文共107页，当前为第77页。6ABCDEF101015121287665

（a）无向网G1算法演示:Prim算法求解最小生成树ABCDEF101075（b）求解过程15数据结构--图的基本知识点全文共107页，当前为第78页。67ABCDEF101015121287665

（a）无向网G1算法演示:Prim算法求解最小生成树ABCDEF1010125（b）求解过程E数据结构--图的基本知识点全文共107页，当前为第79页。67ABCDEF101015121287665

（a）无向网G1算法演示:Prim算法求解最小生成树最小生成树ABCDEF10105E数据结构--图的基本知识点全文共107页，当前为第80页。例1654326513566425131163141643142116432142516543214253Prim算法最小生成树生成过程事例(从1号顶点开始)数据结构--图的基本知识点全文共107页，当前为第81页。课堂练习：写出如下连通网的最小生成树过程165432496102014510106165432495106最小生成树1165432495106最小生成树2最小生成树不唯一！数据结构--图的基本知识点全文共107页，当前为第82页。i012345d[i].adj000000d[i].dist01∞∞58定义一个结构数组：structcost{intadj;intdist;}d[20];2、算法实现02315451839762说明：i—数组下标，又是图中对应顶点的序号d[i].adj—表示i号顶点与生成树中顶点集合U距离最小的顶点号（u）d[i].dist—表示i号顶点与生成树中adj顶点（u号顶点）的距离，当dist=0时表示i号顶点已到生成树中。生成树初始选0号顶点数据结构--图的基本知识点全文共107页，当前为第83页。2、算法实现i012345d[i].adj000000d[i].dist01∞∞5802315451839762(1)取d数组中dist≠0的最小值，则把u=0,v=1,w=1送入生成树，其顶点集为：{0,1}，并修改数组d的内容i012345d[i].adj011000d[i].dist002∞58生成树初始选0号顶点uvw数据结构--图的基本知识点全文共107页，当前为第84页。(2)取d数组中dist≠0的最小值，则把u=1,v=2,w=2送入生成树，其顶点集为：{0,1,2}，并修改数组d的内容i012345d[i].adj011000d[i].dist002∞58i012345d[i].adj012202d[i].dist000756i012345d[i].adj012202d[i].dist000756(3)取d数组中dist≠0的最小值，则把u=0,v=4,w=5送入生成树，其顶点集为：{0,1,2,4}，并修改数组d的内容i012345d[i].adj012442d[i].dist000306数据结构--图的基本知识点全文共107页，当前为第85页。(4)取d数组中dist≠0的最小值，则把u=4,v=3,w=3送入生成树，其顶点集为：{0,1,2,4,3}，并修改数组d的内容i012345d[i].adj012442d[i].dist000306i012345d[i].adj012342d[i].dist000006i012345d[i].adj012342d[i].dist000006(5)取d数组中dist≠0的最小值，则把u=2,v=5,w=6送入生成树，其顶点集为：{0,1,2,4,3,5}，并修改数组d的内容i012345d[i].adj012345d[i].dist000000数据结构--图的基本知识点全文共107页，当前为第86页。无向网的建立：#include<stdio.h>#defineINF32767typedefstruct{intu,v,w;}Tree;/*最小生成树顺序存储元素类型*/voidCreateGraph(MGraph*g){inti,j,w,e;FILE*fp;/*文件指针fp*/fp=fopen("graph.dat","r");/*打开数据文件*/

/*图的顶点数和边数、顶点数据和边的信息从文件获取*/fscanf(fp,"%d%d",&g->vn,&g->en);for(i=0;i<g->vn;i++)/*邻接矩阵初始化*/for(j=0;j<g->vn;j++)/*对角线为0，其余为∞*/if(i==j)g->arc[i][j]=0;elseg->arc[i][j]=INF;02315451839762数据结构--图的基本知识点全文共107页，当前为第87页。无向网的建立（续）：for(i=0;i<g->vn;i++)g->vex[i]='A'+i;/*顶点数据为A、B、C……*/for(e=0;e<g->en;e++){/*从文件读取对应边信息，即有边的顶点序号及权值*/fscanf(fp,"%d%d%d",&i,&j,&w)；

g->arc[i][j]=w;g->arc[j][i]=w;}fclose(fp);/*关闭文件*/}/*结束函数*/文件graph.dat中的内容为：68011045058122237256343359数据结构--图的基本知识点全文共107页，当前为第88页。无向网邻接距阵的输出：voidOutGraph(MGraph*g){inti,j;printf("\n-------Graph--------\n");printf("\nvn=%d\ten=%d",g->vn,g->en);for(i=0;i<g->vn;i++){for(j=0;j<g->vn;j++)printf("%d\t",g->arc[i][j]);printf("\n");}}输出：----------Graph-----------68数据结构--图的基本知识点全文共107页，当前为第89页。prim算法实现：voidPrim(MGraph*g,intv0,TreeE[]){inti,j,k,min;structcost{

intadj;intdist;}d[20];for(i=0;i<g->vn;i++)/*d数组初始化*/{d[i].adj=v0;d[i].dist=g->arc[v0][i];}}for(k=0;k<g->vn-1;k++)/*求vn-1条生成树的边*/{min=INF;j=-1;for(i=0;i<g->vn;i++)/*找权值最小的边*/if(d[i].dist!=0&&d[i].dist<min){j=i;min=d[i].dist;}E[k].u=d[j].adj;E[k].v=j;E[k].w=min;/*送入生成树*/

d[j].adj=j;d[j].dist=0;/*修改新送入生成树顶点的信息*/数据结构--图的基本知识点全文共107页，当前为第90页。prim算法实现（续）：

for(i=0;i<g->vn;i++)/*修改数组d中数组*/{/*新加入到生成树的j顶点与i顶点边的权值更小，则修改*/if(d[i].dist!=0&&g->arc[j][i]<d[i].dist){d[i].adj=j;d[i].dist=g->arc[j][i];}}}/*结束求生成树的for*/}/*结束函数*/数据结构--图的基本知识点全文共107页，当前为第91页。最小生成树的输出：voidOutTree(TreeE[],intk){inti;printf("\nspaningtree\n");for(i=0;i<k;i++)/*生成树E数组中有k条边*/printf("\n%c-----%c------%d",E[i].u,E[i].v,E[i].w);}输出：spaningtree0--------1---------11--------2---------20--------4---------54--------3---------32--------5---------6数据结构--图的基本知识点全文共107页，当前为第92页。主函数：main(){MGraphG;TreeE[20];CreateGraph(&G);OutGraph(&G);Prim(&G,0,E);OutTree(E,G.vn-1);}数据结构--图的基本知识点全文共107页，当前为第93页。二、Kruskal（克鲁斯卡尔）算法1、算法思想把图的所有边按其权