《数据结构》图.ppt

第第7章　章　图图7.1　图的定义和术语　图的定义和术语7.2　图的存储结构　图的存储结构7.3　图的遍历　图的遍历7.4　　生成树生成树 7.5　　最短路径最短路径7.6 拓扑排序拓扑排序 习题习题 图是一种较线性表和树更为复杂的数据结构图是一种较线性表和树更为复杂的数据结构在性表线性表中，数据元素之间有中，数据元素之间有线性关系线性关系，每一个数，每一个数据元素只有一个直接前驱和一个直接后续；在据元素只有一个直接前驱和一个直接后续；在树树形形结构中，数据元素之间有着明显的结构中，数据元素之间有着明显的层次关系层次关系，即每，即每一个数据元素有一个直接前驱一个数据元素有一个直接前驱(双亲双亲)和零个或多个和零个或多个直接后续直接后续(孩子孩子)；而在；而在图图形结构中，结点之间的关形结构中，结点之间的关系是系是任意的任意的，图中任意两个数据元素之间都可能相，图中任意两个数据元素之间都可能相关由此，图的应用极为广泛例如，城市间的最关由此，图的应用极为广泛例如，城市间的最短路径，火车的联票，交通网的计划，战场上的运短路径，火车的联票，交通网的计划，战场上的运输问题，庞大的施工进度图等都是图的应用。

输问题，庞大的施工进度图等都是图的应用 7.1 图的定义和术语图的定义和术语定义：定义： 图图(graph)：：是一种数据结构，由二个集合是一种数据结构，由二个集合V和和E组成，组成，记作记作G=(V,E)其中V是数据元素是数据元素(顶点顶点)的非空有限集，的非空有限集，E是是V中二元关系中二元关系(边边edge)的集合树是图的特例，而线性表的集合树是图的特例，而线性表是树的特例是树的特例术语：术语： 有向图：有向图：图的每条边都是有序顶点对图的每条边都是有序顶点对(即边是有方向即边是有方向) 弧：弧：有向图的边并将构成该边的有序顶点对用一对有向图的边并将构成该边的有序顶点对用一对尖括号括起来如尖括号括起来如∈∈E，表示从，表示从顶点顶点u到到顶点顶点v的一条的一条弧弧，称，称u为为弧尾弧尾或或初始点初始点，，v为为弧头弧头或或终端点终端点并且说v是与是与u相邻的顶点相邻的顶点，或，或v是是u的的邻接点邻接点 例如，图例如，图7.1(a)所示的为有向图，它是由集合所示的为有向图，它是由集合 V={v0,v1,v2,v3} E={,,,}组成的。

组成的图图7.1 (a)有向图有向图G1 无向图：无向图：图的每条边是无方向的，有图的每条边是无方向的，有∈∈E，必有，必有∈∈E即用圆括号括起来即用圆括号括起来 (u,v)∈∈E表示边，并且，表示边，并且，u和和v互称为邻接点互称为邻接点  例如，图例如，图7.1(b) 为无向图，它是由集合为无向图，它是由集合 V={ v0,v1,v2,v3,v4 } E={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3) ,(v2,v4)}组成的网络：网络：若图中每条边或弧都附加一个数值作为权若图中每条边或弧都附加一个数值作为权子图：子图：若若G1={V1,E1}，，G2={V2,E2}是两个图，且是两个图，且V2被包含被包含在在V1中，中，E2被包含在被包含在E1中，则称图中，则称图G2是图是图G1的子图度：度：无向图中，顶点的度是依附于该顶点的边数无向图中，顶点的度是依附于该顶点的边数有向图有向图中，中，顶点的顶点的入度入度是以该顶点为是以该顶点为弧头的弧数弧头的弧数，顶点的，顶点的出度出度是以该顶是以该顶点为点为弧尾的弧数弧尾的弧数。

路径：路径：在有向图在有向图(或无向图或无向图)中，如果存在首尾相接并且无重中，如果存在首尾相接并且无重复边的边序列复边的边序列,,…, (或或 (v0,v1),(v1,v2),…,(vn-2,vn-1))，那么称这个序列是一条从顶点到，那么称这个序列是一条从顶点到v0到到vn-1的一条路径，记着的一条路径，记着(v0,v1,v2,…,vn-2,vn-1)序列中的中的边数边数称为称为路径长度路径长度在有向图中，路径是由方向的；而在有向图中，路径是由方向的；而在无向图中，路径无方向在无向图中，路径无方向简单路径：简单路径：在一条路径中，若除起点和终点外，所有顶点彼在一条路径中，若除起点和终点外，所有顶点彼此各不相同此各不相同回路：回路：在一条路径中，若起点和终点是同一顶点在一条路径中，若起点和终点是同一顶点简单回路：简单回路：有简单路径组成的回路称为简单回路有简单路径组成的回路称为简单回路连通：连通：在无向图在无向图G中，若从顶点中，若从顶点vi到顶点到顶点vj有路径存在有路径存在连通图：连通图：在无向图在无向图G中，若任意二个顶点之间都是连通的中，若任意二个顶点之间都是连通的.连通分量：连通分量：在非连通的无向图在非连通的无向图G中，极大连通子图中，极大连通子图(在满足在满足连通条件下，尽可能多的包含连通条件下，尽可能多的包含G中的顶点和这些顶点之间中的顶点和这些顶点之间的边的边) . 如图如图7.2中，图中，图G有三个连通分量。

有三个连通分量 (a)有向图G (b)图G的三个连通分量强连通：强连通：在有向图在有向图G中，若从顶点中，若从顶点vi到顶点到顶点vj有路径存在，有路径存在，并且从顶点并且从顶点vj到顶点到顶点vi也有路径存在也有路径存在强连通图：强连通图：在有向图在有向图G中，若任意二个顶点之间都是强连通中，若任意二个顶点之间都是强连通的 强连通分量：在非强连通的有向图强连通分量：在非强连通的有向图G中，极大强连通中，极大强连通子图称为有向图的强连通分量如图子图称为有向图的强连通分量如图7.3中，有向图中，有向图G有两有两个强连通分量个强连通分量生成树：生成树：在一个有在一个有n顶点的连通图顶点的连通图G中，存在一个极小的连中，存在一个极小的连通子图通子图G′，，G′包含图包含图G的所有顶点，但只有的所有顶点，但只有n-1条边，并且条边，并且G′是连通的是连通的a)有向图G                            (b)图G的二个强连通分量 图7.3  有向图及其强连通分量 7.2 图的存储结构图的存储结构 常用的图的存储结构有邻接矩阵、邻接表、十字链表、常用的图的存储结构有邻接矩阵、邻接表、十字链表、多重链表等方法。

本节介绍最为常用的邻接矩阵和邻接表多重链表等方法本节介绍最为常用的邻接矩阵和邻接表方法对图的存储结构的选择取决于具体的应用对图的存储结构的选择取决于具体的应用7.2.1 邻接矩阵邻接矩阵(1)存储形式存储形式 邻接矩阵是用一个邻接矩阵是用一个二维数组二维数组来表示图中顶点间的相邻来表示图中顶点间的相邻关系数据结构关系数据结构 设图设图G=(V,E)，有，有n≥1个顶点，则所对应图个顶点，则所对应图G的邻接矩阵的邻接矩阵A是按如下定义的一个是按如下定义的一个n×n的二维数组的二维数组若图若图G是一个网络，其邻接矩阵是一个网络，其邻接矩阵 借助于邻接矩阵很容易判定任意两个顶点之间是否有边借助于邻接矩阵很容易判定任意两个顶点之间是否有边(或或弧弧)相连，并容易求得各个顶点的度，操作方便相连，并容易求得各个顶点的度，操作方便 (2)基本操作基本操作        (1)求无向图某顶点求无向图某顶点vi的度的度(有向图中有向图中vi的出度的出度)即数组A中第中第i行的非零元素的个数，是顶点行的非零元素的个数，是顶点vi的度的度(出度出度) (2)求有向图某顶点求有向图某顶点vi的入度。

的入度 即数组即数组A中第中第i列的非零元列的非零元素的个数，是顶点素的个数，是顶点vi的入度 (3)检测图中的总边检测图中的总边(弧弧)数扫描整个数组数扫描整个数组A，统计出数组，统计出数组中非零元素的个数无向图的总边数为非零元素个数的一半，中非零元素的个数无向图的总边数为非零元素个数的一半，而有向图的总弧数为非零元素个数而有向图的总弧数为非零元素个数 7.2.2 邻接表邻接表(1)存储形式存储形式 对一个有对一个有n个顶点图的顶点进行编号，顶点的编号从个顶点图的顶点进行编号，顶点的编号从0到到n-1图的邻接表邻接表存储结构与存储结构与树的孩子表示法相同树的孩子表示法相同将图G中每个顶点中每个顶点vi的所有的所有邻接点邻接点用用一个单链表一个单链表(邻接点链表邻接点链表)表示，表示，在在vi的邻接点链表中存放的邻接点链表中存放vj(有有(vi,vj)或或∈∈E)的编号，的编号，以及其它与该边或弧相关的信息一个图有以及其它与该边或弧相关的信息一个图有n个顶点个顶点就有就有n个个邻接点链表邻接点链表(度为度为0的顶点，所对应的邻接点链表为空表的顶点，所对应的邻接点链表为空表)。

这这n个邻接点个邻接点链表的头指针又构成一个线性表链表的头指针又构成一个线性表，用一个指针，用一个指针数组存储该线性表，这样就构成了图的邻接表的存储结构数组存储该线性表，这样就构成了图的邻接表的存储结构例如，在图例如，在图7.1中，中，G1和和G2的的邻接表如图的的邻接表如图7.5所示，图中下所示，图中下标对应顶点标对应顶点vi的编号  在图在图7.5中，存在两种数据结构：一种是顶点结构，存储中，存在两种数据结构：一种是顶点结构，存储顶点编号、属性等相关的信息；一种是边、弧结构，存顶点编号、属性等相关的信息；一种是边、弧结构，存储弧头结点的编号、权值等信息出于简化结构、算法储弧头结点的编号、权值等信息出于简化结构、算法的考虑，这里将这两种数据结构合并为一种结构的考虑，这里将这两种数据结构合并为一种结构 (a)G1的邻接表                           (b)G2的邻接表 图7.5  邻接表存储结构 用用C语言定义的存储结构如下语言定义的存储结构如下:邻接点链表的节点：邻接点链表的节点：typedef struct ALGNode { int ID;　　　　　　　　 struct ALGNode *link;}ALGNode;当用当用ALGNode表示顶点结构时，表示顶点结构时，ID域存储为顶点的编号；域存储为顶点的编号；当用当用ALGNode表示边、弧结构时，表示边、弧结构时，ID域为弧头结点的编域为弧头结点的编号。

号邻接表的整体结构定义如下邻接表的整体结构定义如下：：#define MAX_VEXS 1000typedef struct { ALGNode adjlist[MAX_VEXS]; /* /* 顶点数组顶点数组 * */ / int vexs,arcs; /* /* vexsvexs为顶点数为顶点数,arcs,arcs为弧结点数为弧结点数 * */ /}ALGraph; 逆邻接表：逆邻接表：对于为网络的图对于为网络的图G=(V,E)，在，在node结构中可以添结构中可以添加一个权值域而对于有向图，图加一个权值域而对于有向图，图7.5(a)所示为按所示为按G1出度建立出度建立的邻接表，在该邻接表中求每个顶点的邻接表，在该邻接表中求每个顶点vi的出度和以的出度和以vi为尾的弧为尾的弧方便，但若要求顶点的入度，必须遍历整个邻接表所以，有方便，但若要求顶点的入度，必须遍历整个邻接表所以，有时为了使求顶点时为了使求顶点vi的入度和以的入度和以vi为头的弧方便，可以建立该有为头的弧方便，可以建立该有向图的逆邻接表，即在向图的逆邻接表，即在vi的邻接点链表中存放的邻接点链表中存放vj(有有∈∈E)的编号。

如图的编号如图7.6所示为图所示为图7.1(a)中中G1的逆邻接表的逆邻接表图7.6  G1的逆邻接表 (2)建立邻接表的算法建立邻接表的算法算法算法7.1 建立有向图邻接表的算法建立有向图邻接表的算法/* /* 初始化一个邻接表结构，有初始化一个邻接表结构，有n n个顶点，无弧个顶点，无弧 */ /void ALGraph_Init(ALGraph *G, int n){ int i; G->vexs=n; G->arcs=0; // n// n为顶点数为顶点数 for(i=0; iadjlist[i].ID=i; // // 顶点编号取为顶点的下标顶点编号取为顶点的下标 G->adjlist[i].link=NULL; } } /* /* 在邻接表结构中，插入一个弧结点在邻接表结构中，插入一个弧结点 */ */ void ALGraph_Insert(ALGraph *G,int v1,int v2) { ALGNode *p; p=(ALGNode *)malloc(sizeof(ALGNode)); p->ID=v2; p->link=G->adjlist[v1].link; G->adjlist[v1].link=p; // // 插入在弧链表的首部插入在弧链表的首部 G->arcs++; } /* /* 建立图的邻接表结构建立图的邻接表结构 * */ /void ALGraph_Create(ALGraph *G){ int vn,en,i, v1,v2;  /* /* 结点数结点数vnvn, , 弧数弧数vnvn */ */   scanf("%d,%d",&vn, &en);    ALGraph_Init(G, vn);   for(i=0; i

(3)基本操作基本操作    (a)求无向图顶点求无向图顶点vi的度的度(有向图顶点有向图顶点vi的出度的出度)遍历顶点遍历顶点vi的邻接点链表，统计出邻接点链表中的结的邻接点链表，统计出邻接点链表中的结点数该结点数为顶点点数该结点数为顶点vi的出度在有向图的出度在有向图G中，如中，如何求顶点何求顶点i的出度？下面是一个求顶点出度的算法的出度？下面是一个求顶点出度的算法算法算法7.2求顶点出度的算法求顶点出度的算法 int ALGraph_OutDegree(ALGraph G, int i) { int n;  ALGNode *p;    for(n=0, p=G.adjlist[i].link; p; p=p->link)  n++;    return(n); }(b)求有向图顶点求有向图顶点vi的入度的入度对图中所有顶点的邻接点链对图中所有顶点的邻接点链表进行遍历，统计表进行遍历，统计vertex=i的结点数该结点数为顶点的结点数该结点数为顶点vi的的入度在有向图入度在有向图G中，如何求顶点中，如何求顶点i的入度？的入度？算法算法7.3 求顶点入度的算法求顶点入度的算法int ALGraph_InDegree(ALGraph G, int i){ ALGNode *p;  int j, n;  for(n=0,j=0; jlink)       if(p->ID==i)  n++;  return(n)}   (c)检测图中的总边检测图中的总边(弧弧)数数。

对图对图G=(V,E)中所有顶点的中所有顶点的邻接点链表进行遍历，统计所有邻接点链表的结点数之和邻接点链表进行遍历，统计所有邻接点链表的结点数之和无向图的边数为结点数之和的一半，而有向图的弧数为结无向图的边数为结点数之和的一半，而有向图的弧数为结点数之和点数之和7.3 图的遍历图的遍历•与树的遍历相同，把按一定的规律沿着图中的边访问图与树的遍历相同，把按一定的规律沿着图中的边访问图的每个顶点，并且使的每个顶点，并且使每一个顶点只被访问一次的过程称每一个顶点只被访问一次的过程称为图的遍历为图的遍历•因为在图中任意两个顶点之间都可能有关系为保证每因为在图中任意两个顶点之间都可能有关系为保证每一个顶点只被访问一次，必须对访问过的顶点进行标记，一个顶点只被访问一次，必须对访问过的顶点进行标记，一般是用一般是用一个辅助数组一个辅助数组visit[MAX]作为作为对顶点的标记对顶点的标记当顶点当顶点vi未被访问未被访问，，visit[i]值值为为0；当顶点；当顶点vi已被访问已被访问，，则则visit[i]值值为为1•图的遍历方法通常有图的遍历方法通常有先深度遍历先深度遍历和和先广度遍历先广度遍历两种。

但两种但经常称这两种遍历为深度优先搜索经常称这两种遍历为深度优先搜索DFS和广度优先搜索和广度优先搜索BFS7.3.1    深度优先搜索深度优先搜索DFS(Depth First Search)      图的深度优先搜索是树的先序遍历的推广，其定义(递归)如下：      (1)从图G=(V,E)中选任意某个未访问过的顶点vi作为搜索的出发点     (2)访问vi     (3)以vi的每一个未被访问过的邻接点w为出发点，深度优先搜索图G    (4)直至图G中所有与vi有路径相通的顶点都被访问过    (5)若图G中尚有顶点未曾访问过，则转到(1)；否则，搜索结束定义数组与标记#define FALSE 0#define TRUE  1int visited[MAX];   /* /* 访问标记数组，取值为访问标记数组，取值为FALSEFALSE或或TRUE */TRUE */算法算法7.4 图G的深度优先搜索算法(图G采用邻接点链表存储)void DFSTraverse(ALGraph G) { int v;   for(v=0; vlink)        if(!visited[p->ID]) DFS(G, p->ID);}main(){ ALGraph G;    ALGraph_Create(&G); /* /* 建立图建立图G G的邻接表的邻接表 * */ /     DFSTraverse(G);     /* /* 对图对图G G调用深度搜索算法调用深度搜索算法 * */ /} }7.3.2 广度优先搜索广度优先搜索BFS(Breadth First Search)    图的广度优先搜索与按层次遍历树相似，定义如下：    (1)从图G=(V,E)中选任意某个未访问过的顶点vi作为搜索的出发点。

    (2)访问vi    (3)依次访问vi的各个未曾访问过的邻接点分别从这些邻接点出发进行广度优先搜索，直至图中所有与vi有路径相通的顶点都被访问过    (4)若图中尚有顶点未曾访问过，则转到(1)；否则，搜索结束 算法算法7.6 图G的广度优先搜索算法void BFSTraverse(ALGraph G) { int v;   for(v=0; vlink)            if(visited[p->ID]==FALSE)  /* v的邻接点未搜索过  */              { Q[rear]=p->ID;  rear++; }  /* v的邻接点进队列Q */     } }main(){ ALGraph G;     ALGraph_Create(&G); /* 建立图G的邻接表 */   BFSTraverse(G);     /* 对图G调用广度搜索算法 */}7.4 生成树生成树 7.4.1 概念概念 生成树是一个连通图生成树是一个连通图G的一个极小的连通子图。

包的一个极小的连通子图包含图含图G的所有顶点，但只有的所有顶点，但只有n-1条边条边，并且是，并且是连通的连通的在生成树中，生成树中，不存在回路路径不存在回路路径，但若在生成树中任意增加，但若在生成树中任意增加一条边，则必构成回路一个连通图的生成树不是惟一一条边，则必构成回路一个连通图的生成树不是惟一的，例如，对一个连通图进行深度优先，在搜索过程中的，例如，对一个连通图进行深度优先，在搜索过程中经过的边和图的顶点，构成深度优先生成树；若进行广经过的边和图的顶点，构成深度优先生成树；若进行广度优先搜索，则构成广度优先生成树非连通图有若干度优先搜索，则构成广度优先生成树非连通图有若干个连通分量组成，每一个连通分量都存在生成树，这样个连通分量组成，每一个连通分量都存在生成树，这样就构成生成森林就构成生成森林7.4.2 最小生成树最小生成树(最小支撑树最小支撑树)        若有一个连通的无向图G，它有n个顶点，并且它的边是有权值的在图G上构造生成树G’(n个顶点，n-1条边，G’是连通的)，因为生成树的非惟一性，则有多个G’存在，而最小生成树是n-1条边的权值之和最小的G’最小生成树也是非惟一的，但图G所有最小生成树的n-1条边的权值之和相同，并且为最小值。

        例如，用带权的连通无向图G表示n个城市之间的交通网，最小生成树问题是：如何确定n-1条线路连通这n个城市，并且代价最小        在带权的连通无向图G=(V,E)上，构造最小生成树有普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法，它们都是利用最小生成树中简称为MST的性质：U是顶点集V的一个非空子集，若(u,v)是一条具有最小权值的边，其中u∈U，v∈V-U，则必存在一棵包含边(u,v)的最小生成树(1)普里姆普里姆(Prim)算法算法      该算法是利用MST性质，描述如下：      假设G=(V,E)是带权的连通无向图，从u0∈V开始构造G上最小生成树G’=(U,TE)，初始U={u0}，TE=φ重复以下步骤：在所有的u∈U(生成树中的顶点)，v∈V-U(尚不在生成树中的顶点)，且(u,v)∈E中找一条权值最小的边(u0,v0)并入TE，同时v0并入U，直至U=V时结束此时，TE中包含n-1条边，并使n个顶点连通，且权值之和最小如图7.8所示，其为在一个带权的连通无向图G中，构造最小生成树的过程       为实现这个算法需要引入辅助数组辅助数组closest[]和lowcost[]记录从U到V-U的权值最小的边。

closest[i]=j(i∈V-U ,j∈U) ，表示顶点i到j的一条边(j,i)，同时(j,i)是U到V-U中的顶点i权值最小的边j,i)的权值存放在lowcost[i]中图7.8  普里姆算法构造最小生成树过程   在图7.8(c)中，U={0,2,5}，V-U={1,3,4}，对于U-V中的顶点1到U中的顶点的边有：(0,1)=6，(2,1)=5，(5,1)=∞，所以，U到顶点1权值最小的边是(2,1)=5，则 closest[1]=2同样，可求出closest[3]=5，closest[4]=2它们所对应的lowcost数组分别是：lowcost[1]=(2,1)=5，lowcost[3]= (5,3)=2，lowcost[4]=(2,4)=6       图7.9所示为图7.8构造最小生成树过程中，辅助数组closest[]和lowcost[]的变化情况，在这里，对于顶点j∈U，其lowcost[j]=O      若图G=(V,E)采用邻接矩阵表示，邻接矩阵所对应的二维数组是cost[MAX][MAX]则普里姆算法如下：        (1)初始化(U={0})，closest[i]=0;lowcost[i]=cost[0][i];lowcost[0]=0；(i=1,2,…,n-1)。

      (2)每次扫描数组lowcost[]，找出值最小且不为0的lowcost[k]，得到边最小生成树的一条边(closest[k],k)，将其输出；    (3)令lowest[k]=0，将k并入U中；   (4)修改数组closest[i]和lowcost[i]（lowcost[i]!=0及i∈V-U）；   (5)重复(2)、(3)、(4)，直到U=V（或循环n-1次）结束 下标i 0   1 2 3 4 5    U    V-U 1closest[i]  0   0  0    0    0   0    {0}{1,2,3,4,5}Lowcost[i] 0  6 1  5 ∞∞2closest[i] 0  2 0  0   2   2   {0,2} {1,3,4,5}lowcost[i] 0  5 0  5   6   43 closest[i] 0  2 0  5   2   2  {0,2,5}  {1,3,4,}lowcost[i] 0  5 0  2   6   04closest[i] 0  2 0  5   2   2 {0,2,3,5}     {1,4}lowcost[i] 0  5 0  0   6   05closest[i] 0  2 0  5   1   2{0,1,2,3,5}     {4}lowcost[i] 0  0 0  0   3   06closest[i] 0  2 0  5   1   2{0,1,2,3,4,5}      фlowcost[i] 0  0 0  0   0   0      图7.9  图7.8构造最小生成树过程中辅助数组的值     算法算法7.6 最小生成树的普里姆算法最小生成树的普里姆算法。

    void prim(int cost[][N],int start_v) /* start_v为出发点的序号 */     { int closest[N],lowcost[N],i,j,k,min;      for(i=0;i

算法描述如下：       设带权的连通无向图G=(V,E)，有n个顶点最小生成树的初始状态为有n个顶点但无边的非连通图T=(V,φ)，图中每个顶点自成一个连通分量        (1)将E中的边按权值的递增顺序排序，选择权值最小的边，若与该边相关的顶点落在T中不同连通分量上，则将其加入到T中；否则，将其舍弃      (2)循环至所有顶点在同一连通分量上如何识别一条边所相关的顶点是否落在一个连通分量上？在此采用集合的方法，即将在一个连通分量上的所有顶点看成一个集合当从E中取得一条边(xi,xj)后，若xi和xj在同一个集合u中，则将该边舍弃；否则，则将该边加入到T中，并将xj所在的集合v并入集合u为此引入辅助数组sets[]图7.10  克鲁斯卡尔算法构造最小生成树的过程        ①初始化：图G中的n个顶点，构成n个连通分量顶点xi对应的连通分量用集合i表示，所以sets[i]=i，即表示第i个顶点在集合i中       ②依次取出的E中的边(按边权值递增顺序)，设取出的边(xi,xj)      ③判断：若sets[i]=sets[j]，则表示xi和xj在同一个集合中，返回②；否则，xi和xj在不同集合中，则表示xi和xj落在不同连通分量上，转到④。

      ④将边(xi,xj)并入T，同时将xj所在集合v(与xj连通的顶点)并入xi所在集合u(与xi连通的顶点)，即：由v=sets[j]和u=sets[i]，扫描辅助数组sets[]，若sets[k]=v，则将sets[k]=u      ⑤重复②、③、④，取出n-1条边     例如，图7.10所示为依照克鲁斯卡尔算法构造一棵最小生成树的过程sets[]是辅助数组状态在克鲁斯卡尔算法中，数据结构定义如下define MAX 50  /* 最大边数 */typedef struct        /* 图的存储结构 */ { int begin,end;     /* 边的相关顶点编号 */   int cost; } EDGE;   /* 边的权值 */ EDGE edges[MAX];  /* 存放边的数组 */ int num;          /* edges[]中实际存储的边数 */算法算法7.7 最小生成树的克鲁斯卡尔算法：    int kruskal(EDGE edges[],int num)    /* edges[]边是按权值递增有序，图中边数为num */    { int sets[N], t,i,j,k,u,v;      for(i=0;i

例城市之间的距离，可能有这样一种问题存在例如，如，A城到城到B城是否有通路；城是否有通路；A城到城到B城的哪条通城的哪条通路代价最低路代价最低(距离最短距离最短)上述的问题就是最短路上述的问题就是最短路径问题• 这里讨论的图是带权有向图，并称路径的起始这里讨论的图是带权有向图，并称路径的起始点为源点，路径的最后端点为终点下面讨论两点为源点，路径的最后端点为终点下面讨论两种最常见的最短路径问题，并给出最短路径问题种最常见的最短路径问题，并给出最短路径问题的算法7.5.1 求求某源点到其余各顶点的最短路径某源点到其余各顶点的最短路径       定义：给定带权值的有向图G=(V,E)，E中每条弧有非负的权指定V中的一个顶点v作为源点，求从v出发到G中其余各顶点的最短路径，被称为单源最短路径问题      算法：采用迪杰斯特拉(Dijkstra)算法，解决单源最短路径问题即按路径长度递增的次序产生最短路径      图G采用邻接矩阵cost[][]存储，定义一个辅助数组dist[N]把G=(V,E)的顶点集合V划分成U和V-U，U为从v出发，已确定最短路径终点集合，初始状态为{v}，V-U为尚未确定最短路径顶点集合.      算法描述如下：       (1)对从v出发，已确定为最短路径终点的顶点vi(i∈U)，所对应的数组分量dist[i]的值为负数；对从v出发，尚未确定为最短路径终点的顶点vj(j∈V-U)，所对应的数组分量dist[j]的值为Wvj，而Wvj为从v出发，考虑途经已确定为终点的顶点，到达vj的最短路径。

初始时，对j∈V-U，则有dist[j]=cost[v][j]；而对U={v}，则有dist[v]=-cost[v][v](或为零)     (2)扫描dist[]数组，找出非零、非负且最小dist[j](j∈V-U)，即在当前情况下，从顶点v出发到顶点vj的路径是最短的    (3)vj并入集合U，则dist[j]=-dist[j]    (4)调整dist[k](k∈V-U)，考虑从v出发，途经vj到达vk是否更短比较：            若  -dist[j]+cost[j][k]

    void dijkstra(int cost[][N],int v)    /* 对采用邻接矩阵存cost储的图G，从顶点v出发，求单源最短路径 */     { int dist[N],i,j,w;       for(i=0;i0)   /* vk是尚未到达的终点 */     if(-dist[j]+cost[j][k]=0 && dist[i]

7.5.2 每对顶点之间的最短路径每对顶点之间的最短路径      对带有权值的有向图G=(V,E)中任意一对顶点(u,v)，求u到v的最短路径，被称为每对顶点之间的最短路径问题对该问题的解决有两种方法：其一，每次以一个顶点为源点，重复执行Dijkstra算法这样，便可求得每对顶点之间的最短路径总时间复杂度为o(n3)其二，采用弗洛伊德(Floyd)算法，这里主要讨论该算法      对有向图G，采用带权邻接矩阵cost[][]存储同时定义一个二维数组A[N][N]，其每一个分量A[i][j]的值是顶点i到顶点j的最短路径弗洛伊德算法的基本思想是：       (1)初始时，对图中任意两个顶点vi和vj，如果从vi到vj存在弧，则从vi到vj存在一条长度为cost[i][j]的路径，但该路径不一定是最短路径，还需要进行n次试探，即考虑从vi出发途经vk(k=0,2,…,n-1)到达vj是否距离更短             初始化A[i][j]=cost[i][j]（没有考虑途经其它顶点）        (2)对图中任意两个顶点vi和vj之间的路径，考虑途经vk(k=0)的路径(vi,vk,vj)是否存在。

若存在，则比较途经vk(k=0)是否距离更短，即：比较A[i][k]+A[k][j]和A[i][j] (前者为途经vk的距离，而后者为没有考虑途经vk的距离)，较小者送A[i][j]       (3)重复(2)，从vi出发，考虑途经vk(k=1,2,3,…,n-1)到达vj的距离是否更短        n次比较之后，辅助数组中的每一个分量A[i][j]中存放的值，是从vi出发，已考虑了途经图G中所有顶点，到达vj的最短路径根据上面分析，可得到用C语言描述的弗洛伊德(Floyd)算法如下: 算法算法7.9 每对顶点之间最短路径的弗洛伊德算法    void floyd(int cost[][N])    /* 对采用带权邻接矩阵存储的有向图，求每对顶点之间的最短路径 */    { int a[N][N],i,j,k;      for(i=0;i

检查一个有向图是否存在回环，可以采用拓扑排序方法进行7.6.1 顶点活动网顶点活动网(AOV网)        实际应用中，常用有向图来描述工程的进度、系统实施过程工程可以分为若干个称为活动(activity)的子工程，而且这些子工程之间通常有一定的先后关系以顶点为活动，以有向边表示先后关系的有向图，被称为AOV网在AOV网中，若从顶点vi到顶点vj有一条有向路径，则vi是vj的前驱；vj是vi的后续若是网中一条弧，则vi是vj的直接前驱；vj是vi的直接后续        在AOV网中，不应该有回环出现，因为存在回环意味着某项活动以自身的完成为先决条件显然，这是不合理的所以，对给定的AOV网，必须检测网中是否存在回环回环检测的方法是：对有向图构造其顶点拓扑有序序列，若网中所有顶点都在它的拓扑序列中，则AOV必定不存在回环 例如，一个计算机软件专业的学生必须学习一系列基本课程(如图7.12(a)所示) ，构成的AOV网中有如下两个拓扑序列：       C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8 和   C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8 课程编号  课程名称 先决条件   C1  程序设计    无   C2  离散数学    C1   C3  数据结构  C1 ,C2   C4  汇编语言    C1   C5  算法分析  C3 ,C4   C6 计算机体系结构    C11   C7  编译方法  C5 ,C3   C8  操作系统  C3 ,C6   C9  高等数学   C10  线性代数    C9   C11  普通物理    C9   C12  数值分析 C9 ,C10 ,C1图7.12  课程之间的优先关系以及表示该关系的AOV网 7.6.2 拓扑排序拓扑排序        对一个AOV网进行拓扑排序过程，就是在一个只有部分顶点之间有先后关系的AOV网中，构造一个任意顶点之间都有先后关系的线性序列。

即：对任意vi和vj，若它们属于该线性序列，则vi和vj之间必有先后关系，可能是vi是vj的(直接)前驱，也可能vj是vi的(直接)前驱例如，图7.12(b)中，C5和C3,C4,C7之间有先后关系，而得到的拓扑序列：  C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8表示C5和任意顶点之间的都有先后关系，C1,C2,C3,C4是C5的(直接)前驱，而C5是C7,C9,C10,C11,C6,C12,C8的(直接)前驱得到该序列的过程称为拓扑排序拓扑排序的方法如下：    (1)在AOV网中选择一个没有直接前驱的顶点，并将其输出    (2)从AOV网中删除该顶点和所有以它为尾的弧    (3)重复(1)和(2)，直至所有顶点都被输出，或者当前AOV网中不存在没有前驱的顶点为止前一种情况表示AOV网中无回环存在，而后一种情况则说明AOV网中存在回环图7.13  AOV网及其拓扑有序序列产生的过程     按上述方法对图7.13(a)中所示的AOV网进行拓扑排序，得到的拓扑序列为：               v5-v0-v3-v2-v1-v4 为了在计算机中实现上述操作，AOV网采用邻接表作为存储结构。

另外，在邻接表的头结点中增加一个存放顶点入度的数据域，入度为0的顶点即为没有前驱的顶点当删除一条边后，与该边相关联的弧头顶点的入度减1 图7.14  图7.13(a)的AOV网所对应的邻接表 图7.13(a)的AOV网所对应的邻接表如图7.14所示用一个栈存放AOV网中入度为0的顶点具体算法描述如下：  (1)将邻接表中所有入度为0的顶点编号进栈   (2)栈为空，转到(3)栈不为空，首先，栈顶元素vi出栈并输出；然后，在邻接表中查找以顶点vi为尾的弧，将顶点vk的入度减1，若顶点vk的入度为0，则顶点vk进栈重复(2)  (3)判断输出的顶点数，若不等于n，则AOV网中有回环存在   根据上面的描述，可得到用C语言描述的AOV网的数据结构和拓扑排序算法   struct node    { int degree; /* 在顶点中用于存放入度，在弧结点中用于存放入点编号 */       struct node *link;    }; typedef struct node NODE;    算法算法7.10 建立AOV网的邻接表算法    int create(NODE adjlist[]) /* 建立邻接表算法 */        { NODE *p;      int num,i,v1,v2;      scanf("%d\n",&num);  /* 读入结点数 */      for(i=0;ivertex=v2;         /* 插入在链表的首部 */         p->link=adjlist[v1].link; adjlist[v1].link=p;             adjlist[v2].degree++;     /* 统计每个顶点的入度 */      }   return(num);  /* 返回顶点数 */}算法算法7.11 对以邻接表存放的AOV网进行拓扑排序算法。

    void toposort(NODE adjlist[],int num)    /* AOV网有num个顶点，用邻接表adjlist[]存放 */    { int stack[MAX];     /* 存放入度为O的顶点的栈 */       int i,top,out, k;          int num1=0;          /* 统计拓扑序列中结点个数 */       NODE *p;       top=0;               /* 栈为空 */       for(i=0;i0)        { top--; out=stack[top];  /* out为出栈元素 */           printf("%d, ",out);  num1++;         /* 遍历out的邻接点链表，将其中所有弧头顶点的入度减1 */            p=adjlist[out].link;                                   （接下一页）while(p!=NULL)          { k=p->vertex;             adjlist[k].vertex--; /* vk为弧头，入度减1 */            if(adjlist[k].vertex==0)              { stack[top]=k; top++; } /* vk入度为0，入栈 */            p=p->link;          }       }     if(num1