数据结构课件第六章

1、第六章 图图的基本概念图的存储结构图的遍历最小生成树最短路径 活动网络 图的定义 图是由顶点的有限集合(vertex)及顶点间的关系集合组成的一种数据结构： Graph(V, E ) 其中： V = x | x 某个数据对象是顶点的有穷非空集合； E = (x,y) | x,y V 是顶点之间关系的有穷集合，也叫做边(edge)集合。6.1 图的基本概念V(G1)=0, 1, 2, 3; E(G1)=(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3) V(G2)=0, 1, 2, 3, 4, 5, 6; E(G2)=(0, 1), (0, 2), (1

2、, 3), (1, 4), (2, 5), (2, 6) V(G3)=0, 1, 2; E(G3)=, 01230123456012G1G2G3 有向图与无向图 在有向图中，顶点对是有序的。在无向图中，顶点对(x, y)是无序的。完全图 若有n个顶点的无向图有n(n-1)/2 条边, 则此图为完全无向图。有n个顶点的有向图有n(n-1) 条边，则此图为完全有向图。邻接顶点 如果(u, v)是E(G)中的一条边，则称u与v 互为邻接顶点，边(u, v)使得顶点u, v之间相关联 。权 某些图的边具有与它相关的数，称之为权。这种带权图叫做网络。子图 设有两个图 G(V, E) 和G(V, E)。若

3、VV 且EE，则称图G是图G的子图。顶点的度 一个顶点v的度是与它相关联的边的条数。记作TD(v)。在有向图中, 顶点的度等于该顶点的入度与出度之和。对于有向图，顶点v的入度是以v为终点的有向边的条数，记作 ID(v)；顶点v的出度是以v为始点的有向边的条数， 记作OD(v)。路径 在图G(V,E)中，若从顶点vi出发，沿一些边经过一些顶点vp1，vp2，vpm，到达顶点vj。则称顶点序列(vi、vp1、vp2、.、vpm、vj)为从顶点vi到顶点vj的路径。它经过的边(vi,vp1)、(vp1,vp2)、.、(vpm,vj)应是属于E的边。路径长度 非带权图的路径长度是指此路径上边的条数。带

4、权图的路径长度是指路径上各边的权之和。简单路径 若路径上各顶点v1, v2, ., vm均不互相重复, 则称这样的路径为简单路径。回路 若路径上第一个顶点v1与最后一个顶点vm重合, 则称这样的路径为回路或环。连通图与连通分量 在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。非连通图的极大连通子图叫做连通分量。强连通图与强连通分量 在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。生成树 一个连通图的生成树是它的极小

5、连通子图，在n个顶点的情形下，有n-1条边。不予讨论的图例回答下列问题：（1）对于一个具有n个顶点的连通无向图，最多有多少条边，最少有多少条边？（2）对于一个具有n个顶点的强连通有向图，最多有多少条边，最少有多少条边？（1）最多有n(n-1)/2条边，最少有n-1条边。（2）最多有n(n-1)条边，最少有n条边。例 若具有n个顶点的无向图G的顶点度数的和大于或等于2n，则G中必然存在回路，试证明之。假定G有n个顶点，度之和为N，N2n。因为图中每条边涉及两个顶点，也即每条边含有两个度，因此，图中至少有n条边。因为对应一个n个顶点的树图只有n1条边，如果多于n1条边则树图将不存在，也即图中必然存

6、在回路，而由前述所知，该图至少有n条边，故该图必有回路存在。图的抽象数据类型template class Graph public: Graph ( ); void InsertVertex ( const T & vertex ); /插入顶点 void InsertEdge( int v1, int v2, int weight); /插入边 void RemoveVertex ( int v ); /删除顶点 void RemoveEdge ( int v1, int v2 ); /删除边 bool IsEmpty( ); /判边集是否为空 T GetWeight ( int v1, i

7、nt v2 ); 返回边上的权值 int GetFirstNeighbor ( int v ); 返回v的第一个邻接顶点的位 置 int GetNextNeighbor ( int v1, int v2 ); 下一个邻接顶点的位置;6.2 图的存储表示在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。设图G =(V,E )是一个有n个顶点的图，则图的邻接矩阵是一个二维数组 An, n，定义为：无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。邻接矩阵 (Adjacency Matrix)在有向图中, 统计第i行1的个数可得顶点i的出度，统计第

8、j列1的个数可得顶点j的入度。在无向图中，统计第i行(列)1的个数可得顶点i的度。网络的邻接矩阵template class Graph public: Graph ( int sz=DefaultVertices); graph(); bool GraphEmpty( ) const if (numEdges = 0) return ture; else return false; bool GraphFull ( ) const if (numVertices = maxVertices | numEdges = maxVertices*(maxVertices-1)/2) return

9、ture; else return false; 图的模板基类 int NumberOfVertices( ) return numVertices; int NumberOfEdges ( ) return numEdges; virtual bool InsertVertex ( const Type vertex ); virtual bool InsertEdge( int v1, int v2, E cost); virtual bool RemoveVertex ( int v ); virtual bool RemoveEdge ( int v1, int v2 ); T Get

10、Weight ( int v1, int v2 ); int GetFirstNeighbor ( int v ); int GetNextNeighbor ( int v1, int v2 ); Protected int maxVertices; int numEdges; int numVertices; int getVertexPos(T vertex);template class Graphmtx : public gragh friend istream&operator (istream&in, grapgmtx & G)friend ostream&operator (os

11、tream&out, grapgmtx & G)public: Graphmtx ( int sz=DefaultVertices); /构造函数 Graphmtx( delete VerticesList; delete Edge; ) T GetValue ( int i ) /取顶点 return i = 0 & i numVertices ? VerticesListi : NULL; E GetWeight (int v1, int v2 ) /取边上的权 return v1!=-1&v2!=-1 ? Edgev1v2 : 0;用邻接矩阵表示的图的类的定义 int GetFirstN

12、eighbor ( int v ); /取邻接顶点 int GetNextNeighbor ( int v, int w ); /取邻接顶点的下一个邻接顶点 bool InsertVertex ( const T vertex ); /插入顶点 bool InsertEdge ( int v1, int v2, E cost ); /插入边 bool RemoveVertex ( int v ); /删除顶点 bool RemoveEdge ( int v1, int v2 ); /删除边private: T * VerticesList; E * Edge; int GetVertexPos

13、 ( T vertex ) /给出顶点在图中的位置 for ( i=1; i numVertices ) if (VerticesListi = vertex) return i; return 0; template Graphmtx:Graph( int sz)/构造函数 maxVertices = sz; numVertices = 0; numEdges = 0; int i, j; VerticesList = new TmaxVertices; Edge = (int * *) new int * maxVertices; for (i=0; imaxVertices; i+) E

14、dgei = new intmaxVertices; for (i = 0; i sz; i+ ) for ( j = 0; j sz; j+ ) Edgeij = ( i=j ) ? 0 : maxWeight;邻接矩阵实现的部分图操作（构造）template int Graphmtx:getFirstNeighbor(int v)/给出顶点位置v的第一个邻接顶点的位置，如果找 不到，则函数返回-1。 if ( v != -1 ) for ( int col=0; col0 & EdgevcolmaxWeight ) return col; return -1; 邻接矩阵实现的部分图操作（找

15、第一个邻接顶点）template int Graphmtx:getNextNeighbor(int v, int w)/给出顶点v的某邻接顶点w的下一个与v的邻接顶点 if (v != -1 & w != -1) for ( int col=w+1; col0 & EdgevcolmaxWeight) return col; return -1; 邻接矩阵实现的部分图操作（找下一个邻接顶点）template int Graphmtx:insertVertex(const T& vertex)/插入顶点vertex if (numVertices=maxVertices) return fals

16、e;/顶点表满，不插入 VerticesListnumVertices+=vertex;return ture; 邻接矩阵实现的部分图操作（插入一个顶点）template int Graphmtx:removeVertex(int v)/删去顶点v和所有与它关联的边 if (v=numVertices) return false; /v不再图中，不删除 if (numVertices=1) return false; /只剩一个顶点，不删除 int i, j; VerticesListv = VerticesListnumVertices-1; /顶点表中删除该结点 for (i=0; i0&

17、EdgeivmaxWeight) numEdges-; 邻接矩阵实现的部分图操作（删除一个顶点） for (i=0; inumVertices; i+)/用最后一列填补第v列 Edgeiv = EdgeinumVertices-1; numVertices-; /顶点数减1 for (j=0; jnumVertices; j+) /用最后一行填补第v行 Edgevj=EdgenumVerticesj; return true; template int Graphmtx:insertEdge(int v1, int v2, E cost)/插入边（v1, v2）权值为cost if (v1-1

18、&v1-1& v2numVertices&Edgev1v2=maxWeight) /插入条件 Edgev1v2=Edgev2v1=cost; numEdges+;return ture; else return false; 邻接矩阵实现的部分图操作（插入一条边）template int Graphmtx:removeEdge(int v1,int v2)/在图中删除边（v1,v2） if (v1-1&v1-1& v20& Edgev1v2maxWeight) Edgev1v2=Edgev2v1=maxWeight; numEdges-; return true; else return fa

19、lse;邻接矩阵实现的部分图操作（删除一条边）template istream& operator istream&in,Graphmtx&G /通过从输入流对象in输入n个顶点信息和e条无向边 的信息建立用邻接矩阵表示的图G。 /邻接矩阵初始化的工作已经在构造函数中完成。 int i, j, k, n, m; T e1, e2; E weight; innm; /输入顶点数n和边数m for (i=0; ie1;G.insertVertex(e1); i=0;通过输入建立图的邻接矩阵表示 while (ie1e2weight; /输入端点信息 j=G.getVertexPos(e1); k=

20、G.getVertexPos(e2); /查顶点号 if (j=-1|k=-1) cout边两端点信息有误，重新输入！endl; else G.inserEdge(j, k, weight); i+; return in;template ostream& operator (ostream& out,Graphmtx&G) /输出图的所有顶点和边的信息 int i, j, k, n, m; T e1, e2; E w; n =G.NumberOfVertices(); m=G.NumberOfEdges(); outn,mendl; /输出顶点数与边数 输出邻接矩阵表示的图的顶点和边信息 f

21、or (i=0; in; i+) for (j=i+1; j0&wmaxWeight) /有效 e1=G.getValue(i); e2=G.getValue(j); /输出 out(e1,e2,w)endl; return out;邻接表 (Adjacency List)无向图的邻接表把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做边结点，结点中保存有与该边相关联的另一顶点的顶点下标dest和指向同一链表中下一个边结点的指针link。有向图的邻接表和逆邻接表在有向图的邻接表中，第i个边链表链接的边都是顶点i发出的边。也叫做出边表。在有向图的逆邻接表中，第i个边链表链

22、接的边都是进入顶点i的边。也叫做入边表。带权图的边结点中保存该边上的权值cost。顶点i的边链表的表头指针adj在顶点表的下标为i的顶点记录中，该记录还保存了该顶点的其它信息。在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。设图中有n个顶点，e条边，则用邻接表表示无向图时，需要n个顶点结点，2e个边结点；用邻接表表示有向图时，若不考虑逆邻接表，只需n个顶点结点，e 个边结点。template struct Edge /边结点的定义 in dest; /边的另一顶点位置 E cost; /边上的权值 Edge *link; /下一条边链指针 Edge() /构造函数 Edge

23、(int num, E weight):dest(num), cost(weight), link(NULL) /构造函数 bool perator!=(Edge&R)const /判边不等否 return(dest!=R.dest) ? true : false; ; 邻接表表示的图的类定义template struct Vertex /顶点的定义 T data; /顶点的名字 Edge *adj; /边链表的头指针;template class Graphlnk:public Graph /图的类定义friend istream& operatoristream&in,Graphlin&

24、G);friend ostream& operatorostream&out,Graphlin& G); /输入和输出public: Graphlnk (int sz=DefaultVertices); /构造函数 Graphlnk(); /析构函数 T getValue(int i) /取位置为i的顶点中的值 return(i=0&iNumVertices) ? NodeTablei.data : 0; E getWeight(int v1,int v2); /返回边(v1,v2)上的权值 bool insertVertex(const T& vertex); /插入一个顶点vertex b

25、ool removeVertex(int v); /在图中删除一个顶点v bool insertEdge(int v); /在图中插入一条边(v1,v2) bool removeEdge(int v1,int v2); /在图中删除一条边(v1,v2) int getFirstNeighbor(int v); /取顶点v的第一个邻接顶点 int getNextNeighbor(int v,int w); /取v的邻接顶点w的下一邻接顶点private: Vertex *NodeTable; /顶点表（各边链表的头结点） int getVertexPos(const T vertex) /给出顶

26、点vertex在图中的位置 for (int i=0; inumVertices; i+) if (NodeTablei.data=Vertex) return i; return -1; ; 网络(带权图)的邻接表template Graphlnk:Graphlnk(int sz)/构造函数：建立一个空的邻接表 maxVertices=sz; numVertices=0; numEdges=0; NodeTable=new VertexmaxVertices; /创建顶点表数组 if (NodeTable=NULL) cerr存储分配错！endl;exit(1); for (int i=0;

27、 imaxVertices; i+) NodeTablei.adj=NULL; 邻接表的构造函数和析构函数template Graphlnk:Graphlnk()/析构函数:删除一个邻接表 for (int i=0; inumVertices; i+) /删除各边链表的结点 Edge *p=NodeTablei.adj; /找到其对应边链表的首结点 while (p!=NULL) /不断删除第一个结点 NodeTablei.adj=p-link; delete p; p=NodeTablei.adj; delete NodeTable; /删除顶点表数组;template int Graphl

28、nk:getFirstNeighbor(int v)/给出顶点位置为v的第一个邻接顶点的位置，如果 找不到，则函数返回-1. if (v!=-1) /顶点v存在 Edge *p=NodeTablev.adj; /对应边链表第一个边结点 if (p!=NULL) return P-data; /存在，返回第一个邻接顶点 return -1; /第一个邻接顶点不存在;邻接表部分成员函数的实现（找第一个邻接顶点）template int Graphlnk:getNextNeighbor(int v, int w)/给出顶点v的邻接顶点w的下一个邻接顶点的位置，若没有 下一个邻接顶点，则函数返回-1.

29、 if (v!=-1) /顶点v存在 Edge *p=NodeTablev.adj; /对应边链表第一个边结点 while (p!=NULL & p-dest!=w) /寻找邻接顶点w p=p-link; if (p!=NULL&p-link!=NULL) return p-link-dest; /返回下一个邻接顶点 return -1; /下一个邻接顶点不存在; 邻接表部分成员函数的实现（找下一个邻接顶点）template E Graphlnk:getWeight(int v1, int v2)/函数返回边(v1,v2)上的权值，若该边不在图中，则函数返回 权值0. if (v1!=-1&v

30、2!=-1) Edge *p=NodeTablev1.adj; /v1的第一条关联的边 while (p!=NULL&p-dest!=v2) /寻找邻接顶点v2 p=p-link; if (p!=NULL) return p-cost; /找到此边，返回权值 return 0; /边(v1,v2)不存在; 邻接表部分成员函数的实现（得到边上的权值）template bool Graphlnk:insetVertex(const T& vertex)/在图的顶点表中插入一个新顶点vertex。若插入成 功，函数返回TRUE，否则返回FALSE。 if (numVertices=maxVertic

31、es) return false; /顶点表满，不能插入 NodeTablenumVertices.data=vertex; /插入在表的最后 numVertices+; return true; 邻接表部分成员函数的实现（插入和删除顶点）template bool Graphlnk:removeVertex(int v)/在图中删除一个指定顶点v，v是顶点号。若删除成功，函 数返回TRUE，否则返回FALSE。 if (numVertices=1 | v=numVertices) return false; /表空或顶点号超出范围 Edge *p, *s, *t; int i, k; whi

32、le (NodeTablev.adj!=NULL) /删除第v个顶点的边链表 p=NodeTablev.adj; k=p-dest; /取邻接顶点k s=NodeTablek.adj; t=NULL; /找对称存放的边结点 while (s!=NULL&s-dest!=v) t=s; s=s-link; if (s!=NULL) /删除对称存放的边结点 if (t=NULL) NodeTablek.adj=s-link; else t-link=s-link; delete s; NodeTablev.adj=p-link; /清除顶点v的边链表结点 delete p; numEdges-;

33、/与顶点v相关联的边数减1 numVertices-; /图的顶点个数减1 NodeTablev.data=NodeTablenumVertices.data; /填补 p=NodeTablev.adj=NodeTablenumVertices.adj; while (p!=NULL) s=NodeTablep-dest.adj; while (s!=NULL) if (s-dest=numVertices) s-dest=v; break; else s=s-link; return true; template bool Graphlnk:insertEdge(int v1, int v2

34、, E weight)/在带权图中插入一条边(v1,v2)，若此边存在或参数不合理， 函数返回FALSE，否则返回TRUE。对于非带权图，最后一 个参数weight不要。算法中相应语句也不要。 if (v1=0&v1=0&v2numVertices) Edge *q,*p=NodeTablev1.adj; /v1对应的边链表头指针 while(p!=NULL&p-dest!=v2) /寻找邻接顶点v2 p=p-link; if (p!=NULL) return false; /找到此边，不插入 p=new Edge; q=new Edge; /否则创建新结点 p-dest=v2; p-cost

35、=weight; p-link=NodeTablev1.adj; /链入v1边链表 NodeTablev1.adj=p;邻接表部分成员函数的实现（插入一条边） q-dest=v1;q-cost=weight; q-link=NodeTablev2.adj; /链入v2边链表 NodeTablev2.adj=q; numEdges+; return true; return 0;template bool Graphlnk:removetEdge(int v1,int v2)/在图中删除一条边(v1,v2) if (v1!=-1&v2!=-1) Edge *p=NodeTablev1.adj,*

36、q=NULL,*s=p; while(p!=NULL&p-dest!=v2) /v1对应边链表中找被删边 q=p; p=p-link; if (p!=NULL) /找到被删边结点 if (p=s) NodeTablev1.adj=p-link; /该结点是边链表首结点 else q-link=p-link; /不是，重新链接 delete p; else return false; /没有找到被删边结点邻接表部分成员函数的实现（删除一条边） p=NodeTablev2.adj; q=NULL, s=p; /v2对应边链表中删除 while (p-dest!=v1) q=p; p=p-link;

37、 /寻找被删边结点 if (p=s) NodeTablev2.adj=p-link; /该结点是边链表首结点 else q-link=p-link; /不是，重新链接 delete p; return true; /没有找到结点 return false; 邻接多重表 (Adjacency Multilist)在邻接多重表中，每一条边只有一个边结点，为有关边的处理提供了方便。无向图的情形边结点的结构 mark vertex1 vertex2 path1 path2其中，mark 是记录是否处理过的标记；vertex1和vertex2是依附于该边的两顶点位置。path1域是链接指针，指向下一条依

38、附于顶点vertex1的边；path2也是链接指针，指向下一条依附于顶点vertex2的边。需要时还可设置一个存放与该边相关的权值的域 cost。顶点的结构存储顶点信息的结点表以顺序表方式组织，每一个顶点结点有两个数据成员：其中，data 存放与该顶点相关的信息，Firstout 是指示第一条依附于该顶点的边的指针。在邻接多重表中, 所有依附于同一个顶点的边都链接在同一个单链表中。从顶点 i 出发, 可以循链找到所有依附于该顶点的边，也可以找到它的所有邻接顶点。邻接多重表的结构 data Firstout有向图的情形在用邻接表表示有向图时，有时需要同时使用邻接表和逆邻接表。用有向图的邻接多重表

39、(十字链表)可把这两个表结合起来表示。 邻接多重表的结构边结点的结构其中，mark是处理标记；vertex1和vertex2指明该有向边始顶点和终顶点的位置。path1是指向始顶点与该边相同的下一条边的指针；path2是指向终顶点与该边相同的下一条边的指针。需要时还可有权值域cost。 mark vertex1 vertex2 path1 path2顶点的结构每个顶点有一个结点，它相当于出边表和入边表的表头结点：其中，数据成员data存放与该顶点相关的信息，指针Firstin指示以该顶点为始顶点的入边表的第一条边，Firstout指示以该顶点为终顶点的出边表的第一条边。 data Firsti

40、n Firstout邻接多重表的结构对于一个具有n个顶点e条边的图G，邻接表表示的空间复杂度为O(n+e)。若图中边的数目远远小于n2(即en2)（稀疏图Sparse Graph），邻接表表示比用邻接矩阵表示节省存储空间。若e接近于n2 (稠密图 Dense Graph)，考虑到邻接表中要附加链域，则应取邻接矩阵表示法为宜。 两种主要存储结构的比较分析空间复杂度在无向图中求顶点的度：邻接矩阵中第i行(或第i列)上非零元素的个数即为顶点vi的度；在邻接表表示中，顶点vi的度则是第i个边表中的结点个数。在有向图中求顶点的度。采用邻接矩阵表示比邻接表表示更方便：邻接矩阵中的第i行上非零元素的个数是顶

41、点vi的出度OD(vi)，第i列上非零元素的个数是顶点vi的入度ID(vi)，顶点vi的度即是二者之和。在邻接表表示中，第i个边表(即出边表)上的结点个数是顶点vi的出度，求vi的入度较困难，需遍历各顶点的边表。若有向图采用逆邻接表表示，则与邻接表表示相反（此时可采用邻接多重表）。求顶点的度在邻接矩阵表示中，(vi，vj)或vi，vj是否是图的一条边，只要判定矩阵中的第i行第j列上的那个元素是否为零即可；在邻接表表示中，需扫描第i个边表，最坏情况下要耗费O(n)时间。边存在的判定在邻接矩阵中求边的数目e，必须检测整个矩阵，所耗费的时间是O(n2)，与e的大小无关；而在邻接表表示中，只要对每个边

42、表的结点个数计数即可求得e，所耗费的时间是O(e+n)。因此，当en2时，采用邻接表表示更节省时间。 边的数量操作邻接矩阵邻接表1求顶点的度遍历矩阵的一行（列）遍历边链表2找顶点遍历顶点数组遍历顶点数组3边存在的判定O(1)遍历边链表4求边的数量遍历整个矩阵遍历所有边链表5插入边O(1)边链表中插入结点操作邻接矩阵邻接表6删除边O(1)遍历边链表7插入顶点O(1)O(1)8删除顶点O(|V|)O(|E|)9找第一个邻接顶点遍历矩阵的一行遍历边链表10找下一个邻接顶点遍历矩阵的一行遍历边链表6.3 图的遍历从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫

43、做图的遍历( Graph Traversal )。图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组visited，它的初始状态为0，在图的遍历过程中，一旦某一个顶点i被访问，就立即让 visitedi为1，防止它被多次访问。深度优先搜索DFS ( Depth First Search )深度优先搜索的示例通过演示了解图的深度优先遍历过程DFS在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点w1；再从w1出发，访问与w1邻接但还没有访问过的顶点w2；然后再从w2

44、出发，进行类似的访问， 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。TemplateVoid DFS (Graph& G, const T& v)/从顶点出发，对图G进行深度优先遍历的主过程 int i，loc=G.NumberOfVertices()/取图中的顶点个数 Bool visited=new booln;/创建辅助数组 for (int i=0;

45、in; i+) Visitedi=false; loc=G.getVertexPos(v); DFS(G, loc, visited); Delete visited; 图的深度优先搜索算法TemplateVoid DFS(Graph&G, int v, bool visited)/子过程从顶点位置V出发，以深度优先的次序访问所有可读入的尚未访问过的顶点，算法中用到一个辅助数组visited,对已访问过的顶点作访问标记 CoutG.getValue(v)”;/访问顶点v Visitedv=true; /顶点v做访问标记 int w=G.getFirstNeighor(v); /找顶点v的第一个

46、邻接顶点w while (w!=-1) if (visitedw=false) DFS(G, w, visited); /若w未访问过，递归访问顶点w w=G.getNextNeighbor(v,w); ; 算法分析图中有n个顶点，e条边。如果用邻接表表示图，沿边链可以找到某个顶点v的所有邻接顶点w。由于总共有2e个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)。如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n2)。广度优先搜索BFS ( Breadth First Search

47、)广度优先搜索的示例 广度优先搜索过程 广度优先生成树通过演示了解图的广度优先遍历过程使用广度优先搜索在访问了起始顶点v之后，由v出发，依次访问v的各个未曾被访问过的邻接顶点w1, w2, , wt，然后再顺序访问w1, w2, , wt的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点， 如此做下去，直到图中所有顶点都被访问到为止。广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。为了实现逐层访问，算法中使用了一个队列，用来记忆正在访问的这一

48、层和上一层的顶点，以便于向下一层访问。与深度优先搜索过程一样，为避免重复访问，需要一个辅助数组visited，给被访问过的顶点加标记。TemplateVoid BFS(Graph&G, const T& v)/从顶点v出发，以广度优先的次序横向搜索图，算法中使用了 一个队列 int i, w, n=G.NumberOfVertices( ); /取图中的顶点个数 Bool * visited=new booln; /visited 顶点是否访问过 for (i=0; in; i+) visitedi=false; /初始化 int loc=G.getVertexPos(v); /取顶点号 Co

49、untG.getValue(loc);访问顶点v,做已访问标记 Visitedloc=true; Queue Q; Q.EnQueue(loc); /顶点进队列，实现分层访问 while (!Q.IsEmpty( ) /循环，访问所有顶点 Q.DeQueue(loc); /从队列中退出顶点loc w=G.getFirstNeighor(loc); /找顶点loc的第一个了邻接顶点w图的广度优先搜索算法 while (w!=-1) 若邻接顶点w存在 if（visitedw=false） CoutG.getValue(w); visitedw=true; Q.EnQueue(w);/顶点w进队列

50、w=G.getNextNeighbor(loc, w) /找顶点loc的下一个邻接顶点 Delete visited; 算法分析如果使用邻接表表示图，则循环的总时间代价为 d0 + d1 + + dn-1 = O(e)，其中的 di 是顶点 i 的度。所有顶点均进出队列1次，所以总的时间代价是O(n+e)。如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的 n 个元素，总的时间代价为O(n2)。例图中给出了7个顶点组成的无向图，从顶点1出发，对它进行深度优先遍历得到的的顶点序列是（1），而进行广度优先遍历得到的顶点序列是（2）。1345267(1) 1354267 1347625

51、 1534276 1247653 以上都错 (2) 1534267 1726453 1354276 1247653 以上都错 （1）1534276 （2）1354276例画出图中给出的无向图的邻接表表示，使得其中无向边结点表中第一个顶点号小于第二个顶点号，同时请列出从顶点1开始的深度优先和广度优先遍历所得到的顶点序列和边序列。154623154623V1V2V3V4V5V62356134124623561461345154623深度优先遍历：1，2，3，4，5，6(1，2) (2，3) (3，4) (4，5) (5，6)广度优先遍历1，2，3，5，6，4(1，2) (1，3) (1，5) (1

52、，6) (2，4)V6V5V4V3V2V12356134124623561461345连通分量 (Connected component)当无向图为非连通图时，从图中某一顶点出发，利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点，只能访问到该顶点所在的最大连通子图(连通分量)的所有顶点。若从无向图的每一个连通分量中的一个顶点出发进行遍历，可求得无向图的所有连通分量。在算法中，需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量。对于非连通的无向图，所有连通分量的生成树组成了非连通图的生

53、成森林。Templatevoid Components(Graph&G)/通过DFS,找出无向图的所有连通分量 int i，n=G.NumberOfVertices();/取图中顶点个数 bool * visited=new booln;/visited 记录顶点是否访问过 for (int i=0;in;i+) visitedi=false; /初始化，表示所有顶点未访问过 for(i=0;in;i+) /顺序扫描所有顶点 for(i=0;in;i+) . if（visitedi=false） /若没有访问过，则访问这个连通分量 DFS(G, i ,visited);/未访问，出发访问 po

54、net() /输出这个连通分量 Delete visited; 确定连通分量的算法重连通分量 (Biconnected Component)在无向连通图G中，当且仅当删去G中的顶点v及所有依附于v的所有边后，可将图分割成两个或两个以上的连通分量，则称顶点v为关节点。1,3,5,7是关节点安全的通信网络应该是重连通的没有关节点的连通图叫做重连通图。在重连通图上, 任何一对顶点之间至少存在有两条路径, 在删去某个顶点及与该顶点相关联的边时, 也不破坏图的连通性。一个连通图G如果不是重连通图，那么它可以包括几个重连通分量。在一个无向连通图G中, 重连通分量可以利用深度优先生成树找到。 当且仅当u在生

55、成树中是v的祖先，或者v是u的祖先时，非生成树的边(u,v)就是一条回边（用虚线表示，如(3,1)(5,7)）。不是回边的非生成树的边叫做交叉边。dfn 顶点的深度优先数，标明进行深度优先搜索时各顶点访问的次序。如果在深度优先生成树中，顶点u是顶点v的祖先, 则有dfnu dfnv。深度优先生成树的根是关节点的充要条件是它至少有两个子女。其它顶点u是关节点的充要条件是它至少有一个子女 w, 从w出发,不能通过w、w的子孙及一条回边所组成的路径到达u的祖先。在图G的每一个顶点上定义一个low值，lowu 是从 u或u的子孙出发通过回边可以到达的最低深度优先数。u是关节点的充要条件是： u是具有两

56、个以上子女的生成树的根 u不是根，但它有一个子女w，使得 loww dfnu这时w及其子孙不存在指向顶点u的祖先的回边。lowu = min dfnu, min loww | w 是 u 的一个子女 , min dfnx | (u, x) 是一条回边 void Graph:DfnLow ( const int x ) /公有函数：从顶点x开始深度优先搜索 int num = 1; / num是访问计数器 dfn = new intNumVertices; low = new intNumVertices; /dfn是深度优先数, low是最小祖先访问顺序号 for ( int i = 0; i

57、 NumVertices; i+ ) dfni = lowi = 0; /给予访问计数器num及dfnu, lowu初值 DfnLow ( x, -1 ); /从根x开始 delete dfn; delete low;计算dfn与low的算法 (1)void Graph:DfnLow ( const int u, const int v ) /私有函数：从顶点u开始深度优先搜索计算dfn/ 和low。在产生的生成树中v是u的双亲。 dfnu = lowu = num+; int w = GetFirstNeighbor (u); while ( w != -1 ) /对u所有邻接顶点w循环 i

58、f ( dfnw = 0 ) /未访问过, w是u的孩子 DfnLow ( w, u ); /从w递归深度优先搜索 lowu = min2 ( lowu, loww ); /子女w的loww先求出, 再求lowu 计算dfn与low的算法 (2)else if ( w != v ) /w访问过且w不是v，是回边 lowu = min2 ( lowu, dfnw ); /根据回边另一顶点w调整lowu w = GetNextNeighbor (u, w); /找顶点u在w后面的下一个邻接顶点 在算法DfnLow增加一些语句, 可把连通图的边划分到各重连通分量中。首先, 根据 DfnLow (w,

59、 u)的返回, 计算loww。如果loww dfnu，则开始计算新的重连通分量。在算法中利用一个栈， 在遇到一条边时保存它。可在函数Biconnected中就能输出一个重连通分量的所有的边。void Graph:Biconnected ( ) /公有函数：从顶点0开始深度优先搜索 int num = 1; /访问计数器num dfn = new intNumVertices; /dfn是深度优先数 low = new intNumVertices; /low是最小祖先号 for ( int i = 0; i 1 时输出重连通分量（1）void Graph:Biconnected ( const

60、 int u, const int v ) /私有函数：计算dfn与low, 根据其重连通分量输/出Graph的边。在产生的生成树中, v 是 u 的双亲/结点, S 是一个初始为空的栈，应声明为图的数/据成员。 int x, y, w; dfnu = lowu = num+; w = GetFirstNeighbor (u); /找顶点u的第一个邻接顶点w while ( w != - 1 ) if ( v != w & dfnw 1 时输出重连通分量（2） if ( dfnw = 0 ) /未访问过, w是u的孩子 Biconnected (w, u); /从w递归深度优先访问 lowu