图图类－遍历－应用

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,LOGO,LOGO,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,Chapter12,图,2024/9/21,1,12.1,图的基本概念和基本术语,12.2,图的应用示例,12.4 抽象数据类型Graph和Diagraph,12.5 无向图,、有向图及网络的描述,12.7,图的类定义,12.8 图的遍历,12.10 图的搜索算法,12.11,图的应用,内容提要,2,12.7,类定义,无权有向图和无向图可以看作每条边的权是,1,的加权有向图和无向图。,无向图可以看作：,可以看作边,(,i,j,),和边,(,j,i,),都存在的有向图；,也可以看作所有边的权均为,1,的加权图；,或者看作所有边的权为,1,，若边,(,i,j,),存在，则边,(,j,i,),也存在的加权有向图。,3,邻接矩阵,描述的图类关系,AdjacencyWDigraph,AdjacencyWGraph,AdjacencyDigraph,AdjacencyGraph,AdjacencyWDigraph,（加权有向图的耗费邻接矩阵）,AdjacencyWGraph,（加权图）,AdjacencyDigraph,（有向图）,AdjacencyGraph,（无向图）,4,12.7.2,邻接矩阵类,加权有向图的耗费邻接矩阵（程序,12-1,）,template,class,AdjacencyWDigraph,friend AdjacencyWGraph;,public:,AdjacencyWDigraph (int Vertices = 10, T noEdge = 0);,AdjacencyWDigraph() Delete2DArray(a,n+1); ,bool Exist(int i, int j) const;,int Edges( ) const return e; ,int Vertices( ) const return n; ,AdjacencyWDigraph,5,AdjacencyWDigraph,int OutDegree(int i) const;,int InDegree(int i) const;,private :,T NoEdge; /,用于没有边存在的情形,int n; /,顶点数目,int e; /,边数,T *a; /,二维数组, ;,6,AdjacencyWDigraph,构造函数,templateAdjacencyWDigraph:,AdjacencyWDigraph,(int Vertices, T noEdge), /,构造函数,n = Vertices;,e = 0;,NoEdge = noEdge;,Make2DArray(a, n+1, n+1);,/,初始化为没有边的图,for (int i = 1; i = n; i+),for (int j = 1; j n | aij = NoEdge),return false;,return true;,函数,Exist,的代码不能区分下面两种情况：,i,或,j,是否为有效顶点；,边,(i, j),是否存在。,8,添加边,: Add,templateAdjacencyWDigraph&,AdjacencyWDigraph :,Add,(int i, int j, const T& w), /,如果边,(i,j),不存在，则将该边加入有向图中,if (i n | j n | i = j | aij != NoEdge),throw BadInput();,aij = w;,e+;,return *this;,(1 ),9,删除边,: Delete,template AdjacencyWDigraph&,AdjacencyWDigraph :,Delete,(int i, int j), /,删除边,( i , j ) .,if (i n | j n | aij = NoEdge),throw BadInput();,aij = NoEdge;,e- ;,return *this;,( 1 ),10,求顶点出度,: OutDegree,template,int AdjacencyWDigraph:,OutDegree,(int i) const,/,返回顶点,i,的出度,if (i n) throw BadInput();,/,计算顶点,i,的出度,int sum = 0;,for (int j = 1; j = n; j+),if (,aij,!= NoEdge) sum+;,return sum;,( n ),遍历第,i,行中,有效边的条数,11,求顶点入度,: InDegree,template,int AdjacencyWDigraph:,InDegree,(int i) const,/,返回顶点,i,的入度,if (i n) throw BadInput();,/,计算顶点,i,的入度,int sum = 0;,for (int j = 1; j = n; j+),if (,aji,!= NoEdge) sum+;,return sum;,( n),遍历第,i,列中,有效边的条数,12,无向加权图的定义（程序,12-2,）,template,class,AdjacencyWGraph,: public AdjacencyWDigraph,public :,AdjacencyWGraph(int Vertices = 10, T noEdge = 0) :,AdjacencyWDigraph(Vertices, noEdge), ,AdjacencyWGraph& Add(int i, int j, const T& w),AdjacencyWDigraph :,Add(i,j,w),;,aji=w,;,return *this;,AdjacencyWGraph& Delete(int i, int j),AdjacencyWDigraph :Delete(i , j) ;,aji = NoEdge,;,return *this;,int Degree(int i) const return,OutDegree(i);, ;,1,）无向图的邻接矩阵,是对称的,2,）派生类中如何解决,同名函数的屏蔽问题,13,无向图的定义（程序,12-4,）,class,AdjacencyGraph,: public AdjacencyWGraph,public :,AdjacencyGraph(int Vertices = 10) :,AdjacencyWGraph(Vertices,0,) ,AdjacencyGraph& Add(int i, int j),AdjacencyWGraph :Add (i, j, 1),;,return *this;,AdjacencyGraph& Delete(int i, int j),AdjacencyWGraph:Delete(i, j),;,return *this;, ;,14,有向图的定义（程序,12-3,）,class,AdjacencyDigraph,: public AdjacencyWDigraph,public :,AdjacencyDigraph(int Vertices = 10) :,AdjacencyWDigraph(Vertices, 0) ,AdjacencyDigraph& Add(int i, int j),AdjacencyWDigraph:,Add(i, j,1),;,return *this;,AdjacencyDigraph& Delete(int i, int j),AdjacencyWDigraph:Delete(i, j) ;,return *this;, ;,15,template,Chain& Chain:Delete(T& x),/,删除与,x,匹配的元素,/,如果不存在相匹配的元素，则引发异常,BadInput,ChainNode *current = first,*trail = 0; /,指向,current,之前的节点,/,搜索匹配元素,while (current & current-data != x),trail = current;,current = current-link;,12.7.3,扩充,Chain,类,-,删除元素,16,删除元素（续）,if (!current) throw BadInput( ); /,不存在匹配元素,/,在节点,current,中找到匹配元素,x = current-data; /,保存匹配元素,/,从链表中删除,current,节点,if (trail),trail-link = current-link;,else,first = current-link;,delete current; /,释放节点,return *this;,17,邻接表描述的图类关系,LinkedBase,LinkedDigraph,LinkedWDigraph,LinkedGraph,LinkedWGraph,LinkedDigraph,LinkedWDigraph,LinkedGraph,LinkedWGraph,链表节点的,结构不同,18,无权和加权图的派生路径之所以不同，其原因在于加权有向图和无向图的链表节点中有一个,权值域,，而无权有向图和无向图中则没有。,对于后者，使用,int,类型的链节点就足够了；而对于前者，链节点必须包含,一个权值域,和,一个顶点域,。尽管节点结构存在这种差别，但某些基本函数的代码仍然是一样的。,因此，引入一个新类,LinkedBase,，它包含了构造函数、析构函数、,Edges,和,OutDegree,函数。,12.7.4,类,LinkedBase,19,邻接链描述的基类（程序,12-6,）,template class LinkedBase,友元类,public:,LinkedBase(int Vertices = 10),n = Vertices ;,e = 0;,h = new Chain n+1; ,LinkedBase( ) delete h; ,int Edges( ) const return e; ,int Vertices( ) const return n; ,int,OutDegree(int i),const,if (i n) throw OutOfBounds();,return,hi.Length();,private:,int n; /,顶点数,int e; /,边数,Chain *h; /,边节点链表表头指针数组, ;,20,1,2,3,h,1,2,3,2,1,3,data,link,data,link,int,OutDegree,(int i) const,if (i n) throw OutOfBounds();,return,hi.Length(),;,某个节点的出度：统计第,i,行链表中结点的个数,( d,i,out,),21,12.7.5,链接类,有向图的邻接链表（程序,12-7,）,class,LinkedDigraph,: public LinkedBase,public:,LinkedDigraph(int Vertices = 10) : LinkedBase (Vertices) ,bool Exist(int i, int j) const;,LinkedDigraph,LinkedDigraph,int InDegree(int i) const;,protected :,LinkedDigraph, ;,22,判断边,( i, j ),是否存在,bool LinkedDigraph:Exist(int i, int j) const,/,边,( i , j ),存在吗,?,if (i n) throw OutOfBounds( );,return (hi.Search(j) ? true : false;,1,2,3,h,1,2,3,2,1,3,data,link,data,link,( d,i,out,),23,把边,(i, j),加入到图中,LinkedDigraph& LinkedDigraph:Add(int i, int j), /,把边,(i,j),加入到图中,if (i n | j n | i = j |,Exist,(i, j),throw BadInput();,return AddNoCheck(i, j);,LinkedDigraph& LinkedDigraph:,AddNoCheck(int i, int j), /,增加边但不检查可能出现的错误,hi.Insert(0,j);,/,把,j,添加到顶点,i,的表中,e+;,return *this;,( d,i,out,),24,删除边,( i , j ),LinkedDigraph& LinkedDigraph:Delete(int i, int j), /,删除边,( i , j ),if (i n) throw OutOfBounds();,hi.Delete( j ) ; /,找到并删除节点,e-;,return *this;,1,2,3,h,1,2,3,2,1,3,data,link,O,(e),25,返回顶点,i,的入度,int LinkedDigraph:InDegree(int i) const, /,返回顶点,i,的入度,if (i n) throw OutOfBounds();,/,计算到达顶点,i,的边,int sum = 0;,for (int j = 1; j n | i =j | Exist(i, j),throw BadInput();,return AddNoCheck(i, j);,( d,i,out,),28,添加边,(i, j),不检查可能出现的错误,LinkedGraph& LinkedGraph:AddNoCheck(int i, int j),/,添加边,(i,j),不检查可能出现的错误,hi.Insert (0, j),;,try ,hj.Insert(0,i),; ,对称加入！,/,若出现异常,则取消第一次插入，并引发同样的异常,catch (.) hi.Delete(j); throw; ,e+;,return *this;,1,4,2,3,h,1,2,3,4,2,4,1,3,2,1,data,link,data,link,29,删除边,( i , j ),LinkedGraph& LinkedGraph:Delete(int i, int j), /,删除边,( i , j ),LinkedDigraph:Delete( i , j ) ;,对称删除,(,隐含,e-),e+;,/,补偿，边只需减少一条！,LinkedDigraph:Delete( j , i ) ;,return *this;,1,4,2,3,h,1,2,3,4,2,4,1,3,2,1,data,link,data,link,30,GraphNode,类,template class GraphNode,friend LinkedWDigraph;,friend LinkedWGraph;,friend Chain;,public :,int operator,!=,(GraphNode y) const, return ( vertex != y.vertex ) ; ,void Output(ostream& out) const, out vertex weight ,public :,LinkedWDigraph(int Vertices = 10) : LinkedBase (Vertices) ,bool Exist(int i, int j) const;,LinkedWDigraph& Add(int i, int j,const T& w,);,LinkedWDigraph,int InDegree(int i) const;,protected :,LinkedWDigraph &,AddNoCheck(int i, int j, const T, ;,32,是否存在边,(i, j),template,bool LinkedWDigraph:Exist(int i, int j) const, /,存在边,(i,j),吗,?,if (i n) throw OutOfBounds();,GraphNode x;,x.vertex = j;,return hi.Search(x);,vertex,weight,link,加权图边节点结构,GraphNode,( d,i,out,),33,添加边,( i , j ),templateLinkedWDigraph&,LinkedWDigraph :Add(int i, int j, const T& w), /,添加边,( i , j ),if (i n | j n | i = j| Exist(i, j),throw BadInput();,return AddNoCheck(i, j, w);,( d,i,out,),34,添加边,( i , j ),，不检查可能出现的错误,template LinkedWDigraph&,LinkedWDigraph :AddNoCheck(int i, int j, const T& w), /,添加边,( i , j ),，不检查可能出现的错误,GraphNode x;,x.vertex = j;,x.weight = w;,h i .Insert (0 , x ) ;,e+ ;,return *this;,35,删除边,( i , j ),templateLinkedWDigraph& LinkedWDigraph :Delete(int i, int j), /,删除边,( i , j ),if (i n) throw OutOfBounds();,GraphNode x;,x.vertex = j;,h i . Delete (x) ;,e - - ;,return *this;,O,(e),36,返回顶点,i,的入度,template,int LinkedWDigraph:InDegree(int i) const,/,返回顶点,i,的入度,if (i n) throw OutOfBounds( );,int sum = 0;,GraphNode x;,x.vertex = i;,/,检查所有的,( j , i ),for (int j = 1; j = n; j+),if (hj.Search(x) sum+;,return sum;,O,(ne),37,图的遍历定义：从图中,某一顶点出发,，按照一定规则，通过边或弧对图中,所有顶点访问一次且只访问一次,。,图的遍历比树的遍历复杂，主要表现在以下方面：,（,1,）,出发点的选取,与,图的连通性,；,（,2,）,回路,的判断及处理：,（,3,）,下一个要访问的顶点,的选取。,设置一个访问的标记数组,reachn,，初值为,0,，一旦访问了某顶点,vi,，便置,reachi,为,1,或被访问时的序号。,12.8,图的遍历,38,几个主要操作：使用遍历器,Begin(i),：返回,第一个,与顶点,i,邻接的顶点。,对于邻接表，返回顶点,i,所对应表中的第一个顶点；,对于邻接矩阵，返回邻接于顶点,i,的最小（即第一个）顶点。,在两种情况中，如果没有邻接顶点，都将返回零值。,NextVertex (i),：返回,下一个,与顶点,i,邻接的顶点。,即返回顶点,i,对应邻接表中的下一个顶点或返回邻接于顶点,i,的下一个最小顶点。,当没有下一个顶点时函数返回零。,1,4,2,3,G,1,0,1,1,1,1,0,1,1,1,1,0,0,1,1,0,0,A,39,几个主要操作,InitializePos(),：初始化用来跟踪每一个邻接表或,(,耗费,),邻接矩阵每一行中,当前位置,的存储配置。,DeactivatePos(),：释放,InitializePos( ),所产生的存储配置。,40,12.8.2,邻接矩阵的遍历函数,邻接矩阵的遍历函数可以作为,基类,AdjacencyWDigraph,的一个,public,函数来加以实现。,由于其他,3,种邻接类都是从这个类,派生,出来的，因此它们可以从,AdjacencyDigraph,类中继承该函数。,由于可能处在邻接矩阵不同行的不同位置，因此用一个数组,pos,来记录每一行中的位置，这个变量是,AdjacencyWDigraph,的私有成员，定义如下：,int *pos;,41,Pos,的初始化与释放,template,void AdjacencyWDigraph:InitializePos( ), pos = new int n+1; ,template,void AdjacencyWDigraph:DeactivatePos( ), delete pos; ,42,邻接矩阵中返回第一个与顶点,i,邻接的顶点,template,int AdjacencyWDigraph:Begin(int i), /,返回第一个与顶点,i,邻接的顶点,if (i n) throw OutOfBounds();,/,查找第一个邻接顶点,for (int j = 1; j = n; j+),if (aij != NoEdge) /,第,i,行第一个顶点,posi = j; return j;,posi = n + 1; /,没有邻接顶点,return 0;,43,邻接矩阵中返回下一个与顶点,i,邻接的顶点,template,int AdjacencyWDigraph:NextVertex(int i),/,返回下一个与顶点,i,邻接的顶点,if (i n) throw OutOfBounds();,/,寻找下一个邻接顶点,for (int,j = posi + 1,; j vertex : 0;,49,返回下一个与顶点,i,邻接的顶点,template,int LinkedWDigraph:NextVertex(int i), /,返回下一个与顶点,i,邻接的顶点,if (i n) throw OutOfBounds();,GraphNode *x = posi.Next();,return (x) ? x-vertex : 0;,50,后续程序类派生层次图：,P392,遍历器虚基类,无向图和网络类的基类,51,12.10,图的搜索算法,宽（广）度优先搜索（横向）：,BFS,深度优先搜索（纵向）：,DFS,52,（,1,）访问,指定的起始顶点,v,0,，然后依次访问,与,v,0,相邻接的所有顶点,w,1,，,w,2,，,，,w,k,；,（,2,）,按,w,1,，,w,2,，,，,w,k,的顺序,，依次访问它们每一个顶点的所有未被访问过的邻接点,设,w,1,未被访问过的邻接点为,w,11,，,w,12,，,，,w,1m,w,k,未被访问过的邻接点为,w,k1,，,w,k2,，,，,w,kn,（,3,）再按,w,11,，,w,12,，,，,w,1m,，,w,k1,，,w,k2,，,，,w,kn,的顺序，依次去访问它们的所有未被访问过的邻接点；,（,4,）依此类推，直到图中所有被访问过的顶点的邻接点都被访问过为止；,（,5,）如果此时图中还有未被访问过的顶点，则从其中一个未被访问过的顶点出发，重复（,1,）,-,（,5,）直到图中所有顶点都被访问过为止。,图的宽（广）度优先搜索,（,Breadth First Search,，,BFS,）,53,宽度优先搜索（,BFS,）示例,判断从顶点,1,出发可到达的所有顶点的一种方法是首先确定邻接于顶点,1,的顶点集合，这个集合是, 2 , 3 , 4 ,。,然后确定邻接于, 2 , 3 , 4 ,的新的顶点集合，这个集合是, 5 , 6 , 7 ,。邻接于, 5 , 6 , 7 ,的顶点集合为, 8 , 9 ,，而不存在邻接于, 8 , 9 ,的顶点。,因此从顶点,1,出发可到达的顶点集合为, 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ,。,54,V,1,V,2,V,3,V,7,V,6,V,5,V,4,V,8,宽度优先搜索遍历的结果序列为：,V,8,V,1,V,2,V,3,V,4,V,5,V,6,V,7,先访问的顶点其邻接点先被访问,队列。,宽度优先搜索,示例,55,为了实现逐层访问，算法中使用了一个,队列,，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。,为避免重复访问，需要一个辅助数组,reach, ,，给被访问过的顶点加标记。,广度优先搜索是一种,分层,的搜索过程，每向前走一步可能访问一批顶点，类似于,树的层次遍历,。,BFS,算法思想,56,宽度优先搜索（,BFS,）,伪码算法,57,void Network:BFS(int v, int reach, int label), /,宽度优先搜索,LinkedQueue Q;,InitializePos( ); /,初始化图遍历器数组,reachv = label;,Q . Add ( v ) ;,while (!Q.IsEmpty( ) ,int w;,Q.Delete(w); /,获取一个已标记的顶点,int u = Begin(w);,while (u) /,访问,w,的邻接顶点,if (!reachu) /,一个未曾到达的顶点,Q.Add ( u ) ;,reachu = label; /,标记已到达该顶点,u = NextVertex(w); /,下一个与,w,邻接的顶点,DeactivatePos( ); /,释放遍历器数组,58,邻接矩阵描述中,B F S,的直接实现,template,void AdjacencyWDigraph:BFS (int v, int reach, int label), /,宽度优先搜索,LinkedQueue Q;,reachv = label;,Q . Add ( v ) ;,while (!Q.IsEmpty() ,int w;,Q.Delete(w); /,获取一个已标记的顶点,/,对尚未标记的、邻接自,w,的顶点进行标记,for (int u = 1; u link) ,int u = p-data;,if (!reachu) /,一个尚未到达的顶点,Q . Add ( u ) ;,reachu = label; ,60,BFS,算法分析,【,注意,】,只有当选取的,出发点,、采用的,存储结构,以及,遍历方式,都确定时遍历，遍历的结果才是唯一的。,61,（,1,）首先访问,指定的起始顶点,v,0,，,再访问,与,v,0,邻接的任一未访问过的顶点,w,1,；,（,2,）从,w,1,出发，访问,与,w,1,邻接的任一未访问过的顶点,w,2,；,（,3,）从,w,2,出发，重复与（,2,）类似的访问，,直到遇到一个所有邻接点都被访问过的顶点为止,；,（,4,）依次,回退到尚有邻接点未被访问过的顶点,，重复与（,3,）类似的访问，直到图中,所有和,v0,有路径相通的顶点都被访问过,；,（,5,）如果图中,存在未被访问过的顶点,，从其中一个未被访问过的顶点出发，重复（,1,）,-,（,5,），直至图中所有顶点都被访问完。,图的深度优先搜索,（,Depth First Search,，,DFS,）,62,（,1,）从指定顶点,v,0,出发，,访问该顶点,v,0,；,（,2,）从,v,0,的一个未被访问过的邻接点出发,，进行深度优先搜索，直到图中与,v,0,有路径相通的顶点都被访问过；,（,3,）若图中还存在未被访问过的顶点，则从其中一个未被访问的顶点出发，重复（,1,）,-,（,3,），直至图中所有顶点都被访问过为止。,图的深度优先搜索类似于,树的先根遍历,。,深度优先搜索,（DFS,）递归算法思想,63,V,1,V,2,V,3,V,7,V,6,V,5,V,4,V,8,深度优先搜索遍历的结果序列为：,V,7,V,1,V,2,V,4,V,8,V,5,V,6,V,3,后访问的顶点其邻接点先被访问,栈。,深度优先搜索示例,64,深度优先搜索算法,DFS,void Network:DFS(int v, int reach, int label), /,深度优先搜索,InitializePos( ); /,初始化图遍历器数组,dfs ( v, reach, label); /,执行,d f s,DeactivatePos( ); /,释放图遍历器数组,65,实际执行深度优先搜索的代码,dfs,void Network:dfs(int v, int reach, int label), /,实际执行深度优先搜索的代码,reachv = label;,int u = Begin(v);,while (u), / u,邻接至,v,if (!reachu),dfs(u, reach, label),;,u = NextVertex ( v ) ;,66,设置一个栈结构，,在遍历时，每访问一个顶点,w,，就将,w,压入栈中，然后访问,w,的一个未被访问的邻接顶点,如果在遍历过程中某顶点的所有邻接顶点都已被访问过，就从栈顶删去该顶点，,然后继续访问当前栈顶元素的一个未被访问过的邻接顶点，当栈为空时，遍历操作结束。,思考：,DFS,的非递归算法,67,能使,DFS,和,BFS,产生最好和最坏性能的图例,68,选择题：如图所示，给出由,7,个顶点组成的无向图。从顶点,1,出发，对它进行,深度优先遍历,得到的顶点序列是,（,1,）,；而进行,宽度优先遍历,得到的序列是,（,2,）,。,（,1,）,A. 1354267,（,2,）,A. 1534267,B. 1347625 B. 1726453,C. 1534276 C. 1354276,D. 1247653 D. 1247653,1,2,3,4,7,5,6,课堂练习,69,寻找路径,连通图及连通分量,生成树,12.11,应用,70,12.11.1,寻找路径,若从顶点,v,开始搜索（宽度或深度优先）且到达顶点,w,时终止搜索，则可以找到一条从顶点,v,到达顶点,w,的路径。,要实际构造这条路径，需要记住从一个顶点到下一个顶点的边。,对于路径问题，所需要的边的集合已隐含在深度优先的递归过程中，因此可以很容易地,利用深度优先策略,设计一个寻找路径程序。完成顶点,w,的标记之后展开递归，可以反向建立起从,w,到,v,的路径。,71,FindPath,的代码如程序,12 - 21,。这个程序要求把,Vertices( ),定义为,Network,的一个虚拟成员。,findPath,的输入参数是路径的开始顶点,( v ),和目标顶点,( w ),。如果没有从,v,到,w,的路径，,findPath,返回,false,；否则返回,true,。当找到路径时，用参数,length,返回路径长度（路径中边的条数），用顶点数组,p 0,：,length,返回路径，其中,p0=v,且,p length = w,。,findPath,首先检验,v=w,情况。在这种情况下，返回一个长度为,0,的路径。如果,vw,，则调用图的遍历函数,InitializePos,，然后,FindPath,产生并初始化一个数组,reach,，路径的,DFS,实际上是由,Network,的私有成员,findPath,完成的，当且仅当没有路径时，,findPath,返回,false,。,72,函数,findPath,是一个修改过的,DFS,，它对标准的,DFS,作了如下两点修改：,1),一旦到达了目标顶点,w,，,findPath,将不再继续搜索可到达顶点；,2) findpath,将开始顶点,v,到当前顶点,u,路径中的顶点记录到数组,path,中。,findPath,与,DFS,具有相同的复杂性。,73,bool Network:FindPath (int v, int w, int &length, int path),/,寻找一条从,v,到,w,的路径,返回路径的长度，并将路径存入数组,p a t h 0 : l e n g t h ,/,如果不存在路径，则返回,false,/,路径中的第一个顶点总是,v,path0 = v;,length = 0; /,当前路径的长度,if (v = w) return true;,/,为路径的递归搜索进行初始化,int n = Vertices ( ) ;,InitializePos( ); /,遍历器,int *reach = new int n+1;,for (int i = 1; i = n; i+) reachi = 0;,/,搜索路径,bool x =,findPath,(v, w, length, path, reach);,DeactivatePos ( ) ;,delete reach;,return x;,74,bool Network:findPath(int v, int w, int &length, int path, int reach),/,实际搜索,v,到,w,的路径，其中,v != w.,/,按深度优先方式搜索一条到达,w,的路径,reachv = 1;,int u = Begin(v);,while (u) ,if (!reachu) ,length+;,pathlength = u; /,将,u,加入,path,if (u = w),return true,;,if (findPath(u, w, length, path, reach),return true,;,/,不存在从,u,到,w,的路径,length-; /,删除,u,u = NextVertex(v) ;,return false; ,75,12.11.2,连通图及连通分量,通过从任意顶点开始执行,DFS,或,BFS,，并且检验所有顶点是否被标记为已到达顶点，可以,判断一个无向图,G,是否连通,。,假设,i,是搜索的开始顶点并且搜索到达了图中的所有顶点，利用,i,到,u,的反向路径及,i,到,v,的路径，可以构造任意两个顶点,u,和,v,之间的路径。如果图不连通，则函数,Connected,返回,false,，否则返回,true,。,由于,连通,的概念仅针对,无向图和网络,而言，因此，可以定义一个新类,Undirected,，函数,Connected,是,Undirected,的一个成员。,76,确定无向图是否连通,class Undirected : virtual public Network ,public :,bool Connected();, ;,bool Undirected:Connected(), /,当且仅当图是连通的，则返回,true,int n = Vertices( ) ;,/,置所有顶点为未到达顶点,int *reach = new int n+1;,for (int i = 1; i = n; i+),reachi = 0;,/,对从顶点,1,出发可到达的顶点进行标记,DFS(1, reach, 1);,/,检查是否所有顶点都已经被标记,for (int i = 1; i = n; i+),if (!reachi) return false;,return true; ,77,当无向图为,非连通图,时，从图中某一顶点出发，一次调用深度优先搜索算法或广度优先搜索算法不可能访问到图中的所有顶点，只能访问到该顶点所在的,最大连通子图,（连通分量）的所有顶点。,若从无向图的每一个连通分量中的一个顶点出发进行遍历，可求得无向图的所有连通分量。,在实际求连通分量的算法中，需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量。,非连通图有几个连通分量，就要几次调用,DFS,或,BFS,才能访问图中所有的顶点。,连通分量,(Connected component),78,int Undirected:LabelComponents(int L), /,构件标识,/,返回构件的数目， 并用,L 1 : n ,表示构件标号,int n = Vertices( ) ;,/,初始时，所有顶点都不属于任何构件,for (int i = 1; i = n; i+),Li = 0;,int label = 0; /,最后一个构件的,ID,/,识别构件,for (int i = 1; i = n; i+),if (!Li) /,未到达的顶点,/,顶点,i,属于一个新的构件,label + +,;,BFS(i, L, label); /,标记新构件,return label;,79,已知,G(V,E),是一个无向连通图，,E(G),为图,G,的边集，则从图中任一顶点出发遍历图时，必定将,E(G),分成两个集合,T(G),和,B(G):,T(G),：遍历图,G,时所经过的边的集合；,B(G),：遍历图,G,时未经过的边的集合；,则,G=(V, T),称为,G,的一棵生成树。,12.11.3,生成树,在一个无向连通图或网络中执行,DFS,时，到达新顶点的边正好有,n - 1,条，这些边组成的子图也是一个生成树，用这种方法所得到的生成树叫作,深度优先生成树,（,depth-first spanning tree,）。,80,81,82,F,H,G,L,M,I,J,K,E,A,D,C,B,例,83,E,A,D,C,B,L,M,I,J,K,F,H,G,非连通图的,深度优先,生成森林,84,F,H,G,非连通图的,广度优先,生成森林