数据结构图基本知识点课件

第第8章图章图Tuesday,June 25,2024第第8章图章图8.1 8.1 图的基本概念图的基本概念8.2 8.2 图的基本存储结构图的基本存储结构8.2.1 8.2.1 邻接距阵及其实现邻接距阵及其实现8.2.2 8.2.2 邻接表及其实现邻接表及其实现8.3 8.3 图的遍历图的遍历8.3.1 8.3.1 深度优先搜索遍历深度优先搜索遍历8.3.2 8.3.2 广度优先搜索遍历广度优先搜索遍历8.4 8.4 图的应用图的应用8.4.1 8.4.1 连通图的最小生成树连通图的最小生成树8.4.2 8.4.2 拓扑排序拓扑排序一、一、现实中的图现实中的图8.1 8.1 图的基本概念图的基本概念 图最常见的应用是在交通运输和通信网络中找出造价图最常见的应用是在交通运输和通信网络中找出造价最低的方案。通信网络示例如下图所示：最低的方案。通信网络示例如下图所示：图图G是由一个是由一个顶点集顶点集V和一个和一个边边集集E构成的数据结构。构成的数据结构。记为二元组形式：记为二元组形式：G=(V,E)其中其中:V是由顶点构成的是由顶点构成的非空非空有限集合，记为：有限集合，记为：VV0,V1,V2,Vn-1 E是由是由V中顶点的对偶构成的有限集合，记为：中顶点的对偶构成的有限集合，记为：E=(V0,V2),(V3,V4),，若若E为空，则图中只有顶点而没有边为空，则图中只有顶点而没有边。其中对偶可以表示成：其中对偶可以表示成：(Vi,Vj)无序的对偶称为无序的对偶称为边边，即，即(Vi,Vj)=(Vj,Vi)，其图称为，其图称为无向图无向图 有序的对偶称为有序的对偶称为弧弧，即，即，则称，则称Vi为弧尾为弧尾，称，称Vj为弧头为弧头，该图称为，该图称为有向图有向图二、二、图的定义图的定义有向图和无向图示例：有向图和无向图示例：无向图无向图G1的二元组表示：的二元组表示：V(G1)=V1,V2,V3,V4E(G1)=(V1,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互为邻接点互为邻接点。1邻接点邻接点 2顶点的度、入度和出度顶点的度、入度和出度l在无向图中，与顶点在无向图中，与顶点v相邻接的边数称为相邻接的边数称为该顶点的该顶点的度度，记为，记为D(v)。l在有向图中，顶点在有向图中，顶点v的度又分为的度又分为入度入度和和出度出度两种：两种：以顶点以顶点v为终点为终点(弧头弧头)的弧的数目称为顶点的弧的数目称为顶点v的的入度入度，记，记为为ID(v)；以顶点以顶点v为起点为起点(弧尾弧尾)的弧的数目称为顶点的弧的数目称为顶点v的的出度出度，记，记为为OD(v)；有向图顶点有向图顶点v的度为该顶点的入度和出度之和，即的度为该顶点的入度和出度之和，即 D(v)=ID(v)+OD(v)l无论是有向图还是无向图，一个图的顶点数无论是有向图还是无向图，一个图的顶点数n n、边、边(弧弧)数数e e和每个顶点的度和每个顶点的度d di i之间满足以下的关系式：之间满足以下的关系式：l即在有向图或无向图中：即在有向图或无向图中：所有顶点度数之和所有顶点度数之和 ：边数：边数 =2=2：1 13完全图、稠密图和稀疏图完全图、稠密图和稀疏图l在图在图G中：中：若若G为为无无向向图图，任任意意两两个个顶顶点点之之间间都都有有一一条条边边，称称G为为无无向完全图向完全图。顶点数为。顶点数为n，无向完全图的边数：，无向完全图的边数：e=Cn2=n(n 1)/2若若G为为有有向向图图，任任意意两两个个顶顶点点Vi,Vj之之间间都都有有弧弧、，称称G为为有有向向完完全全图图。如如顶顶点点数数为为n，有有向向完完全全图图的弧数：的弧数：e=Pn2=n(n 1)l例如，无向图例如，无向图G1就是就是4个顶点无向完全图。个顶点无向完全图。l若若一一个个图图接接近近完完全全图图，则则称称其其为为稠稠稠稠密密密密图图图图；反反之之，若若一一个个图图含含有很少条边或弧（即有很少条边或弧（即en2），则称其为），则称其为稀疏图稀疏图稀疏图稀疏图。4 4子图子图l若有图若有图G=(V,E)和和G=(V,E)l且且V 是是V的子集，即的子集，即V V，E是是E的子集，即的子集，即 E El则称图则称图G为图为图G的子图。的子图。5路径、回路和路径长度路径、回路和路径长度l在在无无向向图图G中中，若若存存在在一一个个顶顶点点序序列列(Vp,Vi1,Vi2,Vin,Vq)，使使(Vp,Vi1)，(Vi1,Vi2)，(Vin,Vq)均均为为图图G的的边边，则则该该称称顶顶点点的的序序列列为为顶顶点点Vp到到顶顶点点Vq的的路路径径。若若G是是有有向向图图，则则路路径是有向的。径是有向的。l路径长度路径长度定义为路径上的边数或者弧的数目。定义为路径上的边数或者弧的数目。l若一条路径中不出现重复顶点，则称此路径为若一条路径中不出现重复顶点，则称此路径为简单路径简单路径。l若一条路径的起点和终点相同（若一条路径的起点和终点相同（Vp=Vq）称为）称为回路回路或或环环。l除除了了起起点点和和终终点点相相同同外外，其其余余顶顶点点不不相相同同的的回回路路，称称为为简简单单回路回路或或简单环简单环。l例如，在无向图例如，在无向图G1中：中：顶顶点点序序列列（V1,V2,V3,V4）是是一一条条从从顶顶点点V1到到顶顶点点V4，长度为，长度为3的的简单路径简单路径；顶顶点点序序列列（V1,V2,V4,V1,V3）是是一一条条从从顶顶点点V1到到顶点顶点V3，长度为，长度为4的的路径路径，但不是简单路径；，但不是简单路径；顶顶点点序序列列（V1,V2,V3,V1）是是一一条条长长度度为为3的的简简单单回路回路。l在有向图在有向图G3中：中：顶顶点点序序列列（V2,V3,V2）是是一一个个长长度度为为2的的有有向向简简单单环环。6连通、连通分量和连通图、生成树连通、连通分量和连通图、生成树l在无向图在无向图G中：中：如如果果从从顶顶点点Vi 到到顶顶点点Vj至至少少有有一一条条路路径径，则则称称Vi与与Vj是是连连通通的。的。如如果果图图中中任任意意两两个个顶顶点点都都连连通通，则则称称G为为连连通通图图，否否则则称称为为非连通图。非连通图。在非连通图在非连通图G中，任何一个中，任何一个极大连通子图极大连通子图称为称为G的的连通分量连通分量。任任何何连连通通图图的的连连通通分分量量只只有有一一个个，即即其其自自身身，而而非非连连通通图图有有多个连通分量。多个连通分量。在在一一个个连连通通图图中中，含含有有全全部部顶顶点点的的极极小小(边边数数最最少少)连连通通子子图图，称称为为该该连连通通图图的的生生成成树树。(包包含含图图的的所所有有 n 个个结结点点，但但只只含含图图的的 n-1 条条边边。在在生生成成树树中中添添加加一一条条边边之之后后，必必定定会会形形成成回回路或环路或环)l非连通图非连通图G4G4A AB BC CD DE EF FG GI IJ JK KA AB BC CD DE EI IJ 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为为强强连连通通图图，否则称为否则称为非强连通图。非强连通图。在在非非强强连连通通图图G中中，任任何何一一个个极极大大强强连连通通子子图图称称为为G的的强强连连通分量通分量。任任何何强强连连通通图图的的强强连连通通分分量量只只有有一一个个，即即其其自自身身，而而非非强强连通图有多个强连通分量。连通图有多个强连通分量。有向图有向图G G和强连通分量示例：和强连通分量示例：8权、带权图、有向网和无向网权、带权图、有向网和无向网l在在一一个个图图中中，各各边边(或或弧弧)上上可可以以带带一一个个数数值值，这这个个数数值值称称为为权权。l这种每条边都带权的图称为这种每条边都带权的图称为带权图或网带权图或网带权图或网带权图或网有向网：有向网：有向网：有向网：带权有向图带权有向图带权有向图带权有向图无向网：无向网：无向网：无向网：带权无向图带权无向图带权无向图带权无向图8.2图的基本存储结构图的基本存储结构l图需存储的信息：图需存储的信息：图需存储的信息：图需存储的信息：各顶点的数据各顶点的数据各顶点的数据各顶点的数据各个边（弧）的信息，包括：各个边（弧）的信息，包括：各个边（弧）的信息，包括：各个边（弧）的信息，包括：l哪两个顶点有边（弧）哪两个顶点有边（弧）哪两个顶点有边（弧）哪两个顶点有边（弧）l若有权要表示出来若有权要表示出来若有权要表示出来若有权要表示出来顶点数、边（弧）数顶点数、边（弧）数顶点数、边（弧）数顶点数、边（弧）数 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有边有边8.2.1邻接矩阵及其实现邻接矩阵及其实现l顶点数据存储：顶点数据存储：顶点数据存储：顶点数据存储：一维数组（顺序存储）一维数组（顺序存储）一维数组（顺序存储）一维数组（顺序存储）l边（弧）信息的存储：边（弧）信息的存储：边（弧）信息的存储：边（弧）信息的存储：邻邻邻邻接接接接矩矩矩矩阵阵阵阵：图图图图中中中中n n个个个个顶顶顶顶点点点点之之之之间间间间相相相相邻邻邻邻关关关关系系系系的的的的n n阶阶阶阶方方方方阵阵阵阵（即即即即二二二二维数组维数组维数组维数组annann）邻接矩阵中元素值情况（规定自身无边、无弧）：邻接矩阵中元素值情况（规定自身无边、无弧）：邻接矩阵中元素值情况（规定自身无边、无弧）：邻接矩阵中元素值情况（规定自身无边、无弧）：l l无向图无向图无向图无向图a ij=0 vi到到vj无弧无弧1 vi到到vj有弧有弧l l有向图有向图有向图有向图a ij=或或0 vi与与vj无边（或无边（或vi到到vj无弧）无弧）w vi与与vj有边（或有边（或vi到到vj有弧）有弧）l l网网网网W表示边上的权值；表示边上的权值；0表示表示vi与与vj是同一个顶点是同一个顶点表示一个计算机允许的、大于所有边上权值的数。表示一个计算机允许的、大于所有边上权值的数。1 1、举例、举例、举例、举例无向图无向图无向图无向图邻接矩阵表示邻接矩阵表示0101010101010111010001100V1V2V4V5V3l l特点：特点：特点：特点：对称对称对称对称行或列方向的非零元素（或行或列方向的非零元素（或行或列方向的非零元素（或行或列方向的非零元素（或1 1）的个数为此顶点的度）的个数为此顶点的度）的个数为此顶点的度）的个数为此顶点的度无向网无向网无向网无向网V1V2V4V5V3254311邻接矩阵表示邻接矩阵表示02420151031430510V1V2V3V4V5V1V2V3V4V5V1V2V3V4V5V1V2V3V4V51 1、举例、举例、举例、举例有向图有向图有向图有向图V1V2V3V40110000000011000邻接矩阵表示邻接矩阵表示l l特点：特点：特点：特点：不一定对称不一定对称不一定对称不一定对称行方向的非零元素（或行方向的非零元素（或行方向的非零元素（或行方向的非零元素（或1 1）的个数为此顶点的出度）的个数为此顶点的出度）的个数为此顶点的出度）的个数为此顶点的出度列方向的非零元素（或列方向的非零元素（或列方向的非零元素（或列方向的非零元素（或1 1）的个数为此顶点的入度）的个数为此顶点的入度）的个数为此顶点的入度）的个数为此顶点的入度V1V2V3V4V1V2V3V4 容易实现图的操作，如：求某顶点的度、判断顶点之间是否容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。有边（弧）、找顶点的邻接点等等。n n个顶点需要个顶点需要n*nn*n个单元存储边个单元存储边(弧弧););空间效率为空间效率为O(nO(n2 2)。对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。邻接矩阵法邻接矩阵法优点：优点：邻接矩阵法邻接矩阵法缺点：缺点：2、邻接矩阵法、邻接矩阵法特点特点3 3、邻接矩阵存储的图类型定义、邻接矩阵存储的图类型定义、邻接矩阵存储的图类型定义、邻接矩阵存储的图类型定义#define MAX 100 /*MAX为图中顶点最多个数为图中顶点最多个数*/typedef int vextype;/*vextype为顶点的数据类型为顶点的数据类型*/typedef struct vextype vexMAX;/*一维数组存储顶点信息一维数组存储顶点信息*/int arcMAXMAX;/*邻接矩阵存储边（弧）信息邻接矩阵存储边（弧）信息*/int vn,en;/*vn顶点数和顶点数和en边数边数*/MGraph;/*图类型图类型*/注：注：MGraph 既可以表示有向图、无向图，也可以表示有既可以表示有向图、无向图，也可以表示有整型权的网整型权的网分析：分析：分析：分析：各顶点信息各顶点信息各顶点信息各顶点信息：键盘输入：键盘输入：键盘输入：键盘输入各边信息各边信息各边信息各边信息：邻接矩阵，顶点间有边值为：邻接矩阵，顶点间有边值为：邻接矩阵，顶点间有边值为：邻接矩阵，顶点间有边值为1 1，无边值为，无边值为，无边值为，无边值为0 0顶点数、边数：顶点数、边数：顶点数、边数：顶点数、边数：键盘输入键盘输入键盘输入键盘输入例：建一个如图所示的无向图例：建一个如图所示的无向图013424 4、建图运算、建图运算、建图运算、建图运算建图建图建图建图就是完成图类型变量中各个成员值的创建过程。就是完成图类型变量中各个成员值的创建过程。就是完成图类型变量中各个成员值的创建过程。就是完成图类型变量中各个成员值的创建过程。执行时输入数据：执行时输入数据：执行时输入数据：执行时输入数据：565601234012340101030312121414232324240101010101010111010001100算法实现（无向图）算法实现（无向图）算法实现（无向图）算法实现（无向图）void CreateGraph(MGraph *g)int i,j,v,e;scanf(%d%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=1;/*建有向图时此句不要建有向图时此句不要*/8.2.2邻接表及其实现邻接表及其实现l是顺序与链接相结合的图的存储方式是顺序与链接相结合的图的存储方式是顺序与链接相结合的图的存储方式是顺序与链接相结合的图的存储方式l所有顶点组成一个数组，为每个顶点建立一个单链表所有顶点组成一个数组，为每个顶点建立一个单链表所有顶点组成一个数组，为每个顶点建立一个单链表所有顶点组成一个数组，为每个顶点建立一个单链表l有两部分组成：有两部分组成：有两部分组成：有两部分组成：表头表头表头表头顶点数组（存放顶点信息）顶点数组（存放顶点信息）顶点数组（存放顶点信息）顶点数组（存放顶点信息）表体表体表体表体单链表（存放与顶点相关的边或弧的信息）单链表（存放与顶点相关的边或弧的信息）单链表（存放与顶点相关的边或弧的信息）单链表（存放与顶点相关的边或弧的信息）1 1、举例、举例、举例、举例无向图无向图无向图无向图邻接表表示邻接表表示V1V2V4V5V3l l顶点的度：顶点的度：顶点的度：顶点的度：该顶点所在单链表中表结点个数该顶点所在单链表中表结点个数该顶点所在单链表中表结点个数该顶点所在单链表中表结点个数无向网无向网无向网无向网V1V2V4V5V3254311邻接表表示邻接表表示V1V2V3V4V50123413 04 202 12 14 3V1V2V3V4V501234123 4024 521114 133042 3152 1与顶点与顶点V1相邻接的顶点相邻接的顶点在数组中的下标在数组中的下标权值权值1 1、举例、举例、举例、举例有向图有向图有向图有向图V1V2V3V4邻接表表示邻接表表示12 V1V2 V3V401233 0 以顶点以顶点V1为始点的弧的终点为始点的弧的终点顶点在数组中的下标顶点在数组中的下标l l顶点的出度顶点的出度顶点的出度顶点的出度该顶点所在单链表中表结点个数该顶点所在单链表中表结点个数该顶点所在单链表中表结点个数该顶点所在单链表中表结点个数l l顶点的入度顶点的入度顶点的入度顶点的入度查查查查询询询询整整整整个个个个邻邻邻邻接接接接表表表表中中中中的的的的表表表表结结结结点点点点，与与与与该该该该顶顶顶顶点点点点的的的的序序序序号号号号（数数数数组下标）一致的表结点个数组下标）一致的表结点个数组下标）一致的表结点个数组下标）一致的表结点个数邻接表的邻接表的缺点：缺点：邻接表的邻接表的优点：优点：空间效率高；空间效率高；容易寻找顶点的邻接点；容易寻找顶点的邻接点；判断任意两顶点间是否有边或弧，需搜判断任意两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵索两结点对应的单链表，没有邻接矩阵方便。方便。2、邻接表法、邻接表法特点特点3 3、邻接表存储的图类型定义、邻接表存储的图类型定义、邻接表存储的图类型定义、邻接表存储的图类型定义（1 1）表）表）表）表(边边边边)结点结点结点结点表示边表示边表示边表示边(或弧或弧或弧或弧)信息的链表中结点信息的链表中结点信息的链表中结点信息的链表中结点adjvexnext表结点：表结点：adjvexnextw邻接点序号邻接点序号(下标下标)下一个邻接下一个邻接点地址点地址权值权值typedef struct arcnodetypedef struct arcnode int adjvex;int adjvex;struct arcnode *next;struct arcnode *next;ArcNodeArcNode,*Arc;,*Arc;表结点类型表结点类型3 3、邻接表存储的图类型定义、邻接表存储的图类型定义、邻接表存储的图类型定义、邻接表存储的图类型定义（2 2）顶点结点类型）顶点结点类型）顶点结点类型）顶点结点类型vertexfirstarc顶点结点：顶点结点：顶点信息顶点信息链表头指针链表头指针(指向第一个表结点指向第一个表结点)typedef struct vexnodetypedef struct vexnode vextype vertex;vextype vertex;ArcNode *firstarc;ArcNode *firstarc;VexNodeVexNode;顶点结点类型顶点结点类型（3 3）图的邻接表类型）图的邻接表类型）图的邻接表类型）图的邻接表类型typedef struct typedef struct VexNode adjlistMAX;VexNode adjlistMAX;/*/*顶点结点所在数组顶点结点所在数组*/int vn,en;int vn,en;ALGraphALGraph;分析：分析：分析：分析：各顶点信息各顶点信息各顶点信息各顶点信息：顶点数据键盘输入：顶点数据键盘输入：顶点数据键盘输入：顶点数据键盘输入各链表各链表各链表各链表：若顶点有出度弧，创建表结点，头插入链表：若顶点有出度弧，创建表结点，头插入链表：若顶点有出度弧，创建表结点，头插入链表：若顶点有出度弧，创建表结点，头插入链表顶点数、边数：顶点数、边数：顶点数、边数：顶点数、边数：键盘输入键盘输入键盘输入键盘输入例：建一个如图所示的有向图例：建一个如图所示的有向图4 4、建图运算、建图运算、建图运算、建图运算建图建图建图建图就是完成图类型变量中各个成员值的创建过程。就是完成图类型变量中各个成员值的创建过程。就是完成图类型变量中各个成员值的创建过程。就是完成图类型变量中各个成员值的创建过程。执行时输入数据：执行时输入数据：执行时输入数据：执行时输入数据：4444012301230202010123233030012312 01 2301233 0 vertexvertexfirstarcfirstarcadjvexadjvexnextnext算法实现（有向图）算法实现（有向图）算法实现（有向图）算法实现（有向图）void 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%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 D EABECD可见，在有向图的邻接表中不易找到指向该顶点的弧ABECD有向图的逆邻接表有向图的逆邻接表A B C D E 303420 01234在有向图的逆邻接表中，对每个顶点，链接的是指向该顶点的弧 8.3 图的遍历图的遍历 从图中某个顶点出发遍历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。图的遍历有两种方法：深度优先搜索遍历（DFS）广度优先搜索遍历（BFS）。它们对无向图和有向图都适用。8.3.1连通图的深度优先搜索遍历连通图的深度优先搜索遍历1深度优先搜索深度优先搜索(dfs)的基本思想的基本思想l首先访问初始出发点首先访问初始出发点V V0 0，并将其标记设置为已访问；，并将其标记设置为已访问；l然然后后任任选选一一个个与与V V0 0相相邻邻接接且且没没有有被被访访问问的的邻邻接接点点V V1 1作作为为新新的的出发点，访问出发点，访问V V1 1之后，将其标记设置为已访问；之后，将其标记设置为已访问；l再再以以V V1 1为为新新的的出出发发点点，继继续续进进行行深深度度优优先先搜搜索索，访访问问与与V V1 1相相邻接且没有被访问的任一个顶点邻接且没有被访问的任一个顶点V V2 2；l重重复复上上述述过过程程，若若遇遇到到一一个个所所有有邻邻接接点点均均被被访访问问过过的的顶顶点点，则则回回到到已已访访问问顶顶点点序序列列中中最最后后一一个个还还存存在在未未被被访访问问的的邻邻接接点点的的顶顶点点，再再从从该该顶顶点点出出发发继继续续进进行行深深度度优优先先搜搜索索，直直到到图图中中所有顶点都被访问过，搜索结束。所有顶点都被访问过，搜索结束。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,V5,V6算法描述：算法描述：访问开始顶点（如访问开始顶点（如 v）；）；寻找寻找 v 顶点未被访问的第一个邻接顶点（如顶点未被访问的第一个邻接顶点（如 w）；）；并把并把 w 作为开始顶点继续深度优先搜索遍历（递归思想）；作为开始顶点继续深度优先搜索遍历（递归思想）；直到所有顶点被访问；直到所有顶点被访问；其中处理：其中处理：（1）访问顶点：自定义访问函数）访问顶点：自定义访问函数 visit()（2）未被访问的邻接点：定义一个标记数组：）未被访问的邻接点：定义一个标记数组：int visitedMAX visitedi=0 i号顶点号顶点未未被访问被访问 1 i号顶点号顶点已已被访问被访问 注意：由于函数是递归的，数组定义成外部数组注意：由于函数是递归的，数组定义成外部数组（3）第一个邻接点：按邻接距阵或邻接表中边存储的顺序）第一个邻接点：按邻接距阵或邻接表中边存储的顺序 22 dfsdfs递归算法实现递归算法实现递归算法实现递归算法实现函数实现：函数实现：形参：形参：图变量地址，开始顶点的序号（下标）图变量地址，开始顶点的序号（下标）返回值：返回值：无无void dfs(MGraph *g,int v)int j,w;visit(g,v);/*访问访问v号顶点号顶点*/visitedv=1;/*v号顶点为已访问号顶点为已访问*/for(j=0;jvn;j+)/*找所有的邻接顶点找所有的邻接顶点*/if(g-arcvj=1&visitedj=0)/*v号顶点与号顶点与j号顶点号顶点 间有边，且间有边，且j号顶点为被访问号顶点为被访问*/w=j;dfs(g,w);22 dfsdfs递归算法实现递归算法实现递归算法实现递归算法实现邻接距阵存储结构的图邻接距阵存储结构的图起始顶点的序号（下标）起始顶点的序号（下标）void visit(MGraph *g,int v)printf(n%d,g-vexv);按算法实现的按算法实现的dfs遍历举例：遍历举例：V0顶点出发遍历结果（唯一）顶点出发遍历结果（唯一）：V0、V1、V2、V3、V4V2顶点出发遍历结果（唯一）顶点出发遍历结果（唯一）：V2、V1、V0、V4、V3V0V1V2V3V4无向图：无向图：邻接矩阵存储结构：邻接矩阵存储结构：V0V1V2V3V401234设计程序创建邻接矩阵的无向图，并用设计程序创建邻接矩阵的无向图，并用dfsdfs图中顶点图中顶点信息并输出：信息并输出：宏定义及数据类型：宏定义及数据类型：#include#define MAX 20 /*图顶点最多不超过图顶点最多不超过20*/typedef int vextype;/*图顶点为图顶点为int型型*/typedef struct vextype vexMAX;int arcMAXMAX;int vn,en;MGraph;/*邻接矩阵图类型邻接矩阵图类型*/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(&mg);for(i=0;iadjlistw.firstarc;/*w号顶点的第一个邻接点地址号顶点的第一个邻接点地址*/22 bfsbfs算法实现算法实现算法实现算法实现邻接表存储结构的图邻接表存储结构的图起始顶点的序号（下标）起始顶点的序号（下标）while(p!=NULL)i=p-adjvex;/*i为邻接顶点的序号（下标）为邻接顶点的序号（下标）*/if(visitedi=0)EnQueue(&Q,i);visitedi=1;p=p-next;/*找所有未访问的邻接点的循环找所有未访问的邻接点的循环*/*队列循环队列循环*/*函数结束函数结束*/按算法实现的按算法实现的bfs遍历举例：遍历举例：V0顶点出发遍历结果（唯一）顶点出发遍历结果（唯一）：V0、V1、V4、V3、V2V2顶点出发遍历结果（唯一）顶点出发遍历结果（唯一）：V2、V3、V1、V4、V0V0V1V2V3V4无向图：无向图：邻接表存储结构：邻接表存储结构：V0V1V2V3V4012341403312403设计程序创建邻接表存储的无向图，并用设计程序创建邻接表存储的无向图，并用bfsbfs图中顶图中顶点信息并输出：点信息并输出：宏定义及数据类型：宏定义及数据类型：#include#include Queue.h /*循环队列相关操作的定义文件循环队列相关操作的定义文件*/#define MAX 20 /*图顶点最多不超过图顶点最多不超过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;/*邻接表存储的图类型邻接表存储的图类型*/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(&alg);for(i=0;ialg.vn;i+)/*访问标记数组置初值访问标记数组置初值0*/visitedi=0;scanf(%d,&start);bfs(&alg,start);l关于遍历小结：关于遍历小结：若图是连通的或强连通的，则从图中某一个若图是连通的或强连通的，则从图中某一个顶点出发可以访问到图中所有顶点；顶点出发可以访问到图中所有顶点；若图是非连通的或非强连通图，则需从图中若图是非连通的或非强连通图，则需从图中多个顶点出发搜索访问，而每一次从一个新多个顶点出发搜索访问，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访的起始点出发进行搜索过程中得到的顶点访问序列恰为每个连通分量中的顶点集。问序列恰为每个连通分量中的顶点集。问题：如何通过遍历算法，求一个非连通图的连问题：如何通过遍历算法，求一个非连通图的连同分量个数？同分量个数？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连通图的最小生成树连通图的最小生成树无向图的应用无向图的应用在在无无向向连连通通图图G G中中，其其一一个个极极小小连连通通子子图图(无无回回路路)是是G G的的生生成成树树，它它含含有有图图中中全全部部n n个个顶顶点点，但但只有只有n-1n-1条边条边，且不唯一。，且不唯一。深深度度优优先先生生成成树树：按按深深度度优优先先遍遍历历生生成成的的生成树生成树c0c1c3c2c4c5例例c0c1c3c2c4c5c0c1c3c2c4c5例例c0c1c3c2c4c5广广度度优优先先生生成成树树：按按广广度度优优先先遍遍历历生生成成的的生生成树成树非连通图的生成森林非连通图的生成森林V0V1V3V4V2V6V8V7V5V9（a）不连通的无向图）不连通的无向图G12V0V1V3V4V2V8V7V9V6V5（c）图）图G12的一个的一个BFS生成森林生成森林V0V1V3V4V2V6V8V7V5V9（b）图）图G12的一个的一个DFS生成森林生成森林例例要要在在n个个城城市市间间建建立立通通讯讯网网，如如何何在在保保证证n个个城城市市连连通通的的前前题题下下最最节节省省经费经费?ABCDEF101015121287665无向网无向网G1ABCDEF10101276花费：花费：45ABCDEF1512865花费：花费：465ABCDEF107610花费：花费：38例例要要在在n个个城城市市间间建建立立通通讯讯网网，如如何何在在保保证证n个个城城市市连连通通的的前前题题下下最最节节省省经费经费?ABCDEF101015121287665无向网无向网G1这这个个问问题题实实际际上上是是连连通通图图的的最最小小生生成成树树问问题。题。ABCDEF1010151212876655ABCDEF107610最小生成树的定义最小生成树的定义若若图图G G是是带带权权的的无无向向连连通通图图（连连通通网网），生生成成树树上上各各边边权权值值之之和和称称为为生生成成树树的的代代价价，代代价价最最小小的的生生成成树树称为最小生成树；称为最小生成树；ln n个顶点、个顶点、n n-1-1条边、权值之和最小。条边、权值之和最小。1654327131791812752410连通网：连通网：1654321397510生成树生成树1：1654327139724生成树生成树2：代价：代价：44代价：代价：60最小生成树最小生成树例例最小生成树的应用最小生成树的应用l集成电路布线集成电路布线l通讯线路布线通讯线路布线如何快速有效地构造如何快速有效地构造最小生成树最小生成树构造最小生成树的准则：构造最小生成树的准则：l必须只使用该网络中的边来构造最小生成树；必须只使用该网络中的边来构造最小生成树；l必必须须使使用用且且仅仅使使用用n-1条条边边来来联联接接网网络络中中的的n个顶点个顶点。一、一、Prim(普里姆普里姆)算法算法1 1、算法思想、算法思想 设设原原连连通通网网G=(V,G=(V,E)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中中，即修改即修改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算法求解最小生成树算法求解最小生成树A ABCE101512（b）求解过程）求解过程67ABCDEF1010151212865 （a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树A AB BCDEF101512765（b）求解过程）求解过程ABCDEF101015121287665（a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树A AB BCDEF1015765（b）求解过程）求解过程6ABCDEF10101512128765（a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树A AB BCD DEF1015765（b）求解过程）求解过程6ABCDEF10101512128765（a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树A AB BCD DEF10157665（b）求解过程）求解过程ABCDEF101015121287665（a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树A AB BCD DEF F1015765（b）求解过程）求解过程ABCDEF101015121287665（a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树A AB BCD DEF F1015765（b）求解过程）求解过程86ABCDEF101015121287665（a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树B BCD DEF F10101575（b）求解过程）求解过程A A6ABCDEF101015121287665（a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树A AB BC CD DEF F101075（b）求解过程）求解过程1567ABCDEF101015121287665（a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树A AB BC CD DEF F1010125（b）求解过程）求解过程E E67ABCDEF101015121287665（a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树最小生成树最小生成树A AB BC CD DEF F10105E E例1654326513566425131163141643142116432142516543214253Prim算法最小生成树生成过程事例算法最小生成树生成过程事例(从从1号顶点开始号顶点开始)课堂练习：写出如下连通网的最小生成树过程课堂练习：写出如下连通网的最小生成树过程165432496102014510106165432495106最小生成树最小生成树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 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 002 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送入生成树送入生成树，其顶点集为：其顶点集为：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)取取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;/*文件指针文件指针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;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);/*关闭文件关闭文件*/*结束函数结束函数*/文件文件graph.dat中中的内容为：的内容为：6 80 1 10 4 50 5 81 2 22 3 72 5 63 4 33 5 9无向网邻接距阵的输出：无向网邻接距阵的输出：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);输出：输出：-Graph-6 8primprim算法实现：算法实现：void Prim(MGraph *g,int v0,Tree E)int i,j,k,min;struct cost 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;/*修改新送入生成树顶点的信息修改新送入生成树顶点的信息*/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;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、算法思想、算法思想 把图的所有边按其权值从小到大排成升序把图的所有边按其权值从小到大排成升序先把权值最小的边加入生成树先把权值最小的边加入生成树依依次次选选取取后后面面的的边边，如如该该边边加加到到生生成成树树中中，使使生生成成树树构构成成回回路路，则则舍舍弃弃该该边边，否否则则该该边边加加入入到到生生成成树树中。中。重重复复上上述述过过程程，直直到到生生成成树树中中包包含含n n 1 1条条边边为为止止，此时即为最小生成树。此时即为最小生成树。例AFEDCB6314566425AFEDCB13254Kruskal算法最算法最小生成树生成过程事例：小生成树生成过程事例：AC10DF21AD32CF43BE44CD55BC56AB67CE68EF69KruskalKruskal算法练习算法练习:abcdegf195141827168213ae12dcbgf71485316217121819abcdegf195141827168213ae12dcbgf7148531621最小生成树代价=1