第8章 图 8.1 图的基本概念和基本操作 8.2 图的邻接矩阵存储结构 8.3 图的邻接表存储结构 8.4 图的其他存储结构 第8章 图 8.1 图的基本概念和基本操作 8.2 图的邻接矩阵存储结构 8.3 图的邻接表存储结构 8.4 图的其他存储结构 8.5 最小生成树 8.6 最短路径

8.1 图的基本概念和基本操作 8.1.1 图的基本概念 图（Graph）是由顶点集合及顶点间的关系集合组成的一种数据结构。 图G的定义是： 8.1 图的基本概念和基本操作 8.1.1 图的基本概念 图（Graph）是由顶点集合及顶点间的关系集合组成的一种数据结构。 图G的定义是： G =（V， E） 式中： V = {x|x∈某个数据对象} E ={（x， y）|x， y∈V} 或 E = {〈x，y〉|x， y∈V并且Path（x，y）}

图8―1 带自身环的图和多重图 （a） 带自身环的图； （b） 多重图

这样， 在图G中， V是顶点的有穷非空集合， E是顶点之间关系的有穷集合， E也叫做边的集合。 图有许多复杂结构， 本教材只讨论最基本的图， 因此， 本书讨论的图中不包括图8―1所示两种形式的图。 图8―1（a）　中有从顶点A到自身的边存在， 称为带自身环的图; 图8―1（b）中从顶点B到顶点D有两条无向边， 称为多重图。

下面我们给出图的基本概念： （1） 有向图和无向图： 在有向图中， 顶点对〈x, y〉是有序的， 顶点对〈x, y〉称为从顶点x到顶点y的一条有向边， 因此， 〈x, y〉与〈y, x〉是两条不同的边。 有向图中的顶点对〈x, y〉用一对尖括号括起来， x是有向边的始点， y是有向边的终点，有向图中的边也称作弧。 在无向图中， 顶点对（x, y）是无序的， 顶点对（x, y）称为与顶点x和顶点y相关联的一条边， 这条边没有特定的方向， （x, y）与（y, x）是同一条边。  

图8―２给出了四个图例。 其中， 图G1和G2是无向图。 G1的顶点集合为V（G1）= {0,1, 2, 3}， 边集合为E（G1）= {(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)}； 图G3和G4是有向图， G3的顶点集合为V（G3）={ 0, 1, 2 }， 边集合为E（G3）= {〈0, 1〉, 〈1, 0〉, 〈1, 2〉}。 对于有向边， 边的方向用箭头画出， 箭头从有向边的始点指向有向边的终点。  

图8―２四个图例 （a） G1； （b） G2； （c） G3； （d） G4

(2) 完全图：在有n个结点的无向图中， 若有n(n-1)/2条边， 则称此图为无向完全图。 图8―２的G1就是无向完全图。 在有n个结点的有向图中， 若有n(n-1)条边， 则称此图为有向完全图。 图8―２的G4就是有向完全图。 完全图中的顶点个数和边的个数都达到最大值。

(3) 邻接顶点：在无向图G1， G2中， 若（u, v）是E(G)中的一条边， 则称u和v互为邻接顶点， 并称边（u, v）依附于顶点u和v。 在图8―２的无向图G1中， 顶点0的邻接顶点有顶点1, 2和3； 在有向图G3， G4中， 若〈u, v〉是E(G)中的一条边， 则称顶点u邻接到顶点v， 顶点v邻接自顶点u， 并称边〈u, v〉与顶点u和顶点v相关联。 在图8―２的有向图G3中， 顶点1因边〈1, 2〉邻接到顶点2。

(4) 顶点的度： 顶点v的度是与它相关联的边的条数， 记作TD(v)。 在有向图中， 顶点的度等于该顶点的入度和出度之和， 即TD(v)=ID(v)+OD(v)。 顶点v的入度ID(v)是以v为终点的有向边的条数； 顶点v的出度OD(v)是以v为始点的有向边的条数。在图8―２的有向图G3中， 顶点1的入度ID(1)=1， 顶点1的出度OD(1)=2， 所以， 顶点1的度 TD(v)= ID(v)+OD(v)=1+2=3。 可以证明， 在一个有n个顶点、 e条有向边（或无向边）的图中， 恒有下列关系式：

(5) 路径： 在图G=(V, E)中， 若从顶点vi出发有一组边使可到达顶点vj， 则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径。 在图8―２的图G2中， 从顶点0到顶点3的路径为0, 1, 3。 (6) 权： 有些图的边附带有数据信息， 这些附带的数据信息称为权。 权可以表示实际问题中从一个顶点到另一个顶点的距离、 花费的代价、 所需的时间， 等等。 带权的图称作网络。图8―3就是带权图。 其中， 图8―3（a）是一个工程的施工进度图， 图8-3（b）是一个交通网络图。

图8―3 带权图 （a） 施工进度图； （b） 交通网络图

（7） 路径长度： 对于不带权的图， 一条路径的路径长度是指该路径上的边的条数； 对于带权的图， 一条路径的路径长度是指该路径上各个边权值的总和。 在图8―２的无向图G2中， 路径0, 1, 3的路径长度为2； 在图8―3（a）的有向图中， 路径1, 3, 6, 7的路径长度为16， 路径1, 4, 7的路径长度为31。 (8) 子图：设有图G1={V1, E1}和图G2={V2, E2}， 若V2V1且E2E1， 则称图G2是图G1的子图。

(9) 连通图和连通分量： 在无向图中， 若从顶点vi到顶点vj有路径， 则称顶点vi和顶点vj是连通的。 如果图中任意一对顶点都是连通的， 则称该图是连通图。 非连通图的极大连通子图称作连通分量。 图8―2的无向图G1和G2都是连通图。 (10) 强连通图和强连通分量： 在有向图中， 若对于每一对顶点vi和vj都存在一条从vi到vj和从vj到vi的路径， 则称该图是强连通图。 非强连通图的极大强连通子图称作强连通分量。 图8―2的有向图G4是强连通图。 图8―2的有向图G3不是强连通图， 但G3有一个强连通分量包括顶点0和顶点1， 边〈0, 1〉和边〈1, 0〉。

(11) 生成树： 一个连通图的极小连通子图称作该图的生成树。 有n个顶点的连通图的生成树有n个顶点和n-1条边。 (12) 简单路径和回路： 若路径上各顶点v1, v2, …, vm, 均互不重复， 则称这样的路径为简单路径； 若路径上第一个顶点v1与最后一个顶点vm重合， 则称这样的路径为回路或环。

8.1.2 图的基本操作 讨论各种类型的图都要用到的图的基本操作。 (1) 在图中增加一个顶点； （2） 如果顶点v1和v2是图中的两个顶点， 则在图中插入边(v1, v2)； （3）如果顶点v是图中的顶点， 则删除图中顶点v和与顶点v相关联的所有边； （4）如果边(v1, v2)是图中的一条边， 则删除边(v1, v2)； （5）如果顶点v是图中的顶点， 则取顶点v的第一个邻接顶点；

（6） 如顶点v和顶点w是图中的两个顶点且它们互为邻接顶点， 则取得顶点v的w邻接顶点的下一个邻接顶点。 （7） 按某种规则遍历图。 和树的遍历类同， 图的遍历也是访问图中的每一个顶点且每个顶点只被访问一次。

8.2 图的邻接矩阵存储结构   8.2.1 邻接矩阵 我们首先定义邻接矩阵。 假设图G=(V, E)有n个顶点， 即V={v0, v1, …, vn-1}， E可用如下形式的矩阵A描述， 对于A中的每一个元素aij， 满足： 若(i, j)∈E或〈i, j〉∈E 否则

由于矩阵A中的元素aij表示了顶点i和顶点j之间边的关系， 或者说， A中的元素aij表示了顶点i和其他顶点j（0≤j≤n-1）的邻接关系， 所以矩阵A称作邻接矩阵。 在图的邻接矩阵存储结构中， 顶点信息使用一维数组存储， 边信息的邻接矩阵使用二维数组存储。 图8―4（a）是一个无向图， 图8―4（b）是对应的邻接矩阵存储结构。 其中， V表示了图的顶点集合， A表示了图的邻接矩阵。 无向图的邻接矩阵一定是对称矩阵。 从无向图的定义和无向图的邻接矩阵定义可知， 邻接矩阵中第i行（或第i列）中非零元素的个数等于第i个顶点的度数。 又由于邻接矩阵中非零元的数值为1， 所以有

图8―4无向图及其邻接矩阵 （a） 无向图； （b） 邻接矩阵

图8―5（a）是一个有向图， 图8―5（b）是对应的邻接矩阵存储结构， 其中， V表示图的顶点集合， A表示图的邻接矩阵。 有向图的邻接矩阵一般是非对称矩阵。从有向图的定义和有向图的邻接矩阵定义可知， 有向图的邻接矩阵中第i行中非零元素的个数等于第i个顶点的出度， 有向图的邻接矩阵中第i列中非零元素的个数等于第i个顶点的入度， 又由于邻接矩阵中非零元素的数值为1， 所以有：

图8―5 有向图及其邻接矩阵 （a） 有向图； （b） 邻接矩阵

对于网（或称带权图）， 邻接矩阵A的定义为：   i≠j且(i,j)∈E或〈i,j〉∈E 否则但i≠j 否则但i=j 其中， wij>0， wij是边(i, j)或弧，〈i, j〉的权值， 权值wij表示了从顶点i到顶点j的代价或称费用。 当i=j时， 邻接矩阵中的元素aij=0可理解为从一个顶点到自己顶点没有代价， 这也完全和实际应用中的问题模型相符。 有种特殊的网允许wij为负值， 本书讨论的网不包括此种网。

图8―6（a）是一个带权图， 图8―6（b）是对应的邻接矩阵存储结构。 其中， V表示图的顶点集合， A表示图的邻接矩阵。 对于带权图， 邻接矩阵第i行中所有0<aij<∞的元素个数等于第i个顶点的出度， 邻接矩阵第j列中所有0<aij<∞的元素个数等于第j个顶点的出度。

图8―6 带权图及其邻接矩阵 （a） 带权图； （b） 邻接矩阵

8.2.2 邻接矩阵表示的图类 对于上述的无向图、 有向图和带权图三种类型的图， 其图类实现方法基本类同， 如有向图中的弧〈a,b〉和弧〈b,a〉就等同于无向图中的边(a,b)， 把不带权图中的边信息均定为1， 不带权图就变成了带权图。 因此， 在上述三种类型的图中， 带权图最有代表性。 下面我们就以带权图为例讨论邻接矩阵表示的图类。

1. 图类的定义 在邻接矩阵表示的图中， 顶点信息用一个一维数组表示， 边（或称弧）信息用一个二维数组表示。 在这里， 顶点信息我们用第3章讨论的线性表表示， 因此我们可以利用线性表实现的功能和提供的共有成员函数方便地完成顶点的插入、 删除等操作。 我们在第3章设计的线性表类是使用抽象数据类型Datatype来定义要操作的数据对象的， 因此这里要在主函数使用图类之前定义抽象数据类型Datatype为图的顶点信息数据类型， 我们的测试例子中定义图的顶点信息数据类型(Vert)为char类型。

大多数情况下带权图的边信息只包含边的权值， 作为教科书， 我们主要注重基本原理和方法的讨论， 因此我们这里设计的图类的边信息只包含边的权。 注意， 由于我们利用线性表来保存顶点信息， 所以关于顶点信息的当前个数、 是否表已满无法再继续插入等均由线性表来维护， 这里无需再考虑， 这也正是面向对象程序设计最主要的优点之一。

＃include "SeqList.h" ＃include "SeqQueue.h" const int MaxVertices = 10; const int MaxWeight = 10000; class AdjMWGraph { private: SeqList Vertices; //顶点信息的线性表

int Edge［MaxVertices］［MaxVertices］; //边的权信息的矩阵 int numOfEdges; //当前的边数 public: AdjMWGraph(const int sz = MaxVertices); //构造函数   int GraphEmpty( )const //图空否 {return Vertices.ListEmpty( );} int NumOfVertices(void) //取当前顶点个数 {return Vertices.ListSize( );}

int Num Of Edges(void) //取当前边个数 {return numOfEdges;} VerT Get Value(const int i); //取顶点i的值 int Get Weight(const int v1,const int v2); //取弧〈v1,v2〉的权 //插入顶点vertex void InsertVertex(const VerT &vertex); //插入弧〈v1,v2〉， 权为weight void InsertEdge(const int v1,const int v2,int weight); //删除顶点i和与顶点i相关的所有边 void Delete Vertex(const int i);

//删除弧〈v1,v2〉 void DeleteEdge(const int v1,const int v2); //取顶点v的第一条邻接边， 取到返回该邻接边的邻接顶点下标； 否则返回-1 int GetFirstNeighbor(const int v); //取顶点v1的<v1,v2>邻接边的下一条邻接边， //若下一条邻接边存在， 则返回该邻接边的邻接顶点下标； 否则返回-1 int GetNextNeighbor(const int v1,const int v2);  //对连通图从顶点v开始用visit( )深度优先搜索访问， visited为访问 标记 void DepthFirstSearch(const int v,int visited［］,

void visit(VerT item)); //对连通图从顶点v开始用visit( )广度优先搜索访问， visited为访问标记 void BroadFirstSearch(const int v,int visited［］,  //对非连通图用visit( )进行深度优先搜索访问 void DepthFirstSearch(void visit(VerT item)); //对非连通图用visit( )进行广度优先搜索访问 void BroadFirstSearch(void visit(VerT item)); };

2. 成员函数的实现 AdjMWGraph::AdjMWGraph(const int sz) //构造函数  { for(int i = 0; i < sz; i++) for(int j = 0; j < sz; j++) { if(i == j) Edge［i］［j］ = 0; else Edge［i］［j］ = MaxWeight; // MaxWeight表示无穷大 } numOfEdges = 0; //当前边个数初始为0

VerT AdjMWGraph::GetValue(const int i) //取顶点i的值 { if(i < 0 || i > Vertices.ListSize()) cerr << "参数i越界出错!" << endl; exit(1); } //使用线性表的GetData(i)成员函数返回顶点i的值 return Vertices.GetData(i);

}  int AdjMWGraph::GetWeight(const int v1,const int v2) //取弧〈v1,v2〉的权 { if(v1 < 0 || v1 > Vertices.ListSize() || v2 < 0 || v2 > Vertices.ListSiz e()) cerr << "参数v1或v2越界出错!" << endl; exit(1);

return Edge［v1］［v2］; //返回弧〈v1,v2〉的权 } void AdjMWGraph::InsertVertex(const VerT &vertex) //插入顶点vertex { //在顶点线性表Vertices的当前表尾ListSize()插入顶点vertex Vertices.Insert(vertex,Vertices.ListSize());

void AdjMWGraph::InsertEdge(const int v1,const int v2,int weight) //插入弧〈v1,v2〉， 权为weight { if(v1 < 0 || v1 > Vertices.ListSize() || v2 < 0 || v2 > Vertices.ListSiz e()) cerr << "参数v1或v2越界出错!" << endl; exit(1); } Edge［v1］［v2］ = weight; //插入权为weight的边

numOfEdges++; //边个数加1 } void AdjMWGraph::DeleteVertex(const int v) //删除顶点v和与顶点v 相关的所有边 { //删除与顶点v相关的所有边 for(int i = 0; i < Vertices.ListSize(); i++) for(int j = 0; j < Vertices.ListSize(); j++)

if((i == v || j == v) && Edge［i］［j］ > 0 && Edge［i ］［j］ < MaxWeight) { Edge［i］［j］ = MaxWeight; numOfEdges--; }   Vertices.Delete(v); //删除顶点v

void AdjMWGraph::DeleteEdge(const int v1,const int v2) //删除弧，〈v1,v2〉 { if(v1 < 0 || v1 > Vertices.ListSize() || v2 < 0 || v2 > Vertices.ListSize() || v1 == v2) cerr << "参数v1或v2出错!" << endl; exit(1); }

Edge［v1］［v2］ = Max Weight; //把该边的权值置为无穷 Num Of Edges--; //边个数减1 }

8.2.3 邻接矩阵图类的深度优先搜索遍历 和树的遍历操作类同， 图的遍历操作也是图问题中最基本和最重要的操作。 图的遍历操作的定义是访问图中的每一个顶点且每个顶点只被访问一次。 图的遍历操作方法有两种：一种是深度优先搜索遍历， 另一种是广度优先搜索遍历。 图的深度优先搜索遍历类同于树的先根遍历， 图的广度优先搜索遍历类同于树的层序遍历。  

图的遍历算法设计需要考虑三个问题： （1） 图的特点是没有首尾之分， 所以算法的参数要指定访问的第一个顶点； （2） 对图的遍历路径有可能构成一个回路， 从而造成死循环， 所以算法设计要考虑遍历路径可能的回路问题； （3） 一个顶点可能和若干个顶点都是相邻顶点， 要使一个顶点的所有相邻顶点按照某种次序被访问。

我们首先考虑第（3）个问题的解决方法。 为解决图的遍历操作的这个问题， 我们在图的成员函数中设计了GetFirstNeighbor(v)成员函数和GetNextNeighbor(v1,v2)成员函数。 GetFirstNeighbor(v)找顶点v的第一条邻接边， 若存在， 则返回该邻接边的邻接顶点下标； 否则返回-1。 GetNextNeighbor(v1,v2)找顶点v1的〈v1,v2〉邻接边的下一条邻接边， 若下一条邻接边存在， 则返回该邻接边的邻接顶点下标； 否则返回-1。

有了这两个成员函数， 我们就可以从顶点v1首先找到第一条邻接边〈v1,v2〉， 再从顶点v1的〈v1,v2〉邻接边找顶点v1的〈v1,v2〉邻接边后的下一条邻接边， 从而可以找到顶点v1的所有邻接边。 这两个成员函数的算法设计如下： int AdjMWGraph::GetFirstNeighbor(const int v) //找顶点v的第一条邻接边， 若存在则返回该邻接边的邻接顶点下标； 否则返回-1 { if(v < 0 || v > Vertices.ListSize( ))

cerr << "参数v1越界出错!" << endl; exit(1); } for(int col = 0; col <= Vertices.ListSize(); col++) //若存在， 则返回该邻接边的邻接顶点下标 if(Edge［v］［col］ > 0 && Edge［v］［col］ < MaxWeight) return col; return -1; //不存在， 则返回-1  int AdjMWGraph::GetNextNeighbor(const int v1,const int v2) //找顶点v1的〈v1,v2〉邻接边的下一条邻接边，  

//若下一条邻接边存在,则返回该邻接边的邻接顶点下标； 否则返回-1 { if(v1 < 0 || v1 > Vertices.ListSize() || v2 < 0 || v2 > Vertices.ListSize()) cerr << "参数v1或v2越界出错!" << endl; exit(1); }

// 使col = v2+1， 因此寻找的是顶点v1的〈v1,v2〉邻接边的下一条邻接边 for(int col = v2+1; col <= Vertices.ListSize(); col++) //若存在， 则返回该邻接边的邻接顶点下标 if(Edge［v1］［col］ > 0 && Edge［v1］［col］ < MaxWeight) return col;return -1; //不存在， 则返回-1 }

对于连通图， 从初始顶点出发一定存在路径和图中的所有其他顶点相连， 所以对于连通图从初始顶点出发一定可以遍历该图。 图的深度优先遍历算法是遍历时深度优先的算法， 即在图的所有邻接顶点中每次都在访问完当前顶点后首先访问当前顶点的第一个邻接顶点， 这样的算法是一个递归算法。 连通图的深度优先搜索遍历算法思想是： （1） 访问初始顶点v并标记顶点v为已访问； （2） 查找顶点v的第一个邻接顶点w；

（3） 若顶点v的邻接顶点w存在， 则继续执行， 否则算法结束； （4） 若顶点w尚未被访问,则访问顶点w并标记顶点w为已访问； （5） 查找顶点v的w邻接顶点后的下一个邻接顶点w， 转到步骤（3）。

void AdjMWGraph::DepthFirstSearch(const int v,int vis ited［］, void visit(VerT item)) { visit(GetValue(v)); //访问顶点v visited［v］ = 1; //标记顶点v已访问  int w = GetFirstNeighbor(v); //顶点w为顶点v的第一个邻接顶点

while(w != -1) //当邻接顶点存在时循环 { if(! visited［w］) DepthFirstSearch(w,visited,visit);/ /对顶点w递归 //顶点w为顶点v的w邻接顶点的下一个邻接顶点 w = GetNextNeighbor(v,w); }

上述递归算法属于第6章讨论过的回溯算法， 当寻找顶点v的邻接顶点成功时继续进行， 当寻找顶点v的邻接顶点失败时回溯到上一次递归调用的地方继续进行。 对于图8―7所示的无向连通图， 若顶点A为访问的首顶点， 则深度优先搜索遍历的顶点访问顺序是： A B D E C F G 。

图8―7 无向连通图及其邻接矩阵 （a） 无向连通图； （b） 邻接矩阵

8.2.4 邻接矩阵图类的广度优先搜索遍历 图的广度优先遍历算法是遍历时广度优先的算法。 它是一个分层搜索的过程， 和树的层序遍历算法类同， 它也需要一个队列以保持访问过的顶点的顺序， 以便按顺序访问这些顶点的邻接顶点。 连通图的广度优先搜索遍历算法思想是： （1） 访问初始顶点v并标记顶点v为已访问； （2） 顶点v入队列； （3） 当队列非空时则继续执行， 否则算法结束； （4） 出队列取得队头顶点u；

（5） 查找顶点u的第一个邻接顶点w； （6） 若顶点u的邻接顶点w存在， 则继续执行， 否则转到步骤（3）； （7） 若顶点w尚未被访问则访问顶点w并标记顶点w为已访问； (8)顶点w入队列； （9） 查找顶点u的w邻接顶点后的下一个邻接顶点w， 转到步骤（6）。

void AdjMWGraph::BroadFirstSearch(const int v,int visited［］ void visit(VerT item)) { VerT u,w; SeqQueue queue; //定义队列queue visit(GetValue(v)); visited［v］ = 1;  queue.QInsert(v); //顶点v入队列

while(!queue.QueueEmpty()) //当队列非空时循环 { u = queue.QDelete(); //出队列得到队头顶点u w = GetFirstNeighbor(u); while(w != -1) //若顶点u的邻接顶点w存在时循环 if(!visited［w］)

visit(GetValue(w)); visited［w］ = 1; queue.QInsert(w); //顶点w入队列 } w = GetNextNeighbor(u,w); //顶点u的w邻接顶点的下一个邻接顶点

8.2.5 非连通图和连通分量 对于连通图， 从图的任意一个顶点开始深度或广度优先遍历一定可以访问图中的所有顶点；但对于非连通图， 从图的任意一个顶点开始深度或广度优先遍历并不能访问图中的所有顶点。 对于非连通图， 从图的任意一个顶点开始深度或广度优先遍历只能访问包括该首顶点的连通分量中的所有顶点。

但当我们把每一个顶点都作为一次首顶点深度或广度优先遍历非连通图， 并根据顶点的访问标记来判断是否需要访问该顶点时， 就一定可以访问该非连通图中的所有顶点。 非连通图的深度优先搜索遍历算法如下： void AdjMWGraph::DepthFirstSearch(void visit(VerT item))={ //定义顶点访问标记数组 int *visited = new int［NumOfVertices()］;  //顶点访问标记数组初始化

for(int i = 0; i < NumOfVertices(); i++) visited［i］ = 0;  for(i = 0; i < NumOfVertices(); i++) //对所有顶点循环 //如该顶点尚未被访问则以该顶点为首顶点深度优先遍历访问 if(! visited［i］) DepthFirstSearch(i,visited,visit);  delete ［］visited; //删除顶点访问标记数组 }

非连通图的广度优先搜索遍历算法如下： void AdjMWGraph::BroadFirstSearch(void visit(VerT item)) { int *visited = new int［NumOfVertices( )］; for(int i = 0; i < NumOfVertices(); i++) visited［i］ = 0; for(i = 0; i < NumOfVertices(); i++) if(!visited［i］) BroadFirstSearch(i,visited,visit); delete ［］visited; }

非连通图的广度优先搜索遍历算法和非连通图的深度优先搜索遍历算法类同， 故不再作注释。 对于图8―7所示的无向连通图， 若删除弧〈0, 2〉和〈2, 0〉， 则该图变为图8-8所示的非连通图。 图8―8非连通图的深度优先搜索遍历顶点序列为： A B D E C F G 。 图8―8非连通图的广度优先搜索遍历顶点序列为： A B D E C F G 。

图8―8 非连通图

8.2.6 邻接矩阵图类的测试 我们以图8―7所示的无向连通图为例测试邻接矩阵图类。 我们首先给出建立邻接矩阵图类对象的外部函数。 为后面使用方便， 我们把下面的结构体定义和外部函数放在文件GraphLib.h中。 struct RowColWeight //定义结构体类型RowColWeight { int row; //行下标

int col; //列下标 int weight; //权值 }; voidCreatGraph(AdjMWGraph &G,Datatype V［］,int n,RowColWeight E［］,int e) //建立图G， 所建立的图G有n个顶点V［0］...V［n-1］， 有e条边E［0］...E［e-1］ { //向图G中插入n个顶点V［0］...V［n-1］ for(int i = 0; i < n; i++) G.InsertVertex(V［i］);  //向图G中插入e条边E［0］...E［e-1］

for(int k = 0; k < e; k++) G. InsertEdge(E［k］. row,E［k］. col,E［k］ for(int k = 0; k < e; k++) G.InsertEdge(E［k］.row,E［k］.col,E［k］.weight); } void Printchar(char item) //访问顶点的函数 { cout << item<<" ";

使用图8―7所示的无向连通图的测试程序如下： typedef char VerT; //顶点类型定义 typedef char Datatype; //邻接矩阵图类中所使用线性表类型定义 ＃include "AdjMWGraph.h" ＃include "GraphLib.h"  void main(void) { AdjMWGraph g;

char a［］ = {′A′, ′B′, ′C′, ′D′, ′E′, ′F′, ′G′}; RowColWeight rcw［］ = {{0, 1, 1}, {0, 2, 1}, {1, 3, 1}, {1, 4, 1}, {2, 5, 1}, {2, 6, 1}, {1, 0, 1}, {2, 0, 1}, {3, 1, 1}, {4, 1, 1}, {5, 2, 1}, {6, 2, 1}}; int n = 7,e = 12; CreatGraph(g,a,n,rcw,e);  cout << "当前的顶点个数为：" << g.NumOfVertices( ) << endl; cout << "当前的边的条数为：" << g.NumOfEdges( ) << endl;

cout << "深度优先搜索序列为："; int *visited = new int［g.NumOfVertices( )］; for(int i = 0; i < g.NumOfVertices( ); i++) visited［i］ = 0; g.DepthFirstSearch(0,visited,Printchar); cout << endl << "广度优先搜索序列为："; for(i = 0; i < g.NumOfVertices(); i++) visited［i］ = 0; g.BroadFirstSearch(0,visited,Printchar); delete ［］visited;

g.DeleteEdge(0,2); g.DeleteEdge(2,0); cout << endl << "当前的顶点个数为：" <<g.NumOfVertices( ); cout << endl << "当前的边的条数为：" << g.NumOfEdges( )<< endl; cout << "深度优先搜索序列为："; g.DepthFirstSearch(Printchar); cout << endl << "广度优先搜索序列为："; g.BroadFirstSearch(Printchar); }

程序的运行结果为： 当前的顶点个数为： 7； 当前的边的条数为： 12； 连通图的深度优先搜索序列为： A B D E C F G； 连通图的广度优先搜索序列为： A B C D E F G。 删除边〈0, 2〉和〈2, 0〉后非连通图有 当前的边的条数为： 10； 非连通图的深度优先搜索序列为： A B D E C F G； 非连通图的广度优先搜索序列为： A B D E C F G。

8.3 图的邻接表存储结构 8.3.1 图的邻接表存储结构 图的邻接矩阵存储结构的主要特点是把图的边信息存储在一个n×n矩阵中。 其中， n为图中的顶点个数。 当这个n×n阶矩阵是稠密矩阵时， 图的邻接矩阵存储结构是最常用也是最高效的存储结构。

图8―9是图8―5（a）所示有向图的邻接表存储结构。 严格地说， 该图的边信息存储矩阵不是一个稀疏矩阵， 因顶点个数太少， 但为使我们讨论问题和表示问题不致过于麻烦， 所以我们假设该图的边信息存储矩阵是一个稀疏矩阵。

图8―9 有向图的邻接表存储结构

图8―9中行数组的data域存储图的顶点信息， adj域为该顶点的邻接顶点单链表的头指针。 第i行单链表中的dest域存储边〈i,j〉的邻接顶点j， 对于任意一条边〈i,j〉， 因i值和存储该顶点的下标值一致， 所以不需要再另外存储。 如果是带权图再增加cost域， 第i行单链表中的dest域值为j的cost域中存储了边〈i,j〉的权值wij。 对比图8―9和第5章图5―4的行指针数组结构的三元组链表， 可以发现， 两者讲述的是同一种存储结构。

8.3.2邻接表存储结构的图类 ＃include "SeqQueue.h" const int MaxVertices = 100; struct Edge //边结构体定义 { int dest; //邻接顶点下标 DistT weight; //权 Edge *next; //指针

Edge( ){} //构造函数 Edge(int d,DistT w): dest(d),weight(w),next(NULL){} };   struct item //顶点数组的元素类型定义 { VerT data; //顶点数据

Edge *adj; //邻接表指针 }; class AdjTWGraph //邻接表图类定义 { private: item Vertices［MaxVertices］; //顶点数组 int numVertices; //顶点数组的当前元素个数

int numOfEdges; //当前边的条数 public: AdjTWGraph(void); ~AdjTWGraph(void);  int GraphEmpty( )const {return numVertices == 0;} int NumOfVertices(void) {return numVertices;} int NumOfEdges(void)

{return numOfEdges;} VerT GetValue(const int i); int GetWeight(const int v1,const int v2);   void InsertVertex(const VerT &vertex); void InsertEdge(const int v1,const int v2,int weight); void DeleteVertex(const int v); void DeleteEdge(const int v1,const int v2); int GetFirstNeighbor(const int v); int GetNextNeighbor(const int v1,const int v2);  

void DepthFirstSearch(const int v,int visited［］, void visit(VerT item)); void BroadFirstSearch(const int v,int visited［］, void DepthFirstSearch(void visit(VerT item)); void BroadFirstSearch(void visit(VerT item)); };

1.构造函数和析构函数 AdjTWGraph::AdjTWGraph(void) { for(int i = 0; i < MaxVertices; i++) Vertices［i］.adj = NULL; numVertices = 0; numOfEdges = 0; }  AdjTWGraph::~AdjTWGraph(void) //释放为存储边信息所动态建立的邻接链表的空间  

{ for(int i = 0; i < numVertices; i++) Edge *p = Vertices［i］.adj,*q; while(p != NULL) q = p->next; delete p; p = q; }

2.简单成员函数的实现 VerT AdjTWGraph::GetValue(const int i) { if(i < 0 || i > numVertices) cerr << "参数i越界出错!" << endl; exit(1); } return Vertices［i］.data;  int AdjTWGraph::GetWeight(const int v1,const int v2)

{ if(v1 < 0 || v1 > numVertices || v2 < 0 || v2 > numVertices) cerr << "参数v1或v2越界出错!" << endl; exit(1); } Edge *p = Vertices［v1］.adj; while(p != NULL && p->dest < v2) p = p->next; if(v2 != p->dest)

cerr << "边<v1,v2>不存在!" << endl; exit(1); } return p->weight;

3. 插入顶点和边以及删除顶点和边成员函数的实现 插入顶点成员函数很简单， 只需在存放顶点信息的数组中插入一个顶点信息。 void AdjTWGraph::InsertVertex(const VerT &vertex) { Vertices［numVertices］.data = vertex; numVertices++; }

插入边〈v1,v2〉的操作是要在数组下标的v1行中的邻接链表中插入一个包含dest, weight和next域的结点。 其中， dest域的值为v2， 邻接链表按dest域的值递增有序。 这是一个建立单链表的过程， 由于所建立的单链表无头指针， 所以算法中要分别考虑是否是单链表的第一次插入； 在不是单链表的第一次插入时,还要考虑在单链表的第一个结点前插入和在单链表的其他位置插入的情况。

void AdjTWGraph::InsertEdge(const int v1,const int v2,int w eight) { if(v1 < 0 || v1 > numVertices || v2 < 0 || v2 > numVertices) cerr << "参数v1或v2越界出错!" << endl; exit(1); }  Edge *q = new Edge(v2,weight);

if(Vertices［v1］.adj == NULL) //第一次插入 Vertices［v1］.adj = q; Else //非第一次插入 { Edge *curr = Vertices［v1］.adj,*pre = NULL; while(curr != NULL && curr->dest < v2) pre = curr; curr = curr->next; } if(pre == NULL) //在第一个结点前插入

{ q->next = Vertices［v1］.adj; Vertices［v1］.adj = q; } else //在其他位置插入 q->next = pre->next; pre->next = q; numOfEdges++;

插入边成员函数算法使用的是10.2.2节将要讨论的链表插入排序算法， 因此邻接表中的结点按边的弧尾顶点的大小有序排列。 插入排序算法的思想是：空链表时， 直接生成第一条边的弧尾顶点的dest域结点插入； 第二条边的弧尾顶点结点插入到链表中的位置由v2和第一条边结点的dest域比较确定(若v2小于第一条边结点的dest, 则把v2生成的结点插在第一条边的结点前； 否则， 把v2生成的结点插在第一条边的结点后)。 关于链表插入排序算法的更详细说明可参看10.2.2节。

插入边成员函数算法最坏情况下的时间复杂度为O(e)， 其中e为边的条数。 删除顶点v时要删除和顶点v关联的所有边， 这包括要删除顶点v的所有出边〈v,j〉和所有入边〈i,v〉。 在邻接表存储的图中删除顶点v的所有入边〈i,v〉的算法比较麻烦， 需要在所有顶点为i的单链表中寻找dest域为v的结点并删除。 由于所建立的单链没有头结点， 所以删除时还要分别考虑要删除结点是单链表的第一个结点和不是单链表的第一个结点的情况。 在邻接表存储的图中删除顶点v的所有出边〈v,j〉的算法是逐个删除顶点数组第v行单链表的所有结点， 并删除该顶点元素。

void AdjTWGraph::DeleteVertex(const int v) { Edge *pre,*curr; for(int i = 0; i < numVertices; i++) //在所有顶点为i的单链表中寻找dest域为v的结点并删除， 即删顶点v的入边 pre = NULL; curr = Vertices［i］.adj; while(curr != NULL && curr->dest < v)

pre = curr; curr = curr->next; } if(pre == NULL && curr->dest == v) //该出边结点是单链表的第一个结点时 { Vertices［i］.adj = curr->next; delete curr; numOfEdges--; else if(curr != NULL && curr->dest == v) //该出边结点是单链表的其他结点时

{ pre->next = curr->next; delete curr; numOfEdges--; } Edge *p = Vertices［v］.adj,*q; for(i = v; i < numVertices-1; i++) Vertices［i］ = Vertices［i+1］; //删除数组的顶点v元素 numVertices--;

while(p != NULL) //删除顶点v的所有出边 { q = p->next; delete p; //释放空间 p = q; numOfEdges--; }

从上述算法中可以看出， 在邻接表中， 为寻找邻接到顶点v的邻接顶点， 即寻找边〈i,v〉的顶点i， 必须遍历整个邻接表， 在每一个按弧尾顶点序号有序的单链表中寻找结点的dest域值等于v的结点。 因此其时间复杂度为O(ne)。 其中， n为顶点个数， e为边的条数。 删除边〈v1,v2〉的算法是在顶点数组的第v1行中删除结点的dest域为v2的结点。 由于所建立的单链没有头结点， 同样在删除时要分别考虑要删除结点是单链表的第一个结点和不是单链表的第一个结点的情况。

void AdjTWGraph::DeleteEdge(const int v1,const int v2) { if(v1 < 0 || v1 > numVertices || v2 < 0 || v2 > numVertices) cerr << "参数v1或v2越界出错!" << endl; exit(1); } Edge *curr = Vertices［v1］.adj,*pre = NULL; while(curr != NULL && curr->dest < v2)

pre = curr; curr = curr->next; } if(pre == NULL && curr->dest == v2) //要删结点是单链表的第一个结点 { Vertices［v1］.adj = curr->next; delete curr; numOfEdges--;

else if(pre != NULL && curr->dest == v2) //不是单链表的第一个结点 { pre->next = curr->next; delete curr; numOfEdges--; } else //参数出错， 该边不存在

{ cerr << "边<v1,v2>不存在!" << endl; exit(1); }

4. 遍历成员函数要调用的成员函数 int AdjTWGraph::GetFirstNeighbor(const int v) { if(v < 0 || v > numVertices) cerr << "参数v1越界出错!" << endl; exit(1); } Edge *p = Vertices［v］.adj; if(p != NULL) return p->dest; else return -1;

int AdjTWGraph::GetNextNeighbor(const int v1,const int v2) { if(v1 < 0 || v1 > numVertices || v2 < 0 || v2 > numVertices) cerr << "参数v1或v2越界出错!" << endl; exit(1); } Edge *p = Vertices［v1］.adj; while(p != NULL)

if(p->next != NULL && p->dest == v2) return p->next->dest; else p = p->next; } return -1;

5. 遍历成员函数 由于遍历图的深度优先遍历算法和图的广度优先遍历算法是固定不变的算法， 而这两个算法的成员函数实现都是通过调用Get First Neighbor(v)和Get Next Neighbor(v1,v2)实现的， 所以邻接表实现的图类的遍历成员函数和邻接矩阵实现的图类的遍历成员函数的实现过程完全一样。 我们在这里只列出一个连通图的深度优先搜索遍历成员函数Depth First Search(visit)， 其余的不再列出。

void AdjTWGraph::DepthFirstSearch(const int v,int visited［］ void visit(VerT item)) { visit(GetValue(v)); visited［v］ = 1; int w = GetFirstNeighbor(v); while(w != -1)

{ if(! visited［w］) Depth First Search(w,visited,visit); w = Get Next Neighbor(v,w); }

8.3.3 邻接表存储结构图类的测试 邻接表存储结构图类的测试程序和8.2.6节的邻接矩阵存储结构图类的测试程序基本相同。 不相同的部分主要是类型定义符和包含的头文件不同， 即测试文件的开头部分不同。 不相同部分如下： typedef char VerT; typedef int DistT; typedef char Datatype; ＃include "AdjTWGraph.h"

另一个不相同之处是主函数中的图类对象的定义语句不同， 这里的图类对象的定义语句为 ：AdjTWGraph g; 。 在主函数调用的创建图的函数CreatGraph(G,V,n,E,e)中，除图G的类型定义不同外， 其他部分也完全相同， 图G的类型定义为AdjTWGraph &G。 该测试程序的测试结果和8.2.6节的测试结果完全相同。 为节省篇幅， 所有相同部分就不再列出。

8.4 图的其他存储结构 8.4.1 逆邻接表 从上述图的邻接表存储结构类的成员函数实现算法中可以看出，在邻接表中，为求顶点v的入度，即为求边〈i,v〉中的顶点i， 必须遍历整个邻接表， 在每一个单链表中寻找结点dest域值等于v的结点，其时间复杂度为O(ne)。其中，n为顶点个数，e为边的条数。

为了便于确定顶点v的入度或以v为头的弧，可以建立图的逆邻接表，即对图中每个顶点v建立一个和邻接表结构类同的单链表，只是这个单链表的dest域改名为source域。source域中存放的是邻接到顶点v的邻接顶点下标，逆邻接表也因此而得名。图8―5（a）的有向图的逆邻接表存储结构如图8―10所示。

图8―10 逆邻接表

在逆邻接表中求顶点v入度最坏情况下的时间复杂度为O(e)。其中，e为边的条数。但是，由于每条边既在邻接表中存储，又在逆邻接表中存储，所以此时插入边和删除边的成员函数要同时对邻接表和逆邻接表进行维护。

8.4.2 十字链表 在图的邻接表和逆邻接表存储结构中，每条边的信息都既要存储在邻接表中，又要存储在逆邻接表中，这增加了插入边和删除边成员函数的算法复杂性。十字链表存储结构是解决这个问题的一个方法。十字链表存储结构既可以方便地表示邻接表和逆邻接表，又使每条边只存储了一个结点。

十字链表中每个结点的结构定义为： headVer tailVer wieght tailNext heatNext 其中：headVer为弧头下标域；tailVer为弧尾下标域；headNext为以顶点tailVer为弧尾的下一个弧头结点指针域，即headNext为顶点tailVer的入边链指针域；tailNext为以顶点headVer为弧头的下一个弧尾结点指针域，即tailNext为顶点headVer的出边链指针域；weight为边〈headVer,tailVer〉的权值域。 十字链表中顶点数组元素结构定义为： data firstIn firstOut

其中：data为顶点信息域，firstIn为该顶点的入边指针域，firstOut为该顶点的出边指针域。 图8―11给出了一个带权有向图和对应的十字链表存储结构。图中链表的结点各个域的排列次序和上边给出的结点结构定义次序相同。可以看出，该图共有7条边，对应的十字链表存储结构也只有7个结点。

图8―11 带权有向图及其十字链表存储结 构（a）带权有向图；（b）十字链表存储结构

在邻接多重表中，存储一条无向边(v1,v2)的结点只有一个。结点的结构为： 8.4.3 邻接多重表 在无向图的邻接表存储结构中，一条无向边(v1,v2)被存储在顶点v1的邻接单链表和顶点v2的邻接单链表中。此外，若要删除一条无向边(v1,v2)，又需两次扫描邻接表，寻找无向边(v1,v2)的两个结点并删除。对于无向图的邻接表存储结构，我们可以改进存储结构为邻接多重表存储结构。 在邻接多重表中，存储一条无向边(v1,v2)的结点只有一个。结点的结构为： mark headVer tailVer weight headNext tailNext

其中：mark为标志域，用来标记该边是否被访问过，结点结构中也可无此域；headVer为弧头下标域；tailVer为弧尾下标域；weight为边（headVer,tailVer）的权值域；headNext为以顶点tailVer为弧尾的下一个弧头结点指针域，即headNext为顶点tailVer的入边链指针域；tailNext为以顶点headVer为弧头的下一个弧尾结点指针域，即tailNext为顶点headVer的出边链指针域。要指出的是，由于一条无向边在多重表存储结构中只有一个结点，

所以从顶点tailVer到顶点headVer的边结点也就是从顶点headVer到顶点tailVer的边结点。 顶点数组元素的结构和邻接表的相同，即一个data域和一个指向该顶点链表的指针first域。图8―12是一个无向图及其邻接多重表存储结构。可以看出，在邻接多重表存储结构中，每条无向边只存储了一个结点。

图8―12 无向图及其邻接多重表存储结构 （a）无向图；（b）邻接多重表存储结构

8.5 最小生成树 8.5.1 最小生成树的基本概念 一个有n个顶点的连通图的生成树是原图的极小连通子图，它包含原图中的所有n个顶点，并且有保持图连通的最少的边。由生成树的定义可知: （1）若在生成树中删除一条边，就会使该生成树因变成非连通图而不再满足生成树的定义；

（2）若在生成树中增加一条边,就会使该生成树中因存在回路而不再满足生成树的定义； （3）一个连通图的生成树可能有许多。 使用不同的遍历图的方法可以得到不同的生成树。如对无向图使用深度优先搜索遍历方法与使用广度优先搜索遍历方法将会得到两个结构不同的生成树；从不同的顶点出发，也可以得到不同的生成树。图8-13给出了一个无向图和它的两棵不同的生成树。

图8―13 无向图和它的不同的生成树 （a）无向图；（b）生成树1；（c）生成树2

从最小生成树的定义可知，构造有n个顶点的无向连通网的最小生成树必须满足以下三条： （3）构造的最小生成树中不存在回路。 构造的最小生成树的方法有许多种，典型的构造方法有两种:一种称作普里姆（Prim）算法，另一种称作克鲁斯卡尔（Kruskal）算法。

8.5.2 普里姆算法 假设G=(V,E)是一个网络，其中V为网中顶点的集合，E为网中带权边的集合。设置两个新的集合U和T，其中U用于存放网G的最小生成树的顶点的集合，T用于存放网G的最小生成树的带权边的集合。令集合U的初值为U={u0}（即假设构造最小生成树时均从顶点u0开始），集合T的初值为T={}。普里姆算法的思想是：从所有顶点u∈U和顶点v∈V-U的带权边中选出具有最小权值的边(u,v)，将顶点v加入集合U中，将边(u,v)加入集合T中。

如此不断重复，直到U=V时即构造完毕。此时集合U中存放着最小生成树的顶点的集合，集合T中存放着最小生成树的带权边的集合。图8―14给出了用普里姆算法构造最小生成树的过程。图8―14（a）是一个有7个顶点、10条无向边的带权图。初始时算法的集合U={A}，集合V-U={B,C,D,E,F,G}，T={}，如图8―14（b）所示。在所有u为集合U中顶点，v为集合V-U中顶点的边(u,v)中，寻找具有最小权值的边(u,v)，寻找到的是边(A,B)，权为50，把顶点B从集合V-U加入到集合U中，把边(A,B)加入到T中，如图8―14（c）所示。

在所有u为集合U中顶点，v为集合V-U中顶点的边(u,v)中寻找具有最小权值的边(u,v)，寻找到的是边(B,E)，权为40，把顶点E从集合V-U加入到集合U中，把边(B,E)加入到T中，如图8―14（d）所示；随后依次从集合V-U加入到集合U中的顶点为D,F,G,C，依次加入到T中的边为(E,D),权为50，(D,F)权为30，(D,G)权为42，(G,C)权为45，分别如图8―14(e),(f),(g),(h)所示。最后得到的图8―14（h）就是原带权连通图的最小生成树。

图8―14 普里姆算法构造最小生成树的过程

图8―14 普里姆算法构造最小生成树的过程

图8―14 普里姆算法构造最小生成树的过程

我们再来讨论普里姆算法的实现问题。普里姆算法要处理的带权图对象G可以是前面讨论过的任意存储结构的图类。我们下面讨论的普里姆算法使用邻接矩阵的图类，算法中定义的对象G的顶点集合就是普里姆算法中的集合V，对象G的边集合就是普里姆算法中的集合E。普里姆算法所构造的最小生成树是集合U和集合T，集合U是顶点的集合，集合T是带权边的集合。要表示一条带权边需有三个参数，

即弧头顶点、弧尾顶点和权值，但考虑到集合U中对应位置上已有弧尾顶点，而弧头顶点是未加入新生成顶点前集合U中的一个顶点，所以算法实现时可设置一个包括两个域的数组，一个域是新加入到最小生成树中边的弧尾顶点，另一个域是新加入到最小生成树中边的权值。由这两个参数用户可以对照网G找到新加入到最小生成树中边的弧头顶点。这样实现的普里姆算法可以大大简化算法实现过程。因此，普里姆算法构造的最小生成树的数组元素结构定义为：

Struct MinSpan Tree { VerT vertex; //顶点信息 Int weight; //权值 };

我们下面设计了实现普里姆算法的外部函数，也可以把它设计成某个图类的成员函数，设计成成员函数的方法和设计成外部函数的方法类同。用普里姆方法建立网G的最小生成树minSTree的外部函数如下： struct MinSpanTree { VerTvertex; intweight; }; voidPrim(AdjMWGraph&G,MinSpanTreeminSTree［］) //用普里姆方法建立网G的最小生成树minSTree

intn=G.NumOfVertices(),minCost; int*lowCost=newint［n］; inti,j,k;  for(i=1;i<n;i++)//初始化 { lowCost［i］=G.GetWeight(0,i); closeVertex［i］.vertex=G.GetValue(0); }  //从序号为0的顶点出发构造最小生成树

minSTree［0］.vertex=G.GetValue(0); cout<<"顶点值="<<G.GetValue(0)<<endl; for(i=1;i<n;i++) { //寻找当前最小权值的边的顶点 minCost=MaxWeight;//MaxWeight为图类中定义的最大权值 j=1;k=1; while(j<n) if(lowCost［j］<minCost&&lowCost［j］!=0)

minCost=lowCost［j］; k=j; } j++; cout<<"顶点值="<<G.GetValue(k)<<"边的权值="<<minC ost cout<<endl; lowCost［k］=0; //修改其他顶点的边的权值*/ for(intj=1;j<n;j++) {

if(G.GetWeight(k,j)<lowCost［j］) { lowCost［j］=G.GetWeight(k,j); minSTree［j］.vertex=G.GetValue(k); }

上述函数存放在文件Prim.h中。分析上述普里姆算法可见，算法主要是一个两重循环，其中每一重循环的次数均为顶点个数n，所以该算法的时间复杂度为O(n2)。由于该算法的时间复杂度只与网中顶点的个数有关，而与网中边的条数无关，所以当该算法用于顶点个数不很多而边稠密的网时，时间效率较高。 以图8―14（a）所示的无向连通网为例，上述普里姆算法函数的测试程序如下：

typedefcharVerT; typedefcharDatatype; ＃include"AdjMWGraph.h" ＃include"Prim.h" ＃include"GraphLib.h“ //包含CreatGraph()函数 voidmain(void) { AdjMWGraphg;

chara［］={′A′,′B′,′C′,′D′,′E′,′F′,′G′}; RowCo lWeightrcw［］={{0,1,50},{1,0,50},{0,2,60},{2,0,6 0},{1,3,65},{3,1,65},{1,4,40},{4,1,40},{2,3,52},{3,2,52}, {2,6,45},{6,2,45},{3,4,50},{4,3,50},{3,5,30,},{5,3,30}, {3,6,42},{6,3,42},{4,5,70},{5,4,70}}; intn=7,e=20;

CreatGraph(g,a,n,rcw,e); intm=g.NumOfVertices(); MinSpanTree*closeVertex=newMinSpanTree［m］; Prim(g,closeVertex); }

程序的运行结果为： 顶点值=A 顶点值=B边的权值=50 顶点值=E边的权值=40 顶点值=D边的权值=50 顶点值=F边的权值=30 顶点值=G边的权值=42 顶点值=C边的权值=45

程序显示的顶点序列和边的权值序列对应了图8―14（b）到图8―14（h）的最小生成树构造过程。在解决实际问题时，我们根据上述程序运行的结果，再结合原问题的网，在这里为图8―14（a），即可构造出图8―14（a）的最小生成树图8―14（h）。另外，函数的返回参数minSTree中也存放了类似的结果，可用于其他使用最小生成树的应用程序的输入参数。

8.5.3 克鲁斯卡尔算法 与普里姆算法不同，克鲁斯卡尔算法是一种按照网中边的权值的递增顺序构造最小生成树的方法。克鲁斯卡尔算法的思想是：设无向连通网G=(V,E)，其中V为顶点的集合，E为边的集合。设网G的最小生成树T由顶点集合和边的集合构成，其初值为T=(V,{})，即初始时最小生成树T只由网G中的顶点集合组成，各顶点之间没有一条边。

对于图8―14（a）所示的无向连通网，按照克鲁斯卡尔算法构造最小生成树的过程如图8―15所示。根据克鲁斯卡尔算法构造最小生成树的方法，按照网G中边的权值从小到大的顺序，反复选择当前尚未被选取的边集合中权值最小的边加入到最小生成树中，直到网中所有顶点都加入到最小生成树中为止。最后，图8―15（f）所示就是所构造的最小生成树。对比图8―15（f）和图8―14（h）可以发现，虽然构造最小生成树的方法不同，但克鲁斯卡尔算法构造的最小生成树和普里姆算法构造的最小生成树结构完全相同。

图8―15 克鲁斯卡尔算法构造最小生成树的过程

按照上述克鲁斯卡尔算法思想设计克鲁斯卡尔算法函数主要包括两个部分：首先是网G中e条边的权值的排序，其次是判断新选取的边的两个顶点是否属于同一个连通分量。对网G中e条边的权值的排序方法可以有很多种，各自的时间复杂度均不相同。对e条边的权值排序算法时间复杂度最好的方法如快速排序法、堆排序法等可以达到O(elbe)。

判断新选取的边的两个顶点是否属于同一个连通分量的问题是一个在最多有n个结点的生成树中遍历寻找新选取的边的两个顶点是否存在的问题，此算法的时间复杂度最坏情况下为O(n)。一个连通分量还可以看作是一个等价类，判断新选取的边的两个顶点是否属于同一个连通分量的问题可以看作是一个求等价类的过程。等价类属于集合结构，本书没有讨论。关于排序问题我们将在第9章讨论。

从上述分析我们可以得出，克鲁斯卡尔算法的时间复杂度主要由排序方法决定，而克鲁斯卡尔算法的排序方法只与网中边的个数有关，而与网中顶点的个数无关，当使用时间复杂度为O(elbe)的排序方法时，克鲁斯卡尔算法的时间复杂度即为O(elbe)，因此当网的顶点个数较多、而边的条数较少时，使用克鲁斯卡尔算法构造最小生成树效果较好。  

8.6 最短路径   8.6.1 最短路径的基本概念 在一个图中，若从一个顶点到另一个顶点存在着一条路径，则称该路径的路径长度为该路径上所经过的边的数目。图中从一个顶点到另一个顶点可能存在着多条路径，我们把路径长度最短的那条路径叫做最短路径，其路径长度叫做最短路径长度或最短距离。

在一个网中，若从一个顶点到另一个顶点存在着一条路径，则称该路径上所经过边的权值之和为该路径上的带权路径长度。网中从一个顶点到另一个顶点可能存在着多条路径，我们把带权路径长度最短的那条路径也叫做最短路径，其带权路径长度也叫做最短路径长度或最短距离。

实际上，不带权的图上最短路径问题也可以归结为带权的网上最短路径问题。因只要把不带权的图上所有边上的权值均定义为1，则不带权的图上最短路径问题也就归结为带权的网上最短路径问题了。因此不失一般性，我们这里只讨论带权的网上最短路径问题。 网有无向网和有向网，当把无向网中的每一条边(vi,vj)都定义为弧〈vi,vj〉和弧〈vj,vi〉，则有向网就变成了无向网。因此不失一般性，我们这里只讨论带权的有向网上最短路径问题。

图8―16是一个有向网和它的邻接矩阵。该网从顶点A到顶点D有三条路径，分别为路径（A,D），其带权路径长度为30；路径（A,C,F,D），其带权路径长度为22；路径（A,C,B,E,D），其带权路径长度为32；路径（A,C,F,D）称为最短路径，其带权路径长度22称为最短距离。

图8―16 有向网及其邻接矩阵 （a）有向网；（b）邻接矩阵

8.6.2 从一个顶点到其余各顶点的最短路径 对于从有向网中一个确定顶点（称为源点）到其余各顶点的最短路径问题，狄克斯特拉(Dijkastra)提出了一个按路径长度递增的顺序逐步产生最短路径的构造算法，狄克斯特拉算法的思想是：设置两个顶点的集合S和T，集合S中存放已找到最短路径的顶点，集合T中存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点，设为v0。然后，不断从集合T中选择到源点v0路径长度最短的顶点u加入到集合S中。

集合S中每加入一个新的顶点u，都要修改源点v0到集合T中剩余顶点的当前最短路径长度值。集合T中各顶点的新的当前最短路径长度值，为原来的当前最短路径长度值与顶点u的最短路径长度值加上顶点u到该顶点的路径长度值（即为从源点过顶点u到达该顶点的路径长度）中的较小者。此过程不断重复，直到集合T中的顶点全部加入到集合S中为止。 对于图8―16所示的有向网，图8―17给出了狄克斯特拉算法求从顶点A到其余各顶点的最短路径的过程。图中，虚线表示当前可选择的边，实线表示算法已确定包括到集合S中的顶点所对应的边。

图8―17 狄克斯特拉算法求从顶点A到其余 各顶点的最短路径的过程

函数设计成迭代过程。设从源点v0到其余各顶点中最短的一条路径为(v0,vk)，其中vk满足： distance［vk］=min{distance［vi］|vi∈V-v0}V 是网G的顶点 一旦确定distance［vk］且distance［vk］小于最大权值，则标识顶点vk已从集合T到集合S中。

根据上述设计思想设计的外部函数如下，该外部函数也可方便地改为图类的成员函数。   voidDijkstra(AdjMWGraph&G,intv0,intdistance［］,intpath［］) //网G从下标v0顶点到其他顶点的最短距离distance和最短路径下标path {intn=G.NumOfVertices(); int*s=newint［n］; intminDis,i,j,u;   //初始化 for(i=0;i<n;i++) {

distance［i］=G.GetWeight(v0,i); s［i］=0; if(i!=v0&&distance［i］<MaxWeight)path［i］=v0; elsepath［i］=-1; } s［v0］=1;//标记顶点v0已从集合T加入到集合S中 //在当前还未找到最短路径的顶点集中选取具有最短距离的顶点u for(i=1;i<n;i++) { minDis=MaxWeight; for(j=0;j<=n;j++)

if(s［j］==0&&distance［j］<minDis) { u=j; minDis=distance［j］; } //当已不再存在路径时算法结束；此语句对非连通图是必需的 if(minDis==MaxWeight)return; s［u］=1;//标记顶点u已从集合T加入到集合S中 //修改从v0到其他顶点的最短距离和最短路径 for(j=0;j<n;j++) if(s［j］==0&&G.GetWeight(u,j)<MaxWeight&&

distance［u］+G.GetWeight(u,j)<distan ce［j］) { //顶点v0经顶点u到其他顶点的最短距离和最短路径 distance［j］=distance［u］+G.GetWeight (u,j); path［j］=u; }

上述函数的主体是两个循环次数为顶点个数n的循环，所以该函数的时间复杂度为O(n2)。 以图8―16的有向网为例的测试程序如下： typedefcharVerT; typedefcharDatatype; ＃include"AdjMWGraph.h" ＃include"Dijkstra.h" ＃include"GraphLib.h"   voidmain(void) {

AdjMWGraphg; chara［］={′A′,′B′,′C′,′D′,′E′,′F′}; RowCo lWeightrcw［］={{0,2,5},{0,3,30},{1,0,2},{1,4,8} ,{2,1,15},{2,5,7},{4,3,4},{5,3,10},{5,4,18}}; intn=6,e=9; CreatGraph(g,a,n,rcw,e);   intm=g.NumOfVertices(); int*distance=newint［m］; int*path=newint［m］; intv0=0;

Dijkstra(g,v0,distance,path); cout<<"从顶点"<<g.GetValue(v0)<<"到其他各顶点的最短距离为： "<<endl; for(inti=0;i<m;i++) cout<<"到顶点"<<g.GetValue(i) <<"的最短距离为："<<distance［i］<<endl; cout<<"从顶点"<<g.GetValue(v0) <<"到其他各顶点最短路径的前一顶点为："<<endl; for(i=0;i<m;i++) if(path［i］!=-1)

cout<<"到顶点"<<g.GetValue(i) <<"的前一顶点为"<<g.GetValue(path［i］)<<end l; }

程序的运行结果如下： 从顶点A到其他各顶点的最短距离为： 到顶点A的最短距离为：0 到顶点B的最短距离为：20 到顶点C的最短距离为：5 到顶点D的最短距离为：22 到顶点E的最短距离为：28 到顶点F的最短距离为：12

从顶点A到其他各顶点最短路径的前一顶点为： 到顶点B的前一顶点为：C 到顶点C的前一顶点为：A 到顶点D的前一顶点为：F 到顶点E的前一顶点为：B 到顶点F的前一顶点为：C

当测试程序的v0=3时的运行结果如下： 从顶点D到其他各顶点的最短距离为： 到顶点A的最短距离为：10000 到顶点B的最短距离为：10000 到顶点C的最短距离为：10000 到顶点D的最短距离为：0 到顶点E的最短距离为：10000 到顶点F的最短距离为：10000 如果在函数中没有语句： if(minDis==MaxWeight)return; 则当v0=3时，因从源点v0到其他顶点没有路径存在而出错。

8.6.3 所有顶点之间的最短路径 对于一个各边权值均大于0的有n个顶点的带权有向图，若要求所有顶点之间的最短路径和最短距离，可轮流以每一个顶点为源点，重复调用上述狄克斯特拉算法函数Dijkstra()n次，即可求得所有顶点之间的最短路径和最短距离。 利用Dijkstra()函数求所有顶点之间的最短路径算法如下。其中，distance［i］中存放着从顶点i到其他顶点的最短距离，path［i］中存放着从顶点i到其他顶点的最短路径的前一顶点下标。

voidShortPath(AdjMWGraph&G,int**distance,int**path) { intn=G.NumOfVertices(); for(inti=0;i<n;i++) Dijkstra(G,i,distance［i］,path［i］); }

由于狄克斯特拉算法的时间复杂度是O(n2)，所以n次调用狄克斯特拉算法的时间复杂度是O(n3)。 以图8―16的有向网为例的测试程序如下。其中，函数Make2DArray()为5.2节讨论的两维动态数组。 ＃include<conio.h>//包含getch()函数 typedefcharVerT; typedefcharDatatype; ＃include"AdjMWGraph.h" ＃include"Dijkstra.h" ＃include"GraphLib.h"

voidShortPath(AdjMWGraph&G,int**distance,int**path) { intn=G.NumOfVertices(); for(inti=0;i<n;i++) Dijkstra(G,i,distance［i］,path［i］); } template<classT> voidMake2DArray(T**&a,introw,intcol) //定义二维动态数组a，其行数为row,列数为col

{ a=newT*［row］;//a为有row个指针的指针数组 for(inti=0;i<row;i++) a［i］=newT［col］;//每个指针指向一个有col 个元素空间的数组 } voidmain(void) AdjMWGraphg;

chara［］={′A′,′B′,′C′,′D′,′E′,′F′}; RowColWeightrcw［］={{0,2,5},{0,3,30},{1,0,2},{1,4,8}, {2,1,15},{2,5,7},{4,3,4},{5,3,10},{5,4,18}}; intn=6,e=9; CreatGraph(g,a,n,rcw,e); intm=g.NumOfVertices(); int**distance,**path; Make2DArray<int>(distance,m,m); Make2DArray<int>(path,m,m);

ShortPath(g,distance,path);  inti,j; for(i=0;i<m;i++) { cout<<"从顶点"<<g.GetValue(i) <<"到其他各顶点的最短距离为："<<endl; for(j=0;j<m;j++) cout<<"到顶点"<<g.GetValue(j) <<"的最短距离为："<<distance［i］［j］< <endl;

cout<<"从顶点"<<g.GetValue(i) <<"到其他各顶点最短路径的前一顶点分别为："<<endl; for(j=0;j<m;j++) if(path［i］［j］!=-1) cout<<"到顶点"<<g.GetValue(j) <<"的前一顶点为"<<g.GetV alue(path［i］［j］)<<endl; getch();//键入任意键继续，以便观察屏幕 }

在递推求最短距离An［i］［j］的过程中，我们同时定义pathk［i］［j］。pathk［i］［j］保存从顶点vi到顶点vj递推产生的最短路径的顶点序号，且该最短路径上所经过的顶点序号不大于k。 根据上述弗洛伊德算法思想求所有顶点之间的最短路径和最短距离的函数如下： voidFloyd(AdjMWGraph&G,int**distance,int**path) //求图G中每对顶点之间的最短距离distance和最短路径的顶点序号path { inti,j,k; intn=G.NumOfVertices();

//初始化 for(i=0;i<n;i++) for(j=0;j<n;j++) { distance［i］［j］=G.GetWeight(i,j); if(i!=j&&distance［i］［j］!=MaxWeight)path［i ］［j］=i; elseif(i==j)path［i］［j］=0; elsepath［i］［j］=-1; }

for(k=0;k<n;k++) for(i=0;i<n;i++) for(j=0;j<n;j++) { if(distance［i］［j］>(distance［i］［k］ +distance［k］［j］)) distance［i］［j］=distance［i］ ［k］+distance［k］［j］;

path［i］［j］=path［k］［j］; }

如前面所分析的，在第k+1次递推时存在两种可能性，从顶点vi到顶点vj又产生一条经过序号为k+1顶点的路径和不存在经过序号为k+1的顶点的路径。当从顶点vi到顶点vj又产生一条经过序号为k+1顶点的路径时，还要判断新产生路径的距离是否比原来路径的距离短；当距离短时替换，否则不替换。 上述算法产生的最短路径的顶点序列中间的若干个顶点序号会出现不连续，但可根据最短距离和原始网的邻接矩阵识别出，即此最短路径的顶点序列可作辅助参考。