C语言数据结构第06讲图.ppt
59页
实用数据结构基础实用数据结构基础第第7 7章章 图图 第7章 图Ø知 识 点图的逻辑结构及基本术语图的逻辑结构及基本术语邻接矩阵和邻接表的存储结构和特点邻接矩阵和邻接表的存储结构和特点深度优先搜索和广度优先搜索两种遍历算法深度优先搜索和广度优先搜索两种遍历算法图的连通性和生成树的概念图的连通性和生成树的概念最短路径的含义及求最短路径的算法最短路径的含义及求最短路径的算法 Ø难难 点点图的遍历图的遍历 最小生成树最小生成树 最短路径最短路径Ø要要 求求熟练掌握以下内容：熟练掌握以下内容： 图的存储结构图的存储结构 图的遍历算法图的遍历算法了解以下内容：了解以下内容： 图的最小生成树和求最小生成树算法图的最小生成树和求最小生成树算法 带权有向图的最短路径问题带权有向图的最短路径问题 第7章 目录Ø7-1 7-1 图的定义和术语图的定义和术语Ø7-2 7-2 图的存储表示图的存储表示Ø7-3 7-3 图的遍历图的遍历Ø7-47-4 图的连通性图的连通性Ø7-5 7-5 最短路径最短路径Ø小小 结结Ø实验实验7 7 图子系统图子系统Ø习题习题7 7 7-1 图的定义和术语 图图（（GraphGraph））是是一一种种比比树树形形结结构构更更复复杂杂的的非非线线性性结结构构。
在在图图形形结结构构中中，，每每个个结结点点都都可可以以有有多多个个直直接接前前驱驱和和多多个个直直接接后后继7-1 7-1 图的定义和术语图的定义和术语7-1-1 7-1-1 图的定义图的定义 图图（（GraphGraph））是是由由非非空空的的顶顶点点（（VerticesVertices））集集合合和和一一个个描描述述顶顶点点之之间间关关系系————边边（（EdgesEdges））的的有有限限集集合合组组成成的的一一种种数数据据结构可以用二元组定义为：结构可以用二元组定义为： G G＝（＝（V V，，E E）） 其其中中，，G G表表示示一一个个图图，，V V是是图图G G中中顶顶点点的的集集合合，，E E是是图图G G中中边边的集合 图图7-1 无向图无向图G1 图图7-2 有向图有向图G G2 2 V1V3V2V4V5V1V3V2V4 G1=（（V，，E）） V＝＝{v1,v2,v3,v4,v5}；； E＝＝{(v1,v2),(v1,v4),(v2,v3),(v3,v4), (v3,v5),(v2,v5)}。
v(vi i, ,v vj j) )表示顶点表示顶点v vi i和顶点和顶点v vj j之间有一之间有一条无向直接连线，也称为边条无向直接连线，也称为边G2=(V,E)V={v1,v2,v3,v4}E={
可可以以证证明明，，在在一一个个含含有有n n个顶点的无向完全图中，有个顶点的无向完全图中，有n (n-1)/2n (n-1)/2条边 （（4 4）有向完全图）有向完全图 在在一一个个有有向向图图中中，，如如果果任任意意两两顶顶点点之之间间都都有有方方向向互互为为相相反反的的两两条条弧弧相相连连接接，，则则称称该该图图为为有有向向完完全全图图在在一一个个含含有有n n个顶点的有向完全图中，有个顶点的有向完全图中，有n (n-1) n (n-1) 条弧5 5）稠密图、稀疏图）稠密图、稀疏图 我我们们称称边边数数很很多多的的图图为为稠稠密密图图；；称称边边数数很很少少的的图图为为稀稀疏图6 6）顶点的度）顶点的度 在在无无向向图图中中：：一一个个顶顶点点拥拥有有的的边边数数，，称称为为该该顶顶点点的的度度记为记为TD (v)TD (v) 在有向图中：在有向图中： (a) 一个顶点拥有的弧头的数目，称为该顶点的入度，一个顶点拥有的弧头的数目，称为该顶点的入度， 记为记为ID (v)；； (b) 一个顶点拥有的弧尾的数目，称为该顶点的出度，一个顶点拥有的弧尾的数目，称为该顶点的出度， 记为记为OD (v)；； (c) 一个顶点度等于顶点的入度一个顶点度等于顶点的入度+出度，出度， 即：即：TD (v)=ID (v)＋＋OD (v)。
在图在图7-1的的G1中有：中有： TD(v1)=2 TD(v2)=3 TD(v3)=3 TD(v4)=2 TD(v5)=2 在图在图7-2的的G2中有：中有： ID(v1)=1 OD(v1)=2 TD(v1)=3 ID(v2)=1 OD(v2)=0 TD(v2)=1 ID(v3)=1 OD(v3)=1 TD(v3)=2 ID(v4)=1 OD(v4)=1 TD(v4)=2 可可以以证证明明，，对对于于具具有有n n个个顶顶点点、、e e条条边边的的图图，，顶顶点点v vi i的的度度TD (vTD (vi i) )与顶点的个数以及边的数目满足关系：与顶点的个数以及边的数目满足关系： （（7 7）权）权 图图的的边边或或弧弧有有时时具具有有与与它它有有关关的的数数据据信信息息，，这这个个数数据据信息就称为权（信息就称为权（WeightWeight）ACBD58697（（8 8）网）网————边（或弧）上带权边（或弧）上带权的图称为网（的图称为网（NetworkNetwork）。
如图如图7-37-3所示，就是一个无所示，就是一个无向网如果边是有方向的带权向网如果边是有方向的带权图，则就是一个有向网图，则就是一个有向网图图7-3 一个无向网示意一个无向网示意图图7-3 一个无向网示意一个无向网示意 （（9 9）路径、路径长度）路径、路径长度 顶点顶点v vi i到顶点到顶点v vj j之间的路径是指顶点序列之间的路径是指顶点序列v vi i,v,vi1i1,v,vi2i2, , …, v …, vimim, ,v vj j. .其中，（其中，（v vi i,v,vi1i1），），(v(vi1i1,v,vi2i2) )，，…,…,(v(vimim,.,.v vj j) )分别为图中的边路径上边的数目称为路径长度分别为图中的边路径上边的数目称为路径长度 在在图图7-17-1的的无无向向图图G1G1中中，，v v1 1→v→v4 4→v→v3 3→v→v5 5与与v v1 1→v→v2 2→v→v5 5是是从顶点从顶点v v1 1 到顶点到顶点v v5 5 的两条路径，路径长度分别为的两条路径，路径长度分别为3 3和和2 2。
1010）回路、简单路径、简单回路）回路、简单路径、简单回路 在在一一条条路路径径中中，，如如果果其其起起始始点点和和终终止止点点是是同同一一顶顶点点，，则则称称其其为为回回路路或或者者环环如如果果一一条条路路径径上上所所有有顶顶点点除除起起始始点点和和终终止点外彼此都是不同的，则称该路径为简单路径止点外彼此都是不同的，则称该路径为简单路径 在在图图7-17-1中中，，前前面面提提到到的的v v1 1到到v v5 5的的两两条条路路径径都都为为简简单单路路径径除除起起始始点点和和终终止止点点外外，，其其他他顶顶点点不不重重复复出出现现的的回回路路称称为为简简单回路，或者简单环如图单回路，或者简单环如图7-27-2中的中的v v1 1→v→v3 3→v→v4 4→v→v1 1 （（1111））子图子图 对对于于图图G=G=（（V V，，E E）），，G’=G’=（（V’V’，，E’E’）），，若若存存在在V’V’是是V V的子集的子集 ，，E’E’是是E E的子集的子集 ，则称图，则称图G’G’是是G G的一个子图的一个子图 图图7-47-4示出了示出了G G1 1和和G G2 2的子图。
的子图 图图7-4 图图G1和和G2的两个子图示意的两个子图示意 (a) G1的子图的子图 (b) G2的子图的子图 V1V3V2V1V3V2V4V5V1V3V2V4V5 图图7-1 无向图无向图G1 （（1212））连通连通图、图、连通分量连通分量 在在无无向向图图中中，，如如果果从从一一个个顶顶点点v vi i到到另另一一个个顶顶点点v vj j(i≠j)(i≠j)有有路路径径，，则则称称顶顶点点v vi i和和v vj j是是连连通通的的任任意意两两顶顶点点都都是是连连通通的的图图称称为为连连通通图图无无向向图图的的极极大大连连通通子子图图称称为为连连通通分分量量图图7-5 (7-5 (a)a)中有两个中有两个连通分量连通分量，如图，如图7-5 (7-5 (b)b)所示AEBFCDAEBFCD (a) 无向图无向图G3 (b) G3的两个的两个连通分量连通分量 图图7-5 无向图及无向图及连通分量连通分量示意示意 （（13）强）强连通连通图、强图、强连通分量连通分量 对对于于有有向向图图来来说说，，若若图图中中任任意意一一对对顶顶点点vi 和和vj(i≠j)均均有有从从一一个个顶顶点点vi到到另另一一个个顶顶点点vj有有路路径径，，也也有有从从vj到到vi的的路路径径，，则则称称该该有有向向图图是是强强连连通通图图。
有有向向图图的的极极大大强强连通连通子图子图称为称为强强连通分量连通分量 图图7-2中中有有两两个个强强连连通通分分量量，，分分别别是是{v1,v2,v3}和和{v4}，，如图如图7-6所示14）生成树）生成树 连连通通图图G的的一一个个子子图图如如果果是是一一棵棵包包含含G的的所所有有顶顶点点的的树树，，则则该该子子图图称称为为G的的生生成成树树（（Spanning Tree））在在生生成成树树中中添添加加任任意意一一条条属属于于原原图图中中的的边边必必定定会会产产生生回回路路，，因因为为新新添添加加的的边边使使其其所所依依附附的的两两个个顶顶点点之之间间有有了了第第二二条条路路径径若若生生成成树树中中减减少少任任意意一一条条边边，，则则必必然然成成为为非非连连通通的的n个个顶顶点点的的生生成成树树具具有有n-1条边V1V3V2V4图图7-6 有向图有向图G2的两个的两个 强强连通分量连通分量示意示意 7-1-3 图的基本操作图的基本操作 图的基本操作有：图的基本操作有：（（1））CreatGraph（（G））输输入入图图G的的顶顶点点和和边边，，建建立立图图G的的存储。
存储2））DFSTraverse（（G，，v））在在图图G中中，，从从顶顶点点v出出发发深深度度优先遍历图优先遍历图G3））BFSTtaverse（（G，，v））在在图图G中中，，从从顶顶点点v出出发发广广度度优先遍历图优先遍历图G 图图的的存存储储结结构构比比较较多多对对于于图图的的存存储储结结构构的的选选择择取取决决于具体的应用和需要进行的运算于具体的应用和需要进行的运算 下面介绍几种常用的图的存储结构下面介绍几种常用的图的存储结构7-2 图的存储表示 邻接矩阵是表示顶点之间相邻关系的矩阵邻接矩阵是表示顶点之间相邻关系的矩阵 假假设设图图G＝＝（（V，，E））有有n个个顶顶点点，，即即V＝＝{v0,v1,…,vn-1}，，则则G的邻接矩阵是具有如下性质的的邻接矩阵是具有如下性质的n阶方阵：阶方阵： 1 若若(vi,vj)或或
表示一个计算机允许的、大于所有边上权值的数 用用邻邻接接矩矩阵阵表表示示法法如如图图7-77-7所所示示；；用用邻邻接接矩矩阵阵表表示示法法如图如图7-87-8所示 图的邻接矩阵具有以下性质：图的邻接矩阵具有以下性质：（（1 1））无无向向图图的的邻邻接接矩矩阵阵一一定定是是一一个个对对称称矩矩阵阵因因此此，，在在具具体体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可2 2））对对于于无无向向图图，，邻邻接接矩矩阵阵的的第第i i行行（（或或第第i i列列））非非零零元元素素（或非（或非∞∞元素）的个数正好是第元素）的个数正好是第i i个顶点的度个顶点的度TD(vTD(vi i) )3 3））对对于于有有向向图图，，邻邻接接矩矩阵阵的的第第i i行行（（或或第第i i列列））非非零零元元素素（（或或非非∞∞元元素素））的的个个数数正正好好是是第第i i个个顶顶点点的的出出度度OD(vOD(vi i) )（（或或入入度度ID(vID(vi i) )）4 4））用用邻邻接接矩矩阵阵方方法法存存储储图图，，很很容容易易确确定定图图中中任任意意两两个个顶顶点点之之间间是是否否有有边边相相连连；；但但是是，，要要确确定定图图中中有有多多少少条条边边，，则则必必须须按按行行、、按按列列对对每每个个元元素素进进行行检检测测，，所所花花费费的的时时间间代代价价很很大大。
这是用邻接矩阵存储图的局限性这是用邻接矩阵存储图的局限性 图的邻接矩阵存储的描述如下：图的邻接矩阵存储的描述如下：#define MAXLEN 10typedef struct{ char vexs[MAXLEN]; int edges[MAXLEN][MAXLEN]; int n,e;} MGraph; 建立一个图的邻接矩阵存储的算法如下：建立一个图的邻接矩阵存储的算法如下：void CreateMGraph(MGraph *G){ int i,j,k; char ch1,ch2; printf("请请输输入入顶顶点点数数和和边边数数(输输入入格格式式为为:顶顶点点数数,边边数数):\n"); scanf("%d,%d",&(G->n),&(G->e)); printf("请请输输入入顶顶点点信信息息(顶顶点点号号
邻邻接接表表表表示示法法类类似似于于树树的的孩孩子子链链表表表表示示法法就就是是对对于于图图G中中的的每每个个顶顶点点vi，，该该方方法法将将所所有有邻邻接接于于vi的的顶顶点点vj链链成成一一个个单单链链表表，，这这个个单单链链表表就就称称为为顶顶点点vi的的邻邻接接表表再再将将所所有有点点的的邻邻接接表表表表头头放放到到数数组组中中，，就就构构成成了了图的邻接表图的邻接表 在邻接表表示中有两种结点结构，如图在邻接表表示中有两种结点结构，如图7-9所示 顶点域顶点域 边表头指针边表头指针 邻接点域邻接点域 指针域指针域 顶点表顶点表 边表边表 图图7-9 邻接矩阵表示的结点结构邻接矩阵表示的结点结构vertexfirstedgeadjvexnext 一一种种是是顶顶点点表表的的结结点点结结构构，，它它由由顶顶点点域域（（vertex））和和指指向向第第一一条条邻邻接接边边的的指指针针域域（（firstedge））构构成成，，另另一一种种是是边边表表结结点点，，它它由由邻邻接接点点域域(adjvex)和和指指向向下下一一条条邻邻接接边边的的指指针针域域(next)构构成成。
对对于于网网的的边边表表需需再再增增设设一一个个存存储储边边上上信信息息（（如如权权值值等等））的的域域（（info）），，网网的的边边表表结结构构如如图图7-10所示 邻接点域邻接点域 边上信息边上信息 指针域指针域 图图7-10 网的边表结构网的边表结构adjvex infonext 图图7-11给出无向图给出无向图7-7对应的邻接表表示对应的邻接表表示 邻接表表示形式描述如下：邻接表表示形式描述如下： ＃＃define MAXLEN 10 // 最大顶点数为最大顶点数为10typedef struct node // 边表结点边表结点{ int adjvex; // 邻接点域邻接点域 struct node * next; // 指向下一个邻接点的指针域指向下一个邻接点的指针域 //若要表示边上信息，则应增加一个数据域若要表示边上信息，则应增加一个数据域info }EdgeNode; typedef struct vnode // 顶点表结点顶点表结点 {VertexType vertex; // 顶点域顶点域 EdgeNode * firstedge; // 边表头指针边表头指针 }VertexNode; typedef VertexNode AdjList[MAXLEN]; // AdjList是邻接表类型是邻接表类型typedef struct{ AdjList adjlist; // 接表接表 int n,e; // 顶点数和边数顶点数和边数 }ALGraph; // ALGraph是以邻接表方式存储的图类型是以邻接表方式存储的图类型 建立一个有向图的邻接表存储的算法如下：建立一个有向图的邻接表存储的算法如下： void CreateGraphAL (ALGraph *G) { int i,j,k; EdgeNode * s; printf(“请输入顶点数和边数请输入顶点数和边数(输入格式为输入格式为:顶点数顶点数,边数边数) ：：\n"); scanf("%d,%d",&(G->n),&(G->e)); // 读入顶点数和边数读入顶点数和边数 printf("请输入顶点请输入顶点(格式为格式为:顶点号顶点号
显然，在边稀疏个表结点显然，在边稀疏(e< 7-3 图的遍历 图图的的遍遍历历（（traversing graph））是是指指从从图图中中的的某某一一顶顶点点出出发发，，对对图图中中的的所所有有顶顶点点访访问问一一次次，，而而且且仅仅访访问问一一次次图图的的遍遍历历是是图图的的一一种种基基本本操操作作由由于于图图结结构构本本身身的的复复杂杂性性，，所所以以图图的遍历操作也较复杂，主要表现在以下四个方面：的遍历操作也较复杂，主要表现在以下四个方面：（（1））在在图图结结构构中中，，每每一一个个结结点点的的地地位位都都是是相相同同的的，，没没有有一一个个“自自然然”的的首首结结点点，，图图中中任任意意一一个个顶顶点点都都可可作作为为访访问问的的起起始结点2））在在非非连连通通图图中中，，从从一一个个顶顶点点出出发发，，只只能能够够访访问问它它所所在在的的连连通通分分量量上上的的所所有有顶顶点点，，因因此此，，还还需需考考虑虑如如何何访访问问图图中中其其余的连通分量余的连通分量3））在在图图结结构构中中，，如如果果有有回回路路存存在在，，那那么么一一个个顶顶点点被被访访问问之后，有可能沿回路又回到该顶点之后，有可能沿回路又回到该顶点。 4））在在图图中中，，一一个个顶顶点点可可以以和和其其它它多多个个顶顶点点相相连连，，当当这这个个顶点访问过后，就要考虑如何选取下一个要访问的顶点顶点访问过后，就要考虑如何选取下一个要访问的顶点 7-3-1 深度优先搜索深度优先搜索 深深度度优优先先搜搜索索（（Depth-Fisrst Search））遍遍历历类类似似于于树树的的先先根遍历，是树的先根遍历的推广根遍历，是树的先根遍历的推广 假假设设初初始始状状态态是是图图中中所所有有顶顶点点未未曾曾被被访访问问，，则则深深度度优优先先搜搜索索可可从从图图中中某某个个顶顶点点发发v出出发发，，首首先先访访问问此此顶顶点点，，然然后后任任选选一一个个v的的未未被被访访问问的的邻邻接接点点w出出发发，，继继续续进进行行深深度度优优先先搜搜索索，，直直到到图图中中所所有有和和v路路径径相相通通的的顶顶点点都都被被访访问问到到；；若若此此时时图图中中还还有有顶顶点点未未被被访访问问到到，，则则另另选选一一个个未未被被访访问问的的顶顶点点作作为为起始点，重复上面的做法，直至图中所有的顶点都被访问起始点，重复上面的做法，直至图中所有的顶点都被访问。 V1V5V2V4V8V3V6V7图图7-13 无向图无向图G5 以以图图7-13的的无无向向图图G5为为例例，，其其深深度度优优先先搜搜索索得得到到的的顶顶点点访访问问序列为：序列为： v1 → v2 → v4 → v8 → v5 → v3 → v6 、、 → v7 显显然然，，以以上上方方法法是是一一个个递递归归的的过过程程为为了了在在遍遍历历过过程程中中便便于于区区分分顶顶点点是是否否已已被被访访问问，，需需附附设设访访问问标标志志数数组组visited[0:n-1], ，，其其初初值值为为FALSE ，，一一旦旦某某个个顶顶点点被被访访问问，，则其相应的分量置为则其相应的分量置为TRUE 从从图图的的某某一一点点v出出发发，，递递归归地地进进行行深深度度优优先先遍遍历历的的过过程程如如下面算法所示下面算法所示 void DFSTraverseM(MGraph *G) { int i; for(i=0;i 因因此此，，遍遍历历图图的的过过程程实实质质上上是是对对每每个个顶顶点点查查找找其其邻邻接接点点的的过过程程其其耗耗费费的的时时间间则则取取决决于于所所采采用用的的存存储储结结构构当当用用二二维维数数组组表表示示邻邻接接矩矩阵阵图图的的存存储储结结构构时时，，查查找找每每个个顶顶点点的的邻邻接点所需时间为接点所需时间为O(n2) ，，其中其中n为图中顶点数为图中顶点数 当当以以邻邻接接表表作作图图的的存存储储结结构构时时，，找找邻邻接接点点所所需需时时间间为为O(e)，，其其中中e为为无无向向图图中中边边的的数数或或有有向向图图中中弧弧的的数数由由此此，，当当以以邻邻接接表表作作存存储储结结构构时时，，深深度度优优先先搜搜索索遍遍历历图图的的时时间间复复杂杂度为度为O(n+e) 7-3-2广度优先搜索广度优先搜索 广度优先搜索广度优先搜索 遍历类似于树的按层次遍历遍历类似于树的按层次遍历 假假设设从从图图中中某某顶顶点点v出出发发，，在在访访问问了了v之之后后依依次次访访问问v的的各各个个未未曾曾访访问问过过的的邻邻接接点点，，然然后后分分别别从从这这些些邻邻接接点点出出发发依依次次访访问问它它们们的的邻邻接接点点，，并并使使“先先被被访访问问的的顶顶点点的的邻邻接接点点”先先于于“后后被被访访问问的的顶顶点点的的邻邻接接点点”被被访访问问，，直直至至图图中中所所有有已已被被访访问问的的顶顶点点的的邻邻接接点点都都被被访访问问到到。 若若此此时时图图中中尚尚有有顶顶点点未未被被访访问问，，则则另另选选图图中中一一个个未未曾曾被被访访问问的的顶顶点点作作起起始始点点，，重重复复上上述述过过程程，，直直至至图图中中所所有有顶顶点点都都被被访访问问到到为为止止换换句句话话说说，，广广度度优优先先搜搜索索遍遍历历图图的的过过程程中中以以v为为起起始始点点，，由由近近至至远远，，依依次次访访问问和和v有有路径相通且路径长度为路径相通且路径长度为1,2,…的顶点 对对图图7-13无无向向图图G5 进进行行广广度度优优先先搜搜索索遍遍历历，，首首先先访访问问v1 和和v1的的邻邻接接点点v2和和v3，，然然后后依依次次访访问问v2 的的邻邻接接点点v4 和和v5 及及v3 的的邻邻接接点点v6和和v7，，最最后后访访问问v4 的的邻邻接接点点v8由由于于这这些些顶顶点点的的邻邻接接点点均均已已被被访访问问，，并并且且图图中中所所有有顶顶点点都都被被访访问问，，由由些些完完成成了了图图的的遍遍历历得得到到的顶点访问序列为：的顶点访问序列为： v1→v2 →v3 →v4→ v5→ v6→ v7 →v8 和和深深度度优优先先搜搜索索类类似似，，在在遍遍历历的的过过程程中中也也需需要要一一个个访访问问标标志志数数组组。 并并且且，，为为了了顺顺次次访访问问路路径径长长度度为为2、、3、、…的的顶顶点点，，需需附附设设队队列列以以存存储储已已被被访访问问的的路路径径长长度度为为1、、2、、… 的顶点V1V5V2V4V8V3V6V7图图7-13 无向图无向图G5 从从图图的的某某一一点点v出出发发，，递递归归地地进进行行广广度度优优先先遍遍历历的的过过程程如如下面的算法所示下面的算法所示 void BFSTraverseM(MGraph *G){ int i; for (i=0;i 遍遍历历图图的的过过程程实实质质是是通通过过边边或或弧弧找找邻邻接接点点的的过过程程，，因因此此广广度度优优先先搜搜索索遍遍历历图图和和深深度度优优先先搜搜索索遍遍历历的的时时间间复复杂杂度度是是相相同同的的，，两两者不同之处仅仅在于对顶点访问的顺序不同者不同之处仅仅在于对顶点访问的顺序不同 判判定定一一个个图图的的连连通通性性是是图图的的一一个个应应用用问问题题，，我我们们可可以以利利用用图图的的遍遍历历算算法法来来求求解解这这一一问问题题本本节节将将讨讨论论无无向向图图的的连通性问题，并讨论最小代价生成树等问题连通性问题，并讨论最小代价生成树等问题 7-4-1 7-4-1 无向图的连通分量和生成树无向图的连通分量和生成树 在在对对无无向向图图进进行行遍遍历历时时，，对对于于连连通通图图，，仅仅需需从从图图中中任任一一顶顶点点出出发发，，进进行行深深度度优优先先搜搜索索或或广广度度优优先先搜搜索索，，便便可可访访问问到到图图中中所所有有顶顶点点对对非非连连通通图图，，则则需需从从多多个个顶顶点点出出发发进进行行搜搜索索，，而而每每一一次次从从一一个个新新的的起起始始点点出出发发进进行行搜搜索索过过程程中中得到的顶点访问序列恰为其各个连通分量中的顶点集。 得到的顶点访问序列恰为其各个连通分量中的顶点集 例例如如，，图图7-14 (a)是是一一个个非非连连通通图图G6，，按按照照图图7-14 (b) 所示所示G3 的邻接表进行深度优先搜索遍历的邻接表进行深度优先搜索遍历AEBFCD 图图7-14(a) 非连通图非连通图 图图7-14(b) G6的邻接表的邻接表 两两次次调调用用DFS过过程程（（即即分分别别从从顶顶点点A 和和D出出发发）），，得得到到的顶点访问序列为：的顶点访问序列为： A B F E C E 这这两两个个顶顶点点集集分分别别加加上上所所有有依依附附于于这这些些顶顶点点的的边边，，便便构成了非连通图构成了非连通图G3的两个连通分量的两个连通分量 因因此此，，要要想想判判定定一一个个无无向向图图是是否否为为连连通通图图，，或或有有几几个个连连通通分分量量，，就就可可设设一一个个计计数数变变量量count，，初初始始时时取取值值为为0，，在在深深度度优优先先搜搜索索算算法法循循环环中中，，每每调调用用一一次次DFS，，就就给给count增增1。 这这样样，，当当整整个个算算法法结结束束时时，，依依据据count 的的值值，，就就可可确确定定图的连通性了图的连通性了 设设E(G)E(G)为为连连通通图图G G中中所所有有边边的的集集合合，，则则从从图图中中任任一一顶顶点点出出发发遍遍历历图图时时，，必必定定将将E(G)E(G)分分成成两两个个集集合合T(G)T(G)和和B(G)B(G)，，其其中中T(G)T(G)是是遍遍历历图图过过程程中中历历经经的的边边的的集集合合；；B(G)B(G)是是剩剩余余的的边边的的集集合合显显然然，，T(G)T(G)和和图图G G中中所所有有顶顶点点一一起起构构成成连连通通图图G G的的极小连通子图极小连通子图 按按照照7-1-27-1-2节节的的定定义义，，它它是是连连通通图图的的一一棵棵生生成成树树，，并并且且由由深深度度优优先先搜搜索索得得到到的的为为深深度度优优先先生生成成树树；；由由广广度度优优先先搜搜索索得得到到的的为为广广度度优优先先生生成成树树例例如如，，图图7-15(7-15(a)a)和和( (b)b)所所示示分分别别为为图图7-137-13连连通通图图G5G5的的深深度度优优先先生生成成树树和和广广度度优优先先生生成成树树。 图图中中虚线为集合虚线为集合B(G) B(G) 中的边，实线为集合中的边，实线为集合T(G)T(G)中的边图图7-15(a) G5的深度优先生成树的深度优先生成树图图7-15(b) G5的的广度优先生成树广度优先生成树V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7 对对于于非非连连通通图图，，通通过过这这样样的的遍遍历历，，将将得得到到的的是是生生成成森森林林例例如如，，图图7-16 7-16 ( (b) b) 所所示示为为图图7-16 7-16 ( (a)a)的的深深度优先生成森林，它由三棵深度优先生成树组成度优先生成森林，它由三棵深度优先生成树组成图图7-16(a) 非连通无向图非连通无向图G7图图7-16(b) G7的深度优先生成树林的深度优先生成树林JHKLMAICFGBDEJHKLMAICFGBDE 7-4-2 7-4-2 最小生成树最小生成树1 1．最小生成树的基本概念．最小生成树的基本概念 由由生生成成树树的的定定义义可可知知，，无无向向连连通通图图的的生生成成树树不不一一定定是是唯唯一一的的连连通通图图的的一一次次遍遍历历所所经经过过的的边边的的集集合合及及图图中中所所有有顶顶点点的的集集合合就就构构成成了了该该图图的的一一棵棵生生成成树树，，对对连连通通图图的的不不同同遍遍历历，，就就可可能能得得到到不不同同的的生生成成树树。 图图7-17 (a)、、(b)和和(c)所示的均为图所示的均为图7-13的无向连通图的无向连通图G5的生成树的生成树V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7 图图7-17 7-17 无向连通图无向连通图G5G5的三棵生成树的三棵生成树（（a））（（b））（（c）） 可可以以证证明明，，对对于于有有n个个顶顶点点的的无无向向连连通通图图，，无无论论其其生生成成树树的形态如何，所有生成树中都有且仅有的形态如何，所有生成树中都有且仅有n-1条边 如如果果无无向向连连通通图图是是一一个个网网，，那那么么，，它它的的所所有有生生成成树树中中必必有一棵边的权值之和为最小的生成树，简称为最小生成树有一棵边的权值之和为最小的生成树，简称为最小生成树 最最小小生生成成树树的的概概念念可可以以应应用用到到许许多多实实际际问问题题中中例例如如有有这这样样一一个个问问题题：：以以尽尽可可能能抵抵的的总总造造价价建建造造城城市市间间的的通通讯讯网网络络，，把把十十个个城城市市联联系系在在一一起起在在这这十十个个城城市市中中，，任任意意两两个个城城市市之之间间都都可可以以建建造造通通讯讯线线路路，，通通讯讯线线路路的的造造价价依依据据城城市市间间的的距距离离不不同同而而有有不不同同的的造造价价，，可可以以构构造造一一个个通通讯讯线线路路造造价价网网络络，，在在网网络络中中，，每每个个顶顶点点表表示示城城市市，，顶顶点点之之间间的的边边表表示示城城市市之之间间可可构构造造通通讯讯线线路路，，每每条条边边的的权权值值表表示示该该条条通通讯讯线线路路的的造造价价，，要要想使总的造价最低，实际上就是寻找该网络的最小生成树。 想使总的造价最低，实际上就是寻找该网络的最小生成树 2．常用的构造最小生成树的方法．常用的构造最小生成树的方法（（1 1）构造最小生成树的）构造最小生成树的PrimPrim算法算法 假假设设G＝＝（（V，，E））为为一一连连通通网网，，顶顶点点集集V={v1，，v2，，…，，vn}，，E为为网网中中所所有有带带权权边边的的集集合合设设置置两两个个新新的的集集合合U和和T，，其其中中集集合合U用用于于存存放放G的的最最小小生生成成树树中中的的顶顶点点，，集集合合T存存放放G的的最最小小生生成成树树中中的的边边令令集集合合U的的初初值值为为U＝＝{v1}（（假假设设构造最小生成树时，从顶点构造最小生成树时，从顶点v1出发），集合出发），集合T的初值为的初值为T＝＝{} Prim算算法法的的基基本本思思想想：：从从所所有有u∈∈U，，v∈∈V－－U的的边边中中，，选选取取具具有有最最小小权权值值的的边边（（u，，v）），，将将顶顶点点v加加入入集集合合U中中，，将将边边（（u，，v））加加入入集集合合T中中，，如如此此不不断断重重复复，，直直到到U＝＝V时时，，最最小小生生成成树树构构造造完完毕毕，，这这时时集集合合T中中包包含含了了最最小小生生成成树树的的所所有有边。 边 图图7-18 (a)所所示示的的一一个个网网，，按按照照Prim方方法法，，从从顶顶点点A出出发发，，该该网网的的最最小小生生成成树树的的产产生生过过程程如如图图7-18 (b)、、(c)、、(d)、、(e)、、(f)所示 图图7-18 Prim 算法构造最小生成树的过程示意图算法构造最小生成树的过程示意图 AEBFCDAEBFCDAEBFCDAEBFCDAEBFCDAEBFCD(a)(b)(c)(d)(e)(f)6812141617515666668888812121214145 （（2 2）构造最小生成树的）构造最小生成树的KruskalKruskal算法算法 KruskalKruskal算算法法是是一一种种按按照照网网中中边边的的权权值值递递增增的的顺顺序序构构造造最最小小生生成成树树的的方方法法其其基基本本思思想想是是：：首首先先选选取取全全部部的的n n个个顶顶点点，，将将其其看看成成n n个个连连通通分分量量；；然然后后按按照照网网中中边边的的权权值值由由小小到到大大的的顺顺序序，，不不断断选选取取当当前前未未被被选选取取的的边边集集中中权权值值最最小小的的边边。 依依据据生生成成树树的的概概念念，，n n个个结结点点的的生生成成树树，，有有n-1n-1条条边边，，故故反反复复上上述述过过程程，，直直到到选选取取了了n-1n-1条条边边为为止止，，就就构构成成了了一一棵棵最最小小生成树 图图7-19 Kruskal 算法构造最小生成树的过程示意图算法构造最小生成树的过程示意图 AEBFCDAEBFCDAEBFCDAEBFCDAEBFCDAEBFCD(a)(b)(c)(d)(e)(f)68121416175155666688885121255145返 回 7-5 最短路径 最最短短路路径径问问题题是是图图的的又又一一个个比比较较典典型型的的应应用用问问题题例例如如，，某某一一地地区区的的一一个个交交通通网网，，给给定定了了该该网网内内的的n个个城城市市以以及及这这些些城城市市之之间间的的相相通通公公路路的的距距离离，，问问题题是是如如何何在在城城市市A和和城城市市B之之间间找找一一条条最最近近的的通通路路如如果果将将城城市市用用顶顶点点表表示示，，城城市市间间的的公公路路用用边边表表示示，，公公路路的的长长度度则则作作为为边边的的权权值值，，那那么么，，这这个个问问题题就就可可归归结结为为在在网网中中，，求求点点A到到点点B的的所所有有路路径径中中，，边边的的权权值值之之和和最最短短的的那那一一条条路路径径。 这这条条路路径径就就称称为为两两点点之之间间的的最最短短路路径径，，并并称称路路径径上上的的第第一一个个顶顶点点为为源源点点（（Sourse）），，最最后后一一个个顶顶点点为为终终点点（（Destination））在在不不带带权权的的图图中中，，最最短短路路径径是是指指两两点之间经历的边数最少的路径点之间经历的边数最少的路径 例例如如在在图图7-20中中，，设设V1为为源源点点，，则则从从V1出出发发的的路路径径有有（括号里为路径长度）：（括号里为路径长度）： V V1 1到到V V2 2的路径有条：的路径有条：V V1 1→V→V2 2(20)(20)V V1 1到到V V3 3的路径有条：的路径有条：V V1 1→V→V3 3(15),V(15),V1 1→V→V2 2→V→V3 3(55)(55)V V1 1到到V V4 4的路径有条：的路径有条：V V1 1→V→V2 2→V→V4 4(30),V(30),V1 1→V→V3 3→V→V4 4(45),V(45),V1 1→V→V2 2→V→V3 3→V→V4 4(85)(85)V V1 1到到V V5 5的路径有条：的路径有条：V V1 1→V→V2 2→V→V3 3→V→V5 5(65),V(65),V1 1→V→V3 3→V→V5 5(25)(25)选出选出V V1 1到其它各顶点的最短路径，并按路径长度递增顺序排列如下：到其它各顶点的最短路径，并按路径长度递增顺序排列如下：V V1 1→V→V3 3(15)(15)，，V V1 1→V→V2 2(20)(20)，，V V1 1→V→V3 3→V→V5 5(25)(25)，，V V1 1→V→V2 2→V→V4 4(30)(30)。 图图7-20 V1 出发的路径出发的路径V1V5V2V4V3201035101530 从从上上面面的的序序列列中中，，可可以以看看出出一一个个规规律律：：按按路路径径长长度度递递增增顺顺序序生生成成从从源源点点到到其其它它各各顶顶点点的的最最短短路路径径时时，，当当前前正正生生成成的的最最短短路路径径上上除除终终点点外外，，其其它它顶顶点点的的最最短短路路径径已已经经生生成成迪迪杰杰斯特拉算法正是根据此规律得到的斯特拉算法正是根据此规律得到的 迪迪杰杰斯斯特特拉拉（（DijkstraDijkstra））算算法法的的基基本本思思想想：：设置置两两个个顶点点集集S S和和T T，，S S中中存存放放已已确确定定最最短短路路径径的的顶点点，，T T中中存存放放待待确确定定最最短短路路径径的的顶点点初初始始时S S中中仅有有一一个个源源点点，，T T中中含含除除源源点点外外其其余余顶点点，，此此时各各顶点点的的当当前前最最短短长度度为源源点点到到该顶点点的的弧弧上上的的权值接接着着选取取T T中中当当前前最最短短路路径径长度度最最小小的的一一个个顶点点v v加加入入S S，，然然后后修修改改T T中中剩剩余余顶点点的的当当前前最最短短路路径径长度度，，修修改改原原则是是：：当当v v的的最最短短路路径径长度度与与v v到到T T中中顶点点之之间的的权值之之和和小小于于该顶点点的的当当前前最最短短路路径径长度度时，，用用前前者者替替换后后者者。 重重复复以以上上过程，直到程，直到S S中包含所有中包含所有顶点 图图7-21 7-21 用迪杰斯特拉算法求有向图的最短路径过程用迪杰斯特拉算法求有向图的最短路径过程 V1V5V2V4V3201035101530V1V5V2V4V32015V1V5V2V4V320101530V1V5V2V4V320101530V1V5V2V4V32010153010 小 结（（1 1））图图是是一一种种复复杂杂的的数数据据结结构构，，图图中中的的每每一一个个顶顶点点都都可可以以有有多多个个直直接接前前驱驱和和多多个个直直接接后后继继，，所所以以是是一一种种非非线线性性的的数数据据结结构2 2））因因为为图图是是由由顶顶点点的的集集合合和和顶顶点点间间边边的的集集合合组组成成，，所所以以图图的存储也包括顶点信息和边的信息两个方面的存储也包括顶点信息和边的信息两个方面3 3）图的存储结构常用的有：邻接矩阵和邻接表等要求掌握图的存储结构常用的有：邻接矩阵和邻接表等要求掌握4 4））对对于于n n个个顶顶点点的的图图来来说说，，它它的的邻邻接接矩矩阵阵是是一一个个n×nn×n阶阶的的方方阵阵邻邻接接矩矩阵阵中中的的元元素素取取值值只只能能是是0 0或或1 1，，若若图图为为无无向向图图，，则则矩矩阵阵一一定定是是对对称称矩矩阵阵，，所所以以可可以以采采用用压压缩缩存存储储；；若若是是网网，，则要存储的是权值。 则要存储的是权值5 5））对对于于由由n n个个顶顶点点和和e e 条条边边的的图图，，它它的的邻邻接接表表由由n n个个单单链链表表所所组组成成无无向向图图的的邻邻接接表表占占用用n+2en+2e个个存存储储单单元元；；有有向向图图的的邻邻接表占用接表占用n+en+e个存储单元个存储单元 （（6 6））图图的的遍遍历历就就是是从从图图的的某某一一顶顶点点出出发发，，访访问问图图中中每每个个顶顶点点一一次次且且仅仅一一次次遍遍历历的的基基本本方方法法有有深深度度优优先先搜搜索索遍遍历历和和广广度度优优先先搜搜索索遍遍历历两两种种深深度度优优先先遍遍历历类类似似于于树树的的先先序序遍遍历历；；广度优先遍历类似于树的按层次遍历广度优先遍历类似于树的按层次遍历7 7））取取一一个个无无向向连连通通图图的的全全部部顶顶点点和和一一部部分分边边构构成成一一个个子子图图，，若若其其中中所所有有顶顶点点仍仍是是连连通通的的，，但但各各边边不不构构成成回回路路，，这这个个子子图图称称为为原原图图的的一一个个生生成成树树，，同同一一个个图图可可以以有有多多个个不不同同的的生生成成树树对对于于带带权权的的图图，，其其各各条条边边权权值值之之和和为为最最小小的的生生成成树树即即最最小小生生成成树树。 求求最最小小生生成成树树的的方方法法，，得得到到最最小小生生成成树树中中边边的的次序也可能不同，但最小生成树的权值之和却相同次序也可能不同，但最小生成树的权值之和却相同8 8）对于带权的有向图，求从某一顶点出发到其余各顶点）对于带权的有向图，求从某一顶点出发到其余各顶点的最短路径（所经过的有向边权值总和最小的路径）或求每的最短路径（所经过的有向边权值总和最小的路径）或求每一顶点之间的最短路径称为最短路径问题一顶点之间的最短路径称为最短路径问题 1 1．实验目的．实验目的（（1 1）） 掌握图邻接矩阵的存储方法；掌握图邻接矩阵的存储方法；（（2 2）） 掌握图深度优先编历的基本思想；掌握图深度优先编历的基本思想；（（3 3）） 掌握图广度优先编历的基本思想掌握图广度优先编历的基本思想2 2．实验内容．实验内容（（1 1）） 编写按键盘输入的数据建立图的邻接矩阵存储；编写按键盘输入的数据建立图的邻接矩阵存储；（（2 2）） 编写图的深度优先编历程序；编写图的深度优先编历程序；（（3 3）） 编写图的广度优先编历程序；编写图的广度优先编历程序；（（4 4）） 设计一个选择式菜单形式如下：设计一个选择式菜单形式如下：实验7 图子系统 图子系统图子系统 ******************************************* ******************************************* * 1------- * 1-------更新邻接矩阵更新邻接矩阵 * * * 2------- * 2-------深度优先遍历深度优先遍历 * * * 3------- * 3-------广度优先遍历广度优先遍历 * * * 0------- * 0-------退退 出出 * * ******************************************* ******************************************* 3 3．操作举例．操作举例（（1 1）） 按下图建立按下图建立图的邻接矩阵存储；图的邻接矩阵存储；AEDCB（（2 2）） 按提示输入：按提示输入： 建立一个有向图的邻接矩阵表示建立一个有向图的邻接矩阵表示请输入顶点数和边数请输入顶点数和边数( (输入格式为输入格式为: :顶点数顶点数, ,边数边数): ): 5,7<5,7 的其它操作 习题7 参见习题解答参见习题解答返 回 。
