图的基本概念和基本操作.ppt

第8章 图,8.1 图的基本概念和基本操作 8.2 图的邻接矩阵存储结构 8.3 图的邻接表存储结构 8.4 图的其他存储结构 8.5 最小生成树 8.6 最短路径,8.1 图的基本概念和基本操作,8.1.1 图的基本概念 图（Graph）是由顶点集合及顶点间的关系集合组成的一种数据结构。 图G的定义是： G =（V， E） 式中： V = x|x某个数据对象 E =（x， y）|x， yV 或 E = x，y|x， yV并且Path（x，y）,图81 带自身环的图和多重图 （a） 带自身环的图； （b） 多重图,这样， 在图G中， V是顶点的有穷非空集合， E是顶点之间关系的有穷集合， E也叫做边的集合。 图有许多复杂结构， 本教材只讨论最基本的图， 因此， 本书讨论的图中不包括图81所示两种形式的图。 图81（a） 中有从顶点A到自身的边存在， 称为带自身环的图; 图81（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) 权： 有些图的边附带有数据信息， 这些附带的数据信息称为权。 权可以表示实际问题中从一个顶点到另一个顶点的距离、 花费的代价、 所需的时间， 等等。 带权的图称作网络。图83就是带权图。 其中， 图83（a）是一个工程的施工进度图， 图8-3（b）是一个交通网络图。,图83 带权图 （a） 施工进度图； （b） 交通网络图,（7） 路径长度： 对于不带权的图， 一条路径的路径长度是指该路径上的边的条数； 对于带权的图， 一条路径的路径长度是指该路径上各个边权值的总和。 在图8的无向图G2中， 路径0, 1, 3的路径长度为2； 在图83（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是连通的。 如果图中任意一对顶点都是连通的， 则称该图是连通图。 非连通图的极大连通子图称作连通分量。 图82的无向图G1和G2都是连通图。 (10) 强连通图和强连通分量： 在有向图中， 若对于每一对顶点vi和vj都存在一条从vi到vj和从vj到vi的路径， 则称该图是强连通图。 非强连通图的极大强连通子图称作强连通分量。 图82的有向图G4是强连通图。 图82的有向图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, jE,否则,由于矩阵A中的元素aij表示了顶点i和顶点j之间边的关系， 或者说， A中的元素aij表示了顶点i和其他顶点j（0jn-1）的邻接关系， 所以矩阵A称作邻接矩阵。 在图的邻接矩阵存储结构中， 顶点信息使用一维数组存储， 边信息的邻接矩阵使用二维数组存储。 图84（a）是一个无向图， 图84（b）是对应的邻接矩阵存储结构。 其中， V表示了图的顶点集合， A表示了图的邻接矩阵。 无向图的邻接矩阵一定是对称矩阵。 从无向图的定义和无向图的邻接矩阵定义可知， 邻接矩阵中第i行（或第i列）中非零元素的个数等于第i个顶点的度数。 又由于邻接矩阵中非零元的数值为1， 所以有,图84无向图及其邻接矩阵 （a） 无向图； （b） 邻接矩阵,图85（a）是一个有向图， 图85（b）是对应的邻接矩阵存储结构， 其中， V表示图的顶点集合， A表示图的邻接矩阵。 有向图的邻接矩阵一般是非对称矩阵。从有向图的定义和有向图的邻接矩阵定义可知， 有向图的邻接矩阵中第i行中非零元素的个数等于第i个顶点的出度， 有向图的邻接矩阵中第i列中非零元素的个数等于第i个顶点的入度， 又由于邻接矩阵中非零元素的数值为1， 所以有：,图85 有向图及其邻接矩阵 （a） 有向图； （b） 邻接矩阵,对于网（或称带权图）， 邻接矩阵A的定义为：,ij且(i,j)E或i,jE,否则但ij,否则但i=j,其中， wij0， wij是边(i, j)或弧，i, j的权值， 权值wij表示了从顶点i到顶点j的代价或称费用。 当i=j时， 邻接矩阵中的元素aij=0可理解为从一个顶点到自己顶点没有代价， 这也完全和实际应用中的问题模型相符。 有种特殊的网允许wij为负值， 本书讨论的网不包括此种网。,图86（a）是一个带权图， 图86（b）是对应的邻接矩阵存储结构。 其中， V表示图的顶点集合， A表示图的邻接矩阵。 对于带权图， 邻接矩阵第i行中所有0aij的元素个数等于第i个顶点的出度， 邻接矩阵第j列中所有0aij的元素个数等于第j个顶点的出度。,图86 带权图及其邻接矩阵 （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 EdgeMaxVerticesMaxVertices; /边的权信息的矩阵 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 ,/删除弧v1,v2 void DeleteEdge(const int v1,const int v2); /取顶点v的第一条邻接边， 取到返回该邻接边的邻接顶点下标； 否则返回-1 int GetFirstNeighbor(const int v); /取顶点v1的邻接边的下一条邻接边， /若下一条邻接边存在， 则返回该邻接边的邻接顶点下标； 否则返回-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, void visit(VerT item); /对非连通图用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) Edgeij = 0; else Edgeij = MaxWeight; / MaxWeight表示无穷大 numOfEdges = 0; /当前边个数初始为0 ,VerT AdjMWGraph:GetValue(const int i) /取顶点i的值 if(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 Vertices.ListSize() | v2 Vertices.ListSiz e() cerr “参数v1或v2越界出错!“ endl; exit(1); ,return Edgev1v2; /返回弧v1,v2的权 void AdjMWGraph:InsertVertex(const VerT ,void AdjMWGraph:InsertEdge(const int v1,const int v2,int weight) /插入弧v1,v2， 权为weight if(v1 Vertices.ListSize() | v2 Vertices.ListSiz e() cerr “参数v1或v2越界出错!“ endl; exit(1); Edgev1v2 = 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) /删除顶点v ,void AdjMWGraph:DeleteEdge(const int v1,const int v2) /删除弧，v1,v2 if(v1 Vertices.ListSize() | v2 Vertices.ListSize() | v1 = v2) cerr “参数v1或v2出错!“ endl; exit(1); ,Edgev1v2 = 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 Vertices.ListSize( ) ,cerr 0 /不存在， 则返回-1 int AdjMWGraph:GetNextNeighbor(const int v1,const int v2) /找顶点v1的v1,v2邻接边的下一条邻接边，,/若下一条邻接边存在,则返回该邻接边的邻接顶点下标； 否则返回-1 if(v1 Vertices.ListSize() | v2 Vertices.ListSize() cerr “参数v1或v2越界出错!“ endl; exit(1); ,/ 使col = v2+1， 因此寻找的是顶点v1的v1,v2邻接边的下一条邻接边 for(int col = v2+1; col 0 /不存在， 则返回-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 visitedv = 1; /标记顶点v已访问 int w = GetFirstNeighbor(v); /顶点w为顶点v的第一个邻接顶点,while(w != -1) /当邻接顶点存在时循环 if(! visitedw) DepthFirstSearch(w,visited,visit);/ /对顶点w递归 /顶点w为顶点v的w邻接顶点的下一个邻接顶点 w = GetNextNeighbor(v,w); ,上述递归算法属于第6章讨论过的回溯算法， 当寻找顶点v的邻接顶点成功时继续进行， 当寻找顶点v的邻接顶点失败时回溯到上一次递归调用的地方继续进行。 对于图87所示的无向连通图， 若顶点A为访问的首顶点， 则深度优先搜索遍历的顶点访问顺序是： A B D E C F G 。,图87 无向连通图及其邻接矩阵 （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); visitedv = 1; queue.QInsert(v); /顶点v入队列,while(!queue.QueueEmpty() /当队列非空时循环 u = queue.QDelete(); /出队列得到队头顶点u w = GetFirstNeighbor(u); while(w != -1) /若顶点u的邻接顶点w存在时循环 if(!visitedw) ,visit(GetValue(w); visitedw = 1; queue.QInsert(w); /顶点w入队列 w = GetNextNeighbor(u,w); /顶点u的w邻接顶点的下一个邻接顶点 ,8.2.5 非连通图和连通分量 对于连通图， 从图的任意一个顶点开始深度或广度优先遍历一定可以访问图中的所有顶点；但对于非连通图， 从图的任意一个顶点开始深度或广度优先遍历并不能访问图中的所有顶点。 对于非连通图， 从图的任意一个顶点开始深度或广度优先遍历只能访问包括该首顶点的连通分量中的所有顶点。,但当我们把每一个顶点都作为一次首顶点深度或广度优先遍历非连通图， 并根据顶点的访问标记来判断是否需要访问该顶点时， 就一定可以访问该非连通图中的所有顶点。 非连通图的深度优先搜索遍历算法如下： void AdjMWGraph:DepthFirstSearch(void visit(VerT item)= /定义顶点访问标记数组 int *visited = new intNumOfVertices(); /顶点访问标记数组初始化,for(int i = 0; i NumOfVertices(); i+) visitedi = 0; for(i = 0; i NumOfVertices(); i+) /对所有顶点循环 /如该顶点尚未被访问则以该顶点为首顶点深度优先遍历访问 if(! visitedi) DepthFirstSearch(i,visited,visit); delete visited; /删除顶点访问标记数组 ,非连通图的广度优先搜索遍历算法如下： void AdjMWGraph:BroadFirstSearch(void visit(VerT item) int *visited = new intNumOfVertices( ); for(int i = 0; i NumOfVertices(); i+) visitedi = 0; for(i = 0; i NumOfVertices(); i+) if(!visitedi) BroadFirstSearch(i,visited,visit); delete visited; ,非连通图的广度优先搜索遍历算法和非连通图的深度优先搜索遍历算法类同， 故不再作注释。 对于图87所示的无向连通图， 若删除弧0, 2和2, 0， 则该图变为图8-8所示的非连通图。 图88非连通图的深度优先搜索遍历顶点序列为： A B D E C F G 。 图88非连通图的广度优先搜索遍历顶点序列为： A B D E C F G 。,图88 非连通图,8.2.6 邻接矩阵图类的测试 我们以图87所示的无向连通图为例测试邻接矩阵图类。 我们首先给出建立邻接矩阵图类对象的外部函数。 为后面使用方便， 我们把下面的结构体定义和外部函数放在文件GraphLib.h中。 struct RowColWeight /定义结构体类型RowColWeight int row; /行下标,int col; /列下标 int weight; /权值 ; voidCreatGraph(AdjMWGraph /向图G中插入e条边E0.Ee-1,for(int k = 0; k e; k+) G.InsertEdge(Ek.row,Ek.col,Ek.weight); void Printchar(char item) /访问顶点的函数 cout item“ “; ,使用图87所示的无向连通图的测试程序如下： 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 intg.NumOfVertices( ); for(int i = 0; i g.NumOfVertices( ); i+) visitedi = 0; g.DepthFirstSearch(0,visited,Printchar); cout endl “广度优先搜索序列为：“; for(i = 0; i g.NumOfVertices(); i+) visitedi = 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后非连通图有 当前的顶点个数为： 7； 当前的边的条数为： 10； 非连通图的深度优先搜索序列为： A B D E C F G； 非连通图的广度优先搜索序列为： A B D E C F G。,8.3 图的邻接表存储结构,8.3.1 图的邻接表存储结构 图的邻接矩阵存储结构的主要特点是把图的边信息存储在一个nn矩阵中。 其中， n为图中的顶点个数。 当这个nn阶矩阵是稠密矩阵时， 图的邻接矩阵存储结构是最常用也是最高效的存储结构。,图89是图85（a）所示有向图的邻接表存储结构。 严格地说， 该图的边信息存储矩阵不是一个稀疏矩阵， 因顶点个数太少， 但为使我们讨论问题和表示问题不致过于麻烦， 所以我们假设该图的边信息存储矩阵是一个稀疏矩阵。,图89 有向图的邻接表存储结构,图89中行数组的data域存储图的顶点信息， adj域为该顶点的邻接顶点单链表的头指针。 第i行单链表中的dest域存储边i,j的邻接顶点j， 对于任意一条边i,j， 因i值和存储该顶点的下标值一致， 所以不需要再另外存储。 如果是带权图再增加cost域， 第i行单链表中的dest域值为j的cost域中存储了边i,j的权值wij。 对比图89和第5章图54的行指针数组结构的三元组链表， 可以发现， 两者讲述的是同一种存储结构。,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 VerticesMaxVertices; /顶点数组 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 ,void DepthFirstSearch(const int v,int visited, void visit(VerT item); void BroadFirstSearch(const int v,int visited, void visit(VerT item); void DepthFirstSearch(void visit(VerT item); void BroadFirstSearch(void visit(VerT item); ;,1.构造函数和析构函数 AdjTWGraph:AdjTWGraph(void) for(int i = 0; i MaxVertices; i+) Verticesi.adj = NULL; numVertices = 0; numOfEdges = 0; AdjTWGraph:AdjTWGraph(void) /释放为存储边信息所动态建立的邻接链表的空间, for(int i = 0; i next; delete p; p = q; ,2.简单成员函数的实现 VerT AdjTWGraph:GetValue(const int i) if(i numVertices) cerr “参数i越界出错!“ endl; exit(1); return Verticesi.data; int AdjTWGraph:GetWeight(const int v1,const int v2), if(v1 numVertices | v2 numVertices) cerr dest next; if(v2 != p-dest) ,cerr 不存在!“ weight; ,3. 插入顶点和边以及删除顶点和边成员函数的实现 插入顶点成员函数很简单， 只需在存放顶点信息的数组中插入一个顶点信息。 void AdjTWGraph:InsertVertex(const VerT ,插入边v1,v2的操作是要在数组下标的v1行中的邻接链表中插入一个包含dest, weight和next域的结点。 其中， dest域的值为v2， 邻接链表按dest域的值递增有序。 这是一个建立单链表的过程， 由于所建立的单链表无头指针， 所以算法中要分别考虑是否是单链表的第一次插入； 在不是单链表的第一次插入时,还要考虑在单链表的第一个结点前插入和在单链表的其他位置插入的情况。,void AdjTWGraph:InsertEdge(const int v1,const int v2,int w eight) if(v1 numVertices | v2 numVertices) cerr “参数v1或v2越界出错!“ endl; exit(1); Edge *q = new Edge(v2,weight);,if(Verticesv1.adj = NULL) /第一次插入 Verticesv1.adj = q; Else /非第一次插入 Edge *curr = Verticesv1.adj,*pre = NULL; while(curr != NULL if(pre = NULL) /在第一个结点前插入, q-next = Verticesv1.adj; Verticesv1.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 dest v) ,pre = curr; curr = curr-next; if(pre = NULL else if(curr != NULL & curr-dest = v) /该出边结点是单链表的其他结点时, pre-next = curr-next; delete curr; numOfEdges-; Edge *p = Verticesv.adj,*q; for(i = v; i numVertices-1; i+) Verticesi = Verticesi+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 numVertices | v2 numVertices) cerr dest v2) ,pre = curr; curr = curr-next; if(pre = NULL ,else if(pre != NULL else /参数出错， 该边不存在, cerr 不存在!“ endl; exit(1); ,4. 遍历成员函数要调用的成员函数 int AdjTWGraph:GetFirstNeighbor(const int v) if(v numVertices) cerr dest; else return -1; ,int AdjTWGraph:GetNextNeighbor(const int v1,const int v2) if(v1 numVertices | v2 numVertices) cerr “参数v1或v2越界出错!“ endl; exit(1); Edge *p = Verticesv1.adj; while(p != NULL) ,if(p-next != NULL ,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); visitedv = 1; int w = GetFirstNeighbor(v); while(w != -1), if(! visitedw) 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的邻接顶点下标，逆邻接表也因此而得名。图85（a）的有向图的逆邻接表存储结构如图810所示。,图810 逆邻接表,在逆邻接表中求