第7章 图结构
} for(j=0;j (4) 主函数演示程序void main() 主函数首先建立一个无向网的邻接矩阵G，并显示输出该矩阵，然后通过克鲁斯卡尔算法得到以邻接表存储的最小生成树T，最后显示输出T中所有弧的相关信息。 void main() { MGraph G; ALGraph T; GKind gk=UDN; cout<<\建立一个无向网的邻接矩阵G:\\n\ CreateGraph_MG(G,gk); cout<<\无向网G的邻接矩阵为:\\n\ DisplyMG(G); //显示G的邻接矩阵 MiniTree_Kruskal(T,G); cout<<\无向网G的最小生成树的邻接表为:\\n\ DisplyAL(T); //显示T的邻接表 }程序运行演示结果为： 建立一个无向网的邻接矩阵G: 输入顶点数vexnum和弧数arcnum:7 12↙ 按某种顺序输入7个顶点的值: 1 2 3 4 5 6 7↙ 输入图中12条边(弧)和权的信息u v w: 1 2 2 2 5 10 5 7 6 7 6 1 6 3 5 3 1 4 4 1 1 4 2 3 4 5 7 4 7 4 4 6 8 4 3 2↙ 无向网G的邻接矩阵为: 0 2 4 1 0 0 0 2 0 0 3 10 0 0 4 0 0 2 0 5 0 1 3 2 0 7 8 4 0 10 0 7 0 0 6 0 0 5 8 0 0 1 0 0 0 4 6 1 0 无向网G的最小生成树的邻接表为: 0 (1): [1,2] [3,1] 1 (2): [0,2] 2 (3): [3,2] 3 (4): [6,4] [2,2] [0,1] 4 (5): [6,6] 5 (6): [6,1] 6 (7): [4,6] [3,4] [5,1] 说明： （1）程序运行中所建立的是图7.21(a)所示的无向网G的邻接矩阵，其输出结果是图7.21(b)所示的最小生成树T的邻接表。在T的显示列表中，第1列为结点下标，第2列为结点值，以后的每一项为[邻接点,权值]。 （2）克鲁斯卡尔算法的时间复杂度为O(e*loge)，其中e为无向连通网G的边数。因此，相对于普里姆算法而言，它更适合于求稀疏网的最小生成树问题。 7.5最短路径 在有向网中求解最短路径(shortest path)是一个很有实际应用价值的问题。例如，交通网络可以看成是带权值的图，图中的顶点表示城市，边表示城市之间的交通线，边上的权值表示交通线的长度或花费代价。对这样的交通网络，常常会关心如下问题： （1）从A城市到B城市是否有公路可通？ -.202.- 第7章 图结构 （2）从A城市到B城市有若干条公路可通的情况下，哪一条公路的路程最短或所花费的代价最低？ 以上问题即为求最短路径问题，此时路径长度是路径上的边所带的权值的总和。路径的开始顶点称为源点，最后一个顶点称为终点。 本节我们将分别介绍求最短路径的两个算法，即求某个源点到其它各个顶点的最短路径的迪杰斯特拉(Dijkstra)算法和求网中每一对顶点之间的最短路径的弗洛伊德(Floyd)算法。 7.5.1从源点到其它各顶点的最短路径 从某个源点到其它各个顶点的最短路径又称为单源最短路径。单源最短路径的问题是：给定一个有向网G=(V,VR)和V中的一个顶点v0，分别求出v0到G中其它每个顶点的最短路径长度，即路径上所有权值的和的最小值。 例如，给定有向网G如图7.26(a)所示。其源点为v1，从v1到其它各个顶点的最短路径长度如图7.26(b)所示。 1．迪杰斯特拉(Dijkstra)算法思想 迪杰斯特拉(Dijkstra)提出了一个按路径长度递增的次序产生最短路径的算法，又称为“贪心”算法。该算法的基本思想是： 把图G=(V,VR)中的所有顶点分成两组，令S表示已求出最短路径的顶点的集合，其初始状态仅包含源点，而其余顶点的集合为V-S。按路径长度递增的次序逐个把V-S中的顶点加入到S中，直到从源点出发可以到达的所有顶点都在S中为止。在求最短路径的过程中，始终保持从源点到S中各顶点的最短路径长度，都不大于从源点到V-S中任何顶点的最短路径长度。另外，每个顶点对应一个距离值，S中的顶点对应的距离值是从源点到该点的最短路径长度，V-S中的顶点对应的距离值是从源点到此顶点的，只包含S中顶点为中间顶点的最短路径长度。 为实现该算法，引入数组dist[]，它的每个分量dist[i]有5个域： (1) 表示路径是否结束的域(final)； (2) 表示当前路径长度的域(min)； (3) 表示网中的结点个数的域(vex)； (4) 存储路径上各个顶点的栈(path)； (5) 栈顶指针域(top)。 假设源点为vj，则dist[i].path的初值为{j,i}，dist[j].final=1，dist[i].final=0(i!=j)、dist[i].min的初值为： -.203.- 第7章 图结构 ?权值vj与vi关联 dist[i].min??0v与v不关联ji?迪杰斯特拉(Dijkstra)算法的执行过程是，每次从V-S中选取一个min最小的顶点vk加入 到S中（令dist[k].final=1），并对V-S中各个顶点的距离值dist[i].min进行修改。 dist[i].min的修改过程是：若G.arcs[k][i]存在，并且顶点vk加入到以vi为当前终端顶点的路径中，使得不等式dist[k].min+cost[k][i] 反复执行以上操作，直到再也没有可加入到S中的点为止。 例如，图7.26(a)的邻接矩阵为： 假设以v1为源点，则在求最短路径过程中，dist[i].min以及dist[i].path的变化过程如图7.27所示。 终点 v2 v3 v4 v5 v6 v7 vk S={v1} 2, 由图7.27的第1列可以看出，一开始顶点集S中只有源点即S={v1}，第2列是源点v1到各个顶点的最短路径长度以及路径上的顶点；在第2列中选中“1, 2．迪杰斯特拉(Dijkstra)算法 (1) 定义辅助数组dist[]的结构类型 struct Dist -.204.- 第7章 图结构 { }; int final; //路径是否结束 int min; //当前路径长度 int vex; //网中的结点个数 int top; //存储路径的栈顶指针 int *path; //存储路径的栈 (2) 初始化辅助数组dist[] 函数void InitDist(Dist* &dist,MGraph G,int v)的功能是，通过有向图G的邻接矩阵以及源点v来初始化辅助数组dist[]。 void InitDist(Dist* &dist,MGraph G,int v) { int i; dist=new Dist[G.vexnum]; for(i=0;i 函数int MinDist(Dist *dist)返回路径数组dist[]中的当前最短路径程度。 int MinDist(Dist *dist) { int i=0,j,k,min; while(dist[i].final||!dist[i].mi+n)i++; //查找V-S中第一个最短路径下标i min=dist[i].min; j=i; for(k=i+1;k (4) 迪杰斯特拉算法实现 函数void ShortestPath_DIJ(Dist* &dist,MGraph G,int v)通过迪杰斯特拉算法求出邻接矩阵表示的有向网G从源点v出发到各点的最短路径长度dist[]。 -.205.- 第7章 图结构 void ShortestPath_DIJ(Dist* &dist,MGraph G,int v) { int i,j,k,t,n=G.vexnum; InitDist(dist,G,v); for(k=1;k (5) 最短路径的显示输出 函数void Disply_Dist(Dist* dist)显示输出dist[]中到每一点的最短路径长度和顶点序列。 void Disply_Dist(Dist* dist) { int i,t,n=dist[0].vex; for(i=0;i (6) 求最短路径的主函数 在主函数中，首先创建一个有向网G并显示输出G的邻接矩阵，再输入源点v的下标，求得G中从v出发到每个顶点的最短路径，并输出结果。 void main() { Dist *dist; MGraph G; GKind gk=DN; -.206.-