《图图类遍历应用》由会员分享，可在线阅读，更多相关《图图类遍历应用（87页珍藏版）》请在金锄头文库上搜索。
1、LOGOChapter12 图2024/7/282024/7/281LOGOn12.1 图的基本概念和基本术语图的基本概念和基本术语n12.2 图的应用示例图的应用示例n12.4 抽象数据类型抽象数据类型Graph和和Diagraphn12.5 无向图无向图、有向图及网络的描述、有向图及网络的描述n12.7 图的类定义图的类定义n12.8 图的遍历图的遍历n12.10 图的搜索算法图的搜索算法n12.11 图的应用图的应用内容提要内容提要2LOGO12.7 12.7 类定义类定义v无权有向图和无向图可以看作每条边的权是无权有向图和无向图可以看作每条边的权是无权有向图和无向图可以看作每条边的权是
2、无权有向图和无向图可以看作每条边的权是1 1的加的加的加的加权有向图和无向图。权有向图和无向图。权有向图和无向图。权有向图和无向图。v无向图可以看作：无向图可以看作：无向图可以看作：无向图可以看作：可以看作边可以看作边可以看作边可以看作边( (i i, , j j) ) 和边和边和边和边( (j j, ,i i) ) 都存在的有向图；都存在的有向图；都存在的有向图；都存在的有向图；也可以看作所有边的权均为也可以看作所有边的权均为也可以看作所有边的权均为也可以看作所有边的权均为1 1 的加权图；的加权图；的加权图；的加权图；或者看作所有边的权为或者看作所有边的权为或者看作所有边的权为或者看作所有
3、边的权为1 1，若边，若边，若边，若边( (i i, , j j) ) 存在，则边存在，则边存在，则边存在，则边( (j j, , i i) ) 也存在的加权有向图。也存在的加权有向图。也存在的加权有向图。也存在的加权有向图。3LOGO邻接矩阵邻接矩阵描述的图类关系描述的图类关系AdjacencyWDigraphAdjacencyWDigraphAdjacencyWGraphAdjacencyWGraphAdjacencyDigraphAdjacencyDigraphAdjacencyGraphAdjacencyGraph AdjacencyWDigraph AdjacencyWDigraph
4、（加权有向图（加权有向图（加权有向图（加权有向图的耗费邻接矩阵）的耗费邻接矩阵）的耗费邻接矩阵）的耗费邻接矩阵） AdjacencyWGraph AdjacencyWGraph（加权图）（加权图）（加权图）（加权图） AdjacencyDigraph AdjacencyDigraph（有向图）（有向图）（有向图）（有向图） AdjacencyGraph AdjacencyGraph（无向图）（无向图）（无向图）（无向图）4LOGO12.7.2 12.7.2 邻接矩阵类邻接矩阵类加权有向图的耗费邻接矩阵（程序加权有向图的耗费邻接矩阵（程序加权有向图的耗费邻接矩阵（程序加权有向图的耗费邻接矩阵（程
5、序12-112-112-112-1）templatetemplateclass class AdjacencyWDigraph AdjacencyWDigraph friend AdjacencyWGraph;friend AdjacencyWGraph;public:public:AdjacencyWDigraph (int Vertices = 10, T noEdge = 0);AdjacencyWDigraph (int Vertices = 10, T noEdge = 0);AdjacencyWDigraph() Delete2DArray(a,n+1); AdjacencyWDi
6、graph() Delete2DArray(a,n+1); bool Exist(int i, int j) const;bool Exist(int i, int j) const;int Edges( ) const return e; int Edges( ) const return e; int Vertices( ) const return n; int Vertices( ) const return n; AdjacencyWDigraph& Add (int i, int j, const T& w);AdjacencyWDigraph& Add (int i, int j
7、, const T& w);5LOGOAdjacencyWDigraph& Delete(int i, int j);AdjacencyWDigraph& Delete(int i, int j);int OutDegree(int i) const;int OutDegree(int i) const;int InDegree(int i) const;int InDegree(int i) const;private :private :T NoEdge; / T NoEdge; / 用于没有边存在的情形用于没有边存在的情形用于没有边存在的情形用于没有边存在的情形int n; / int
8、n; / 顶点数目顶点数目顶点数目顶点数目int e; / int e; / 边数边数边数边数T *a; / T *a; / 二维数组二维数组二维数组二维数组 ; ;6LOGOAdjacencyWDigraphAdjacencyWDigraph构造函数构造函数templateAdjacencyWDigraph:templateAdjacencyWDigraph:AdjacencyWDigraphAdjacencyWDigraph(int Vertices, T noEdge)(int Vertices, T noEdge) / / 构造函数构造函数构造函数构造函数n = Vertices;n
9、= Vertices;e = 0;e = 0;NoEdge = noEdge;NoEdge = noEdge;Make2DArray(a, n+1, n+1);Make2DArray(a, n+1, n+1);/ /初始化为没有边的图初始化为没有边的图初始化为没有边的图初始化为没有边的图for (int i = 1; i = n; i+)for (int i = 1; i = n; i+) for (int j = 1; j = n; j+) for (int j = 1; j = n; j+) aij = aij = NoEdgeNoEdge; ; ( n( n2 2 ) )7LOGO判断边
10、是否存在判断边是否存在Exist(int i, int j) Exist(int i, int j) templatetemplatebool AdjacencyWDigraph:bool AdjacencyWDigraph:ExistExist(int i, int j) const(int i, int j) const / / 边边边边(i, j)(i, j)存在吗存在吗存在吗存在吗? ?if (i 1 | j n | j n | aij = NoEdge)if (i 1 | j n | j n | aij = NoEdge) return false; return false;ret
11、urn true;return true; 函数函数函数函数Exist Exist 的代码不能区分下面两种情况：的代码不能区分下面两种情况：的代码不能区分下面两种情况：的代码不能区分下面两种情况： i i 或或或或j j 是否为有效顶点；是否为有效顶点；是否为有效顶点；是否为有效顶点；边边边边(i, j) (i, j) 是否存在。是否存在。是否存在。是否存在。8LOGO添加边添加边: Add: AddtemplateAdjacencyWDigraph&templateAdjacencyWDigraph&AdjacencyWDigraph :AdjacencyWDigraph :AddAdd(i
12、nt i, int j, const T& w)(int i, int j, const T& w) / / 如果边如果边如果边如果边(i,j) (i,j) 不存在，则将该边加入有向图中不存在，则将该边加入有向图中不存在，则将该边加入有向图中不存在，则将该边加入有向图中if (i 1 | j n | j n | i = j | aij != NoEdge)if (i 1 | j n | j n | i = j | aij != NoEdge)throw BadInput();throw BadInput();aij = w;aij = w;e+;e+;return *this;return *
13、this; (1 )(1 )9LOGO删除边删除边: Delete: Deletetemplate AdjacencyWDigraph&template AdjacencyWDigraph& AdjacencyWDigraph : AdjacencyWDigraph :DeleteDelete(int i, int j)(int i, int j) / /删除边删除边删除边删除边( i , j ) .( i , j ) .if (i 1 | j n | j n | aij = NoEdge)if (i 1 | j n | j n | aij = NoEdge) throw BadInput()
14、; throw BadInput();aij = NoEdge;aij = NoEdge;e- ;e- ;return *this;return *this; ( 1 )( 1 )10LOGO求顶点出度求顶点出度: OutDegree: OutDegreetemplatetemplateint AdjacencyWDigraph:int AdjacencyWDigraph:OutDegreeOutDegree(int i) const(int i) const/ / 返回顶点返回顶点返回顶点返回顶点i i的出度的出度的出度的出度if (i n) throw BadInput();if (i n
15、) throw BadInput();/ / 计算顶点计算顶点计算顶点计算顶点i i的出度的出度的出度的出度int sum = 0;int sum = 0;for (int j = 1; j = n; j+)for (int j = 1; j = n; j+) if ( if (aijaij != NoEdge) sum+; != NoEdge) sum+;return sum;return sum; ( n )( n )遍历第遍历第i行中行中有效边的条数有效边的条数11LOGO求顶点入度求顶点入度: InDegree: InDegreetemplatetemplateint Adjacenc
16、yWDigraph:int AdjacencyWDigraph:InDegreeInDegree(int i) const(int i) const/ / 返回顶点返回顶点返回顶点返回顶点i i的入度的入度的入度的入度if (i n) throw BadInput();if (i n) throw BadInput();/ / 计算顶点计算顶点计算顶点计算顶点i i的入度的入度的入度的入度int sum = 0;int sum = 0;for (int j = 1; j = n; j+)for (int j = 1; j = n; j+) if ( if (ajiaji != NoEdge)
17、sum+; != NoEdge) sum+;return sum;return sum; ( n)( n)遍历第遍历第i列中列中有效边的条数有效边的条数12LOGO无向加权图的定义（程序无向加权图的定义（程序12-212-2）templatetemplateclass class AdjacencyWGraphAdjacencyWGraph : public AdjacencyWDigraph : public AdjacencyWDigraph public :public :AdjacencyWGraph(int Vertices = 10, T noEdge = 0) : Adjacen
18、cyWGraph(int Vertices = 10, T noEdge = 0) : AdjacencyWDigraph(Vertices, noEdge)AdjacencyWDigraph(Vertices, noEdge) AdjacencyWGraph& Add(int i, int j, const T& w)AdjacencyWGraph& Add(int i, int j, const T& w) AdjacencyWDigraph : AdjacencyWDigraph : Add(i,j,w)Add(i,j,w) ; ; aji=waji=w; ; return *this;
19、 return *this; AdjacencyWGraph& Delete(int i, int j) AdjacencyWGraph& Delete(int i, int j) AdjacencyWDigraph :Delete(i , j) ; AdjacencyWDigraph :Delete(i , j) ; aji = NoEdgeaji = NoEdge; ; return *this; return *this; int Degree(int i) const return int Degree(int i) const return OutDegree(i);OutDegre
20、e(i); ; ;1）无向图的邻接矩阵）无向图的邻接矩阵是对称的是对称的2）派生类中如何解决）派生类中如何解决同名函数的屏蔽问题同名函数的屏蔽问题13LOGO无向图的定义（程序无向图的定义（程序12-412-4）class class AdjacencyGraphAdjacencyGraph : public AdjacencyWGraph : public AdjacencyWGraph public :public : AdjacencyGraph(int Vertices = 10) : AdjacencyGraph(int Vertices = 10) : AdjacencyWGrap
21、h(Vertices, AdjacencyWGraph(Vertices, 0 0) ) AdjacencyGraph& Add(int i, int j) AdjacencyGraph& Add(int i, int j) AdjacencyWGraph AdjacencyWGraph :Add (i, j, 1):Add (i, j, 1) ; ; return *this; return *this; AdjacencyGraph& Delete(int i, int j) AdjacencyGraph& Delete(int i, int j) AdjacencyWGraphAdjac
22、encyWGraph:Delete(i, j):Delete(i, j) ; ; return *this; return *this; ; ;14LOGO有向图的定义（程序有向图的定义（程序12-312-3）class class AdjacencyDigraphAdjacencyDigraph : public AdjacencyWDigraph : public AdjacencyWDigraph public :public : AdjacencyDigraph(int Vertices = 10) : AdjacencyDigraph(int Vertices = 10) : Adj
23、acencyWDigraph(Vertices, 0) AdjacencyWDigraph(Vertices, 0) AdjacencyDigraph& Add(int i, int j) AdjacencyDigraph& Add(int i, int j) AdjacencyWDigraph: AdjacencyWDigraph:Add(i, j,1)Add(i, j,1) ; ; return *this; return *this; AdjacencyDigraph& Delete(int i, int j) AdjacencyDigraph& Delete(int i, int j)
24、 AdjacencyWDigraph:Delete(i, j) ; AdjacencyWDigraph:Delete(i, j) ; return *this; return *this; ; ;15LOGOtemplatetemplateChain& Chain:Delete(T& x)Chain& Chain:Delete(T& x) / / 删除与删除与删除与删除与x x匹配的元素匹配的元素匹配的元素匹配的元素/ / 如果不存在相匹配的元素，则引发异常如果不存在相匹配的元素，则引发异常如果不存在相匹配的元素，则引发异常如果不存在相匹配的元素，则引发异常BadInputBadInputCh
25、ainNode *current = first,ChainNode *current = first,*trail = 0; / *trail = 0; / 指向指向指向指向currentcurrent之前的节点之前的节点之前的节点之前的节点/ /搜索匹配元素搜索匹配元素搜索匹配元素搜索匹配元素while (current & current-data != x) while (current & current-data != x) trail = current;trail = current;current = current-link;current = current-link;
26、12.7.3 12.7.3 扩充扩充ChainChain类类- -删除元素删除元素16LOGO删除元素（续）删除元素（续） if (!current) throw BadInput( ); / if (!current) throw BadInput( ); / 不存在匹配元素不存在匹配元素不存在匹配元素不存在匹配元素/ /在节点在节点在节点在节点currentcurrent中找到匹配元素中找到匹配元素中找到匹配元素中找到匹配元素 x = current-data; / x = current-data; / 保存匹配元素保存匹配元素保存匹配元素保存匹配元素/ / 从链表中删除从链表中删除从链
27、表中删除从链表中删除current current 节点节点节点节点if (trail) if (trail) trail-link = current-link; trail-link = current-link;elseelse first = current-link; first = current-link;delete current; / delete current; / 释放节点释放节点释放节点释放节点return *this;return *this; 17LOGO邻接表描述的图类关系邻接表描述的图类关系LinkedBaseLinkedBaseLinkedDigraphL
28、inkedDigraphLinkedWDigraphLinkedWDigraphLinkedGraphLinkedGraphLinkedWGraphLinkedWGraphl l LinkedDigraph LinkedDigraphl l LinkedWDigraph LinkedWDigraphl l LinkedGraph LinkedGraphl l LinkedWGraph LinkedWGraph链表节点的链表节点的结构不同结构不同18LOGOv 无权和加权图的派生路径之所以不同，其原因在于无权和加权图的派生路径之所以不同，其原因在于无权和加权图的派生路径之所以不同，其原因在于无权
29、和加权图的派生路径之所以不同，其原因在于加权有向图和无向图的链表节点中有一个加权有向图和无向图的链表节点中有一个加权有向图和无向图的链表节点中有一个加权有向图和无向图的链表节点中有一个权值域权值域权值域权值域，而，而，而，而无权有向图和无向图中则没有。无权有向图和无向图中则没有。无权有向图和无向图中则没有。无权有向图和无向图中则没有。v 对于后者，使用对于后者，使用对于后者，使用对于后者，使用int int 类型的链节点就足够了；而对类型的链节点就足够了；而对类型的链节点就足够了；而对类型的链节点就足够了；而对于前者，链节点必须包含于前者，链节点必须包含于前者，链节点必须包含于前者，链节点必须
30、包含一个权值域一个权值域一个权值域一个权值域和和和和一个顶点域一个顶点域一个顶点域一个顶点域。尽管节点结构存在这种差别，但某些基本函数的代码尽管节点结构存在这种差别，但某些基本函数的代码尽管节点结构存在这种差别，但某些基本函数的代码尽管节点结构存在这种差别，但某些基本函数的代码仍然是一样的。仍然是一样的。仍然是一样的。仍然是一样的。v 因此，引入一个新类因此，引入一个新类因此，引入一个新类因此，引入一个新类LinkedBaseLinkedBase，它包含了构造，它包含了构造，它包含了构造，它包含了构造函数、析构函数、函数、析构函数、函数、析构函数、函数、析构函数、EdgesEdges和和和和O
31、utDegreeOutDegree函数。函数。函数。函数。12.7.4 12.7.4 类类LinkedBaseLinkedBase19LOGO邻接链描述的基类邻接链描述的基类（程序（程序12-612-6）template class LinkedBasetemplate class LinkedBase 友元类友元类友元类友元类public:public:LinkedBase(int Vertices = 10)LinkedBase(int Vertices = 10) n = Vertices ;n = Vertices ;e = 0;e = 0;h = new Chain n+1; h =
32、 new Chain n+1; LinkedBase( ) delete h; LinkedBase( ) delete h; int Edges( ) const return e; int Edges( ) const return e; int Vertices( ) const return n; int Vertices( ) const return n; int int OutDegree(int i)OutDegree(int i) const constif (i n) throw OutOfBounds();if (i n) throw OutOfBounds();retu
33、rn return hi.Length();hi.Length(); private:private:int n; /int n; /顶点数顶点数顶点数顶点数int e; / int e; / 边数边数边数边数Chain *h; /Chain *h; /边节点链表表头指针数组边节点链表表头指针数组边节点链表表头指针数组边节点链表表头指针数组 ; ;20LOGO1 12 23 3h h112233213datalinkdatalinkint int OutDegreeOutDegree(int i) const(int i) const if (i n) throw OutOfBounds();
34、 if (i n) throw OutOfBounds(); return return hi.Length()hi.Length(); ; 某个节点的出度：统计第某个节点的出度：统计第i i行链表中结点的个数行链表中结点的个数 ( d( di ioutout) )21LOGO12.7.5 12.7.5 链接类链接类有向图的邻接链表（程序有向图的邻接链表（程序12-712-7）class class LinkedDigraphLinkedDigraph : public LinkedBase : public LinkedBase public:public:LinkedDigraph(int
35、 Vertices = 10) : LinkedBase LinkedDigraph(int Vertices = 10) : LinkedBase (Vertices) (Vertices) bool Exist(int i, int j) const;bool Exist(int i, int j) const;LinkedDigraph& Add(int i, int j);LinkedDigraph& Add(int i, int j);LinkedDigraph& Delete(int i, int j);LinkedDigraph& Delete(int i, int j);int
36、 InDegree(int i) const;int InDegree(int i) const;protected :protected :LinkedDigraph& AddNoCheck(int i, int j);LinkedDigraph& AddNoCheck(int i, int j); ; ;22LOGO判断边判断边( i, j )( i, j )是否存在是否存在bool LinkedDigraph:Exist(int i, int j) constbool LinkedDigraph:Exist(int i, int j) const/ / 边边边边( i , j )( i
37、, j )存在吗存在吗存在吗存在吗? ? if (i n) throw OutOfBounds( ); if (i n) throw OutOfBounds( ); return (hi.Search(j) ? true : false; return (hi.Search(j) ? true : false; 1 12 23 3h h112233213datalinkdatalink ( d( di ioutout) )23LOGO把边把边(i, j) (i, j) 加入到图中加入到图中LinkedDigraph& LinkedDigraph:Add(int i, int j)LinkedD
38、igraph& LinkedDigraph:Add(int i, int j) / / 把边把边把边把边(i,j) (i,j) 加入到图中加入到图中加入到图中加入到图中if (i 1 | j n | j n | i = j | if (i 1 | j n | j n | i = j | ExistExist(i, j) (i, j) throw BadInput(); throw BadInput();return AddNoCheck(i, j);return AddNoCheck(i, j); LinkedDigraph& LinkedDigraph:LinkedDigraph& Link
39、edDigraph:AddNoCheck(int i, int j)AddNoCheck(int i, int j) / / 增加边但不检查可能出现的错误增加边但不检查可能出现的错误增加边但不检查可能出现的错误增加边但不检查可能出现的错误hi.Insert(0,j);hi.Insert(0,j); / / 把把把把j j 添加到顶点添加到顶点添加到顶点添加到顶点i i 的表中的表中的表中的表中e+;e+;return *this;return *this; ( d( di ioutout) )24LOGO删除边删除边( i , j )( i , j )LinkedDigraph& Linked
40、Digraph:Delete(int i, int j)LinkedDigraph& LinkedDigraph:Delete(int i, int j) / / 删除边删除边删除边删除边( i , j )( i , j )if (i n) throw OutOfBounds();if (i n) throw OutOfBounds();hi.Delete( j ) ; /hi.Delete( j ) ; /找到并删除节点找到并删除节点找到并删除节点找到并删除节点e-;e-;return *this;return *this; 1 12 23 3h h112233213datalinkOO (
41、e)(e)25LOGO返回顶点返回顶点i i的入度的入度int LinkedDigraph:InDegree(int i) constint LinkedDigraph:InDegree(int i) const / / 返回顶点返回顶点返回顶点返回顶点i i的入度的入度的入度的入度if (i n) throw OutOfBounds();if (i n) throw OutOfBounds();/ / 计算到达顶点计算到达顶点计算到达顶点计算到达顶点i i的边的边的边的边int sum = 0;int sum = 0;for (int j = 1; j = n; j+)for (int j
42、= 1; j = n; j+)if (hj.Search(i) sum+;if (hj.Search(i) sum+;return sum;return sum; 1 12 23 3h h112233213datalink某个节点的入度：统计所有链表中满足某个节点的入度：统计所有链表中满足data=idata=i的结点个数的结点个数OO ( ne)( ne)26LOGO无向图的邻接链表类（程序无向图的邻接链表类（程序12-812-8）class class LinkedGraphLinkedGraph : public : public LinkedDigraphLinkedDigraph p
43、ublic:public:LinkedGraph(int Vertices = 10) : LinkedDigraph (Vertices) LinkedGraph(int Vertices = 10) : LinkedDigraph (Vertices) LinkedGraph& Add(int i, int j);LinkedGraph& Add(int i, int j);LinkedGraph& Delete(int i, int j);LinkedGraph& Delete(int i, int j);int int DegreeDegree(int i) const return
44、InDegree(i); (int i) const return InDegree(i); int int OutDegreeOutDegree(int i) const return InDegree(i); (int i) const return InDegree(i); protected :protected :LinkedGraph& AddNoCheck(int i, int j);LinkedGraph& AddNoCheck(int i, int j); ; ;27LOGO向图中添加边向图中添加边( i , j )( i , j )LinkedGraph& LinkedGr
45、aph:Add(int i, int j)LinkedGraph& LinkedGraph:Add(int i, int j) / / 向图中添加边向图中添加边向图中添加边向图中添加边( i , j )( i , j )if (i 1 | j n | j n | i =j | Exist(i, j) if (i 1 | j n | j n | i =j | Exist(i, j) throw BadInput(); throw BadInput();return AddNoCheck(i, j);return AddNoCheck(i, j); ( d( di ioutout) )28LOGO
46、添加边添加边(i, j), (i, j), 不检查可能出现的错误不检查可能出现的错误LinkedGraph& LinkedGraph:AddNoCheck(int i, int j)LinkedGraph& LinkedGraph:AddNoCheck(int i, int j)/ / 添加边添加边添加边添加边(i,j), (i,j), 不检查可能出现的错误不检查可能出现的错误不检查可能出现的错误不检查可能出现的错误hi.Insert (0, j)hi.Insert (0, j) ; ;try try hj.Insert(0,i)hj.Insert(0,i); ; 对称加入！对称加入！对称加入
47、！对称加入！/ / 若出现异常若出现异常若出现异常若出现异常, , 则取消第一次插入，并引发同样的异常则取消第一次插入，并引发同样的异常则取消第一次插入，并引发同样的异常则取消第一次插入，并引发同样的异常catch (.) hi.Delete(j); throw; catch (.) hi.Delete(j); throw; e+;e+;return *this;return *this; 1 14 42 23 3h1234241321datalinkdatalink29LOGO删除边删除边( i , j )( i , j )LinkedGraph& LinkedGraph:Delete(in
48、t i, int j)LinkedGraph& LinkedGraph:Delete(int i, int j) / /删除边删除边删除边删除边( i , j )( i , j )LinkedDigraph:Delete( i , j ) ; LinkedDigraph:Delete( i , j ) ; 对称删除对称删除对称删除对称删除( (隐含隐含隐含隐含e-)e-)e+;e+; / / 补偿，边只需减少一条！补偿，边只需减少一条！补偿，边只需减少一条！补偿，边只需减少一条！LinkedDigraph:Delete( j , i ) ;LinkedDigraph:Delete( j , i
49、 ) ;return *this;return *this; 1 14 42 23 3h1234241321datalinkdatalink30LOGOGraphNodeGraphNode类类template class GraphNode template class GraphNode friend LinkedWDigraph;friend LinkedWDigraph;friend LinkedWGraph;friend LinkedWGraph;friend Chain;friend Chain;public :public :int operator int operator !=
50、!=(GraphNode y) const(GraphNode y) const return ( vertex != y.vertex ) ; return ( vertex != y.vertex ) ; void Output(ostream& out) constvoid Output(ostream& out) const out vertex weight ; out vertex weight ; private :private :int vertex; / int vertex; / 边的第二个顶点边的第二个顶点边的第二个顶点边的第二个顶点T weight; / T weig
51、ht; / 边的权重边的权重边的权重边的权重 ; ;template template ostream& operator(ostream& out, GraphNode x)ostream& operator(ostream& out, GraphNode x) x.Output(out); return out; x.Output(out); return out; 权值结点权值结点31LOGO加权有向图邻接链表类（程序加权有向图邻接链表类（程序12-912-9）templatetemplateclass class LinkedWDigraphLinkedWDigraph : publi
52、c LinkedBaseGraphNode : public LinkedBaseGraphNode public :public :LinkedWDigraph(int Vertices = 10) : LinkedWDigraph(int Vertices = 10) : LinkedBaseGraphNode (Vertices) LinkedBaseGraphNode (Vertices) bool Exist(int i, int j) const;bool Exist(int i, int j) const;LinkedWDigraph& Add(int i, int j, Lin
53、kedWDigraph& Add(int i, int j, const T& wconst T& w); );LinkedWDigraph& Delete(int i, int j);LinkedWDigraph& Delete(int i, int j);int InDegree(int i) const;int InDegree(int i) const;protected :protected :LinkedWDigraph &LinkedWDigraph &AddNoCheck(int i, int j, const T& w);AddNoCheck(int i, int j, co
54、nst T& w); ; ;32LOGO是否存在边是否存在边(i, j) (i, j) templatetemplatebool LinkedWDigraph:Exist(int i, int j) constbool LinkedWDigraph:Exist(int i, int j) const / / 存在边存在边存在边存在边(i,j) (i,j) 吗吗吗吗? ?if (i n) throw OutOfBounds();if (i n) throw OutOfBounds();GraphNode x;GraphNode x;x.vertex = j;x.vertex = j;return
55、 hi.Search(x);return hi.Search(x); vertexvertexweightweightlinklink 加权图边节点结构加权图边节点结构加权图边节点结构加权图边节点结构GraphNodeGraphNode ( d( di ioutout) )33LOGO添加边添加边( i , j )( i , j )templateLinkedWDigraph& templateLinkedWDigraph& LinkedWDigraph :Add(int i, int j, const T& w)LinkedWDigraph :Add(int i, int j, const
56、T& w) / / 添加边添加边添加边添加边( i , j )( i , j )if (i 1 | j n | j n | i = j| Exist(i, j) if (i 1 | j n | j n | i = j| Exist(i, j) throw BadInput(); throw BadInput();return AddNoCheck(i, j, w);return AddNoCheck(i, j, w); ( d( di ioutout) )34LOGO添加边添加边( i , j )( i , j )，不检查可能出现的错误，不检查可能出现的错误 template LinkedWD
57、igraph& template LinkedWDigraph& LinkedWDigraph :AddNoCheck(int i, int j, const T& w) LinkedWDigraph :AddNoCheck(int i, int j, const T& w) / / 添加边添加边添加边添加边( i , j )( i , j )，不检查可能出现的错误，不检查可能出现的错误，不检查可能出现的错误，不检查可能出现的错误GraphNode x;GraphNode x;x.vertex = j; x.vertex = j; x.weight = w; x.weight = w;h i
58、.Insert (0 , x ) ;h i .Insert (0 , x ) ;e+ ;e+ ;return *this;return *this; 35LOGO删除边删除边( i , j )( i , j )templateLinkedWDigraph& templateLinkedWDigraph& LinkedWDigraph :Delete(int i, int j)LinkedWDigraph :Delete(int i, int j) / /删除边删除边删除边删除边( i , j )( i , j )if (i n) throw OutOfBounds();if (i n) thr
59、ow OutOfBounds();GraphNode x;GraphNode x;x.vertex = j;x.vertex = j;h i . Delete (x) ;h i . Delete (x) ;e - - ;e - - ;return *this;return *this; OO (e)(e)36LOGO返回顶点返回顶点i i的入度的入度templatetemplateint LinkedWDigraph:InDegree(int i) constint LinkedWDigraph:InDegree(int i) const/ / 返回顶点返回顶点返回顶点返回顶点i i的入度的入
60、度的入度的入度if (i n) throw OutOfBounds( );if (i n) throw OutOfBounds( );int sum = 0;int sum = 0;GraphNode x;GraphNode x;x.vertex = i;x.vertex = i;/ / 检查所有的检查所有的检查所有的检查所有的( j , i )( j , i )for (int j = 1; j = n; j+)for (int j = 1; j = n; j+)if (hj.Search(x) sum+;if (hj.Search(x) sum+;return sum;return sum
61、; OO (ne)(ne)37LOGO 图的遍历定义：从图中图的遍历定义：从图中图的遍历定义：从图中图的遍历定义：从图中某一顶点出发某一顶点出发某一顶点出发某一顶点出发，按照一定规则，通，按照一定规则，通，按照一定规则，通，按照一定规则，通过边或弧对图中过边或弧对图中过边或弧对图中过边或弧对图中所有顶点访问一次且只访问一次所有顶点访问一次且只访问一次所有顶点访问一次且只访问一次所有顶点访问一次且只访问一次。 图的遍历比树的遍历复杂，主要表现在以下方面：图的遍历比树的遍历复杂，主要表现在以下方面：图的遍历比树的遍历复杂，主要表现在以下方面：图的遍历比树的遍历复杂，主要表现在以下方面：（1 1）出
62、发点的选取出发点的选取出发点的选取出发点的选取与与与与图的连通性图的连通性图的连通性图的连通性；（2 2）回路回路回路回路的判断及处理：的判断及处理：的判断及处理：的判断及处理：（3 3）下一个要访问的顶点下一个要访问的顶点下一个要访问的顶点下一个要访问的顶点的选取。的选取。的选取。的选取。 设置一个访问的标记数组设置一个访问的标记数组设置一个访问的标记数组设置一个访问的标记数组reachnreachn，初值为，初值为，初值为，初值为0 0，一旦，一旦，一旦，一旦访问了某顶点访问了某顶点访问了某顶点访问了某顶点vivi，便置，便置，便置，便置reachireachi为为为为1 1或被访问时的序
63、号。或被访问时的序号。或被访问时的序号。或被访问时的序号。12.8 12.8 图的遍历图的遍历38LOGO几个主要操作：使用遍历器几个主要操作：使用遍历器vvBegin(i)Begin(i) ：返回：返回：返回：返回第一个第一个第一个第一个与顶点与顶点与顶点与顶点i i邻邻邻邻接的顶点。接的顶点。接的顶点。接的顶点。 对于邻接表，返回顶点对于邻接表，返回顶点对于邻接表，返回顶点对于邻接表，返回顶点i i 所对应表中所对应表中所对应表中所对应表中的第一个顶点；的第一个顶点；的第一个顶点；的第一个顶点； 对于邻接矩阵，返回邻接于顶点对于邻接矩阵，返回邻接于顶点对于邻接矩阵，返回邻接于顶点对于邻接矩
64、阵，返回邻接于顶点i i 的的的的最小（即第一个）顶点。最小（即第一个）顶点。最小（即第一个）顶点。最小（即第一个）顶点。 在两种情况中，如果没有邻接顶点，在两种情况中，如果没有邻接顶点，在两种情况中，如果没有邻接顶点，在两种情况中，如果没有邻接顶点，都将返回零值。都将返回零值。都将返回零值。都将返回零值。vvNextVertex (i)NextVertex (i) ：返回：返回：返回：返回下一个下一个下一个下一个与顶与顶与顶与顶点点点点i i邻接的顶点。邻接的顶点。邻接的顶点。邻接的顶点。 即返回顶点即返回顶点即返回顶点即返回顶点i i 对应邻接表中的下一个对应邻接表中的下一个对应邻接表中的
65、下一个对应邻接表中的下一个顶点或返回邻接于顶点顶点或返回邻接于顶点顶点或返回邻接于顶点顶点或返回邻接于顶点i i的下一个最小的下一个最小的下一个最小的下一个最小顶点。顶点。顶点。顶点。 当没有下一个顶点时函数返回零。当没有下一个顶点时函数返回零。当没有下一个顶点时函数返回零。当没有下一个顶点时函数返回零。1 14 42 23 3GG1 10111101111001100A A39LOGO几个主要操作几个主要操作vInitializePos()InitializePos() ：初始化用来跟踪每一个邻接表或：初始化用来跟踪每一个邻接表或：初始化用来跟踪每一个邻接表或：初始化用来跟踪每一个邻接表或(
66、 (耗费耗费耗费耗费) )邻接矩阵每一行中邻接矩阵每一行中邻接矩阵每一行中邻接矩阵每一行中当前位置当前位置当前位置当前位置的存储配置。的存储配置。的存储配置。的存储配置。vDeactivatePos()DeactivatePos() ：释放：释放：释放：释放InitializePos( )InitializePos( )所产生的所产生的所产生的所产生的存储配置。存储配置。存储配置。存储配置。40LOGO12.8.2 12.8.2 邻接矩阵的遍历函数邻接矩阵的遍历函数v邻接矩阵的遍历函数可以作为邻接矩阵的遍历函数可以作为邻接矩阵的遍历函数可以作为邻接矩阵的遍历函数可以作为基类基类基类基类Adja
67、cencyWDigraphAdjacencyWDigraph的一个的一个的一个的一个publicpublic函数来加以实函数来加以实函数来加以实函数来加以实现。现。现。现。v由于其他由于其他由于其他由于其他3 3种邻接类都是从这个类种邻接类都是从这个类种邻接类都是从这个类种邻接类都是从这个类派生派生派生派生出来的，因此出来的，因此出来的，因此出来的，因此它们可以从它们可以从它们可以从它们可以从AdjacencyDigraphAdjacencyDigraph类中继承该函数。类中继承该函数。类中继承该函数。类中继承该函数。v由于可能处在邻接矩阵不同行的不同位置，因此用由于可能处在邻接矩阵不同行的不
68、同位置，因此用由于可能处在邻接矩阵不同行的不同位置，因此用由于可能处在邻接矩阵不同行的不同位置，因此用一个数组一个数组一个数组一个数组pospos来记录每一行中的位置，这个变量是来记录每一行中的位置，这个变量是来记录每一行中的位置，这个变量是来记录每一行中的位置，这个变量是AdjacencyWDigraphAdjacencyWDigraph的私有成员，定义如下：的私有成员，定义如下：的私有成员，定义如下：的私有成员，定义如下：vint *pos;int *pos;41LOGOPos的初始化与释放的初始化与释放template template void AdjacencyWDigraph:In
69、itializePos( ) void AdjacencyWDigraph:InitializePos( ) pos = new int n+1; pos = new int n+1; template template void AdjacencyWDigraph:DeactivatePos( ) void AdjacencyWDigraph:DeactivatePos( ) delete pos; delete pos; 42LOGO邻接矩阵中返回第一个与顶点邻接矩阵中返回第一个与顶点邻接矩阵中返回第一个与顶点邻接矩阵中返回第一个与顶点i i i i邻接的顶点邻接的顶点邻接的顶点邻接的顶点
70、template template int AdjacencyWDigraph:Begin(int i)int AdjacencyWDigraph:Begin(int i) / /返回第一个与顶点返回第一个与顶点返回第一个与顶点返回第一个与顶点i i邻接的顶点邻接的顶点邻接的顶点邻接的顶点if (i n) throw OutOfBounds();if (i n) throw OutOfBounds();/ / 查找第一个邻接顶点查找第一个邻接顶点查找第一个邻接顶点查找第一个邻接顶点for (int j = 1; j = n; j+)for (int j = 1; j = n; j+)if (a
71、ij != NoEdge) /if (aij != NoEdge) /第第第第i i行第一个顶点行第一个顶点行第一个顶点行第一个顶点 posi = j; return j; posi = j; return j; posi = n + 1; / posi = n + 1; / 没有邻接顶点没有邻接顶点没有邻接顶点没有邻接顶点return 0;return 0; 43LOGO邻接矩阵中返回下一个与顶点邻接矩阵中返回下一个与顶点邻接矩阵中返回下一个与顶点邻接矩阵中返回下一个与顶点i i i i邻接的顶点邻接的顶点邻接的顶点邻接的顶点templatetemplateint AdjacencyWDig
72、raph:NextVertex(int i)int AdjacencyWDigraph:NextVertex(int i)/ / 返回下一个与顶点返回下一个与顶点返回下一个与顶点返回下一个与顶点i i邻接的顶点邻接的顶点邻接的顶点邻接的顶点if (i n) throw OutOfBounds();if (i n) throw OutOfBounds();/ / 寻找下一个邻接顶点寻找下一个邻接顶点寻找下一个邻接顶点寻找下一个邻接顶点for (int for (int j = posi + 1j = posi + 1; j = n; j+); j = n; j+)if (aij != NoEdg
73、e) / if (aij != NoEdge) / j j 是下一个顶点是下一个顶点是下一个顶点是下一个顶点 posi = j; return j; posi = j; return j; posi = n + 1; / posi = n + 1; / 不存在下一个顶点不存在下一个顶点不存在下一个顶点不存在下一个顶点return 0; return 0; 44LOGO使用示例使用示例vAdjacencyWDigraph wd;AdjacencyWDigraph wd;v加入边信息加入边信息加入边信息加入边信息，wd.Add(i, j, weight)wd.Add(i, j, weight)v遍
74、历：遍历：遍历：遍历：int pos= wd.Begin(i);int pos= wd.Begin(i);while(pos!=0)while(pos!=0) pos=wd.NextVertex(i); pos=wd.NextVertex(i); 45LOGO12.8.3 12.8.3 邻接链表的遍历函数邻接链表的遍历函数vv 对于用邻接链表描述的图和网络，需要将程序对于用邻接链表描述的图和网络，需要将程序对于用邻接链表描述的图和网络，需要将程序对于用邻接链表描述的图和网络，需要将程序12-1212-12中定义中定义中定义中定义的共享成员函数的共享成员函数的共享成员函数的共享成员函数Initi
75、alizeInitialize和和和和DeactivatePosDeactivatePos加入到加入到加入到加入到LinkedBaseLinkedBase类中，并且，还需要定义一个私有变量类中，并且，还需要定义一个私有变量类中，并且，还需要定义一个私有变量类中，并且，还需要定义一个私有变量pospos： ChainIterator *pos ChainIterator *pos；参见；参见；参见；参见P92-P93P92-P93vv 此外，还需要将余下的两个遍历函数加入到此外，还需要将余下的两个遍历函数加入到此外，还需要将余下的两个遍历函数加入到此外，还需要将余下的两个遍历函数加入到Linke
76、dDigraphLinkedDigraph和和和和LinkedWDigraphLinkedWDigraph类中。类中。类中。类中。void InitializePos( )void InitializePos( ) pos = new ChainIterator n+1; pos = new ChainIterator n+1; void DeactivatePos( ) delete pos; void DeactivatePos( ) delete pos; 46LOGO邻接链表中返回第一个与顶点邻接链表中返回第一个与顶点邻接链表中返回第一个与顶点邻接链表中返回第一个与顶点i i i i邻
77、接的顶点邻接的顶点邻接的顶点邻接的顶点int LinkedDigraph:Begin(int i)int LinkedDigraph:Begin(int i)/ / 返回第一个与顶点返回第一个与顶点返回第一个与顶点返回第一个与顶点i i邻接的顶点邻接的顶点邻接的顶点邻接的顶点if (i n) throw OutOfBounds( );if (i n) throw OutOfBounds( );intint *x = posi.Initialize(hi); *x = posi.Initialize(hi); 返回返回返回返回fisrtfisrt指针指针指针指针return (x) ? *x :
78、 0;return (x) ? *x : 0; 47LOGO邻接链表中返回下一个与顶点邻接链表中返回下一个与顶点邻接链表中返回下一个与顶点邻接链表中返回下一个与顶点i i i i邻接的顶点邻接的顶点邻接的顶点邻接的顶点int LinkedDigraph:NextVertex(int i)int LinkedDigraph:NextVertex(int i) / / 返回下一个与顶点返回下一个与顶点返回下一个与顶点返回下一个与顶点i i邻接的顶点邻接的顶点邻接的顶点邻接的顶点if (i n) throw OutOfBounds();if (i n) throw OutOfBounds();int
79、 *x = posi.Next();int *x = posi.Next();return (x) ? *x : 0;return (x) ? *x : 0; 48LOGO返回第一个与顶点返回第一个与顶点i i邻接的顶点邻接的顶点templatetemplateint LinkedWDigraph:Begin(int i)int LinkedWDigraph:Begin(int i) / / 返回第一个与顶点返回第一个与顶点返回第一个与顶点返回第一个与顶点i i邻接的顶点邻接的顶点邻接的顶点邻接的顶点if (i n) throw OutOfBounds();if (i n) throw Out
80、OfBounds();GraphNode *x = posi.Initialize(hi);GraphNode *x = posi.Initialize(hi);return (x) ? x-vertex : 0;return (x) ? x-vertex : 0; 49LOGO返回下一个与顶点返回下一个与顶点i i邻接的顶点邻接的顶点templatetemplateint LinkedWDigraph:NextVertex(int i)int LinkedWDigraph:NextVertex(int i) / / 返回下一个与顶点返回下一个与顶点返回下一个与顶点返回下一个与顶点i i邻接的
81、顶点邻接的顶点邻接的顶点邻接的顶点if (i n) throw OutOfBounds();if (i n) throw OutOfBounds();GraphNode *x = posi.Next();GraphNode *x = posi.Next();return (x) ? x-vertex : 0;return (x) ? x-vertex : 0; 50LOGO后续程序类派生层次图：后续程序类派生层次图：P392遍历器虚基类遍历器虚基类无向图和网络无向图和网络类的基类类的基类51LOGO12.10 12.10 图的搜索算法图的搜索算法v宽（广）度优先搜索（横向）：宽（广）度优先搜索
82、（横向）：BFSv深度优先搜索（纵向）：深度优先搜索（纵向）：DFS52LOGO（1 1）访问）访问）访问）访问指定的起始顶点指定的起始顶点指定的起始顶点指定的起始顶点v v0 0，然后依次访问，然后依次访问，然后依次访问，然后依次访问与与与与v v0 0相邻接的所有相邻接的所有相邻接的所有相邻接的所有顶点顶点顶点顶点w w1 1，w w2 2，w wk k；（2 2）按按按按w w1 1，w w2 2，w wk k的顺序的顺序的顺序的顺序，依次访问它们每一个顶点的所，依次访问它们每一个顶点的所，依次访问它们每一个顶点的所，依次访问它们每一个顶点的所有未被访问过的邻接点有未被访问过的邻接点有未
83、被访问过的邻接点有未被访问过的邻接点 设设设设w w1 1未被访问过的邻接点为未被访问过的邻接点为未被访问过的邻接点为未被访问过的邻接点为w w1111，w w1212，w w1m1m w wk k未被访问过的邻接点为未被访问过的邻接点为未被访问过的邻接点为未被访问过的邻接点为w wk1k1，w wk2k2，w wknkn（3 3）再按）再按）再按）再按w w1111，w w1212，w w1m 1m ， w wk1k1 ，w wk2k2，w wknkn的顺序，依的顺序，依的顺序，依的顺序，依次去访问它们的所有未被访问过的邻接点；次去访问它们的所有未被访问过的邻接点；次去访问它们的所有未被访问
84、过的邻接点；次去访问它们的所有未被访问过的邻接点；（4 4）依此类推，直到图中所有被访问过的顶点的邻接点都被访）依此类推，直到图中所有被访问过的顶点的邻接点都被访）依此类推，直到图中所有被访问过的顶点的邻接点都被访）依此类推，直到图中所有被访问过的顶点的邻接点都被访问过为止；问过为止；问过为止；问过为止；（5 5）如果此时图中还有未被访问过的顶点，则从其中一个未被）如果此时图中还有未被访问过的顶点，则从其中一个未被）如果此时图中还有未被访问过的顶点，则从其中一个未被）如果此时图中还有未被访问过的顶点，则从其中一个未被访问过的顶点出发，重复（访问过的顶点出发，重复（访问过的顶点出发，重复（访问过
85、的顶点出发，重复（1 1）- -（5 5）直到图中所有顶点都被访）直到图中所有顶点都被访）直到图中所有顶点都被访）直到图中所有顶点都被访问过为止。问过为止。问过为止。问过为止。图的宽（广）度优先搜索图的宽（广）度优先搜索（Breadth First SearchBreadth First SearchBreadth First SearchBreadth First Search，BFSBFSBFSBFS）53LOGO宽度优先搜索（宽度优先搜索（BFSBFS）示例）示例 判断从顶点判断从顶点判断从顶点判断从顶点1 1出发可到达的所有顶点的一种方法是首先确定邻出发可到达的所有顶点的一种方法是首先
86、确定邻出发可到达的所有顶点的一种方法是首先确定邻出发可到达的所有顶点的一种方法是首先确定邻接于顶点接于顶点接于顶点接于顶点1 1的顶点集合，这个集合是的顶点集合，这个集合是的顶点集合，这个集合是的顶点集合，这个集合是 2 , 3 , 4 2 , 3 , 4 。 然后确定邻接于然后确定邻接于然后确定邻接于然后确定邻接于 2 , 3 , 4 2 , 3 , 4 的新的顶点集合，这个集合是的新的顶点集合，这个集合是的新的顶点集合，这个集合是的新的顶点集合，这个集合是 5 , 5 , 6 , 7 6 , 7 。邻接于。邻接于。邻接于。邻接于 5 , 6 , 7 5 , 6 , 7 的顶点集合为的顶点集
87、合为的顶点集合为的顶点集合为 8 , 9 8 , 9 ，而不存在邻接于，而不存在邻接于，而不存在邻接于，而不存在邻接于 8 , 9 8 , 9 的顶点。的顶点。的顶点。的顶点。因此从顶点因此从顶点因此从顶点因此从顶点1 1出发可到达的顶点集合为出发可到达的顶点集合为出发可到达的顶点集合为出发可到达的顶点集合为 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 9 。54LOGOV V1 1V V2 2V V3 3V V7 7V V6 6V V5 5V V4 4V V8 8 宽度优先搜索遍历的宽度优先搜索遍历的宽度
88、优先搜索遍历的宽度优先搜索遍历的结果序列为：结果序列为：结果序列为：结果序列为：V V8 8V V1 1V V2 2V V3 3V V4 4V V5 5V V6 6V V7 7n n 先访问的顶点其邻接点先被访问先访问的顶点其邻接点先被访问先访问的顶点其邻接点先被访问先访问的顶点其邻接点先被访问队列。队列。队列。队列。宽度优先搜索宽度优先搜索示例示例55LOGO 为了实现逐层访问，算法中使用了一个为了实现逐层访问，算法中使用了一个为了实现逐层访问，算法中使用了一个为了实现逐层访问，算法中使用了一个队列队列队列队列，以记忆正在访，以记忆正在访，以记忆正在访，以记忆正在访问的这一层和上一层的顶点，
89、以便于向下一层访问。问的这一层和上一层的顶点，以便于向下一层访问。问的这一层和上一层的顶点，以便于向下一层访问。问的这一层和上一层的顶点，以便于向下一层访问。 为避免重复访问，需要一个辅助数组为避免重复访问，需要一个辅助数组为避免重复访问，需要一个辅助数组为避免重复访问，需要一个辅助数组 reachreach ，给被访问过，给被访问过，给被访问过，给被访问过的顶点加标记。的顶点加标记。的顶点加标记。的顶点加标记。 广度优先搜索是一种广度优先搜索是一种广度优先搜索是一种广度优先搜索是一种分层分层分层分层的搜索过程，每向前走一步可能访的搜索过程，每向前走一步可能访的搜索过程，每向前走一步可能访的搜
90、索过程，每向前走一步可能访问一批顶点，类似于问一批顶点，类似于问一批顶点，类似于问一批顶点，类似于树的层次遍历树的层次遍历树的层次遍历树的层次遍历。BFSBFS算法思想算法思想56LOGO宽度优先搜索（宽度优先搜索（BFSBFS）伪码算法伪码算法57LOGOvoid Network:BFS(int v, int reach, int label)void Network:BFS(int v, int reach, int label) / / 宽度优先搜索宽度优先搜索宽度优先搜索宽度优先搜索LinkedQueue Q;LinkedQueue Q;InitializePos( ); /Initi
91、alizePos( ); /初始化图遍历器数组初始化图遍历器数组初始化图遍历器数组初始化图遍历器数组reachv = label;reachv = label;Q . Add ( v ) ;Q . Add ( v ) ;while (!Q.IsEmpty( ) while (!Q.IsEmpty( ) int w;int w;Q.Delete(w); / Q.Delete(w); / 获取一个已标记的顶点获取一个已标记的顶点获取一个已标记的顶点获取一个已标记的顶点int u = Begin(w);int u = Begin(w);while (u) / while (u) / 访问访问访问访问
92、ww的邻接顶点的邻接顶点的邻接顶点的邻接顶点 if (!reachu) / if (!reachu) / 一个未曾到达的顶点一个未曾到达的顶点一个未曾到达的顶点一个未曾到达的顶点 Q.Add ( u ) ; Q.Add ( u ) ; reachu = label; / reachu = label; / 标记已到达该顶点标记已到达该顶点标记已到达该顶点标记已到达该顶点 u = NextVertex(w); / u = NextVertex(w); / 下一个与下一个与下一个与下一个与ww邻接的顶点邻接的顶点邻接的顶点邻接的顶点 DeactivatePos( ); / DeactivatePo
93、s( ); / 释放遍历器数组释放遍历器数组释放遍历器数组释放遍历器数组 58LOGO邻接矩阵描述中邻接矩阵描述中B F SB F S的直接实现的直接实现templatetemplatevoid AdjacencyWDigraph:BFS (int v, int reach, int label)void AdjacencyWDigraph:BFS (int v, int reach, int label) / / 宽度优先搜索宽度优先搜索宽度优先搜索宽度优先搜索LinkedQueue Q;LinkedQueue Q;reachv = label;reachv = label;Q . Add
94、( v ) ;Q . Add ( v ) ;while (!Q.IsEmpty() while (!Q.IsEmpty() int w; int w; Q.Delete(w); / Q.Delete(w); / 获取一个已标记的顶点获取一个已标记的顶点获取一个已标记的顶点获取一个已标记的顶点/ / 对尚未标记的、邻接自对尚未标记的、邻接自对尚未标记的、邻接自对尚未标记的、邻接自ww的顶点进行标记的顶点进行标记的顶点进行标记的顶点进行标记for (int u = 1; u = n; u+)for (int u = 1; u = n; u+)if (awu != NoEdge & !reachu)
95、 if (awu != NoEdge & !reachu) Q.Add(u); / u Q.Add(u); / u 未被标记未被标记未被标记未被标记reachu = label;reachu = label; OO (sn)(sn)59LOGO链接图和有向图中链接图和有向图中B F SB F S的直接实现的直接实现void LinkedDigraph:BFS(int v, int reach, int label)void LinkedDigraph:BFS(int v, int reach, int label) / / 宽度优先搜索宽度优先搜索宽度优先搜索宽度优先搜索LinkedQueue
96、 Q;LinkedQueue Q;reachv = label;reachv = label;Q . Add ( v ) ;Q . Add ( v ) ;while (!Q.IsEmpty() while (!Q.IsEmpty() int w;int w;Q.Delete(w); / Q.Delete(w); / 获取一个已标记的顶点获取一个已标记的顶点获取一个已标记的顶点获取一个已标记的顶点/ / 使用指针使用指针使用指针使用指针p p沿着邻接表进行搜索沿着邻接表进行搜索沿着邻接表进行搜索沿着邻接表进行搜索ChainNode *p;ChainNode *p;for (p = hw.Firs
97、t(); p; p = p-link) for (p = hw.First(); p; p = p-link) int u = p-data;int u = p-data;if (!reachu) / if (!reachu) / 一个尚未到达的顶点一个尚未到达的顶点一个尚未到达的顶点一个尚未到达的顶点Q . Add ( u ) ;Q . Add ( u ) ;reachu = label; reachu = label; 60LOGOBFSBFS算法分析算法分析【注意注意注意注意】只有当选取的只有当选取的只有当选取的只有当选取的出发点出发点出发点出发点、采用的、采用的、采用的、采用的存储结构
98、存储结构存储结构存储结构以及以及以及以及遍历方式遍历方式遍历方式遍历方式都确定时遍历，遍历的结果才是唯一的。都确定时遍历，遍历的结果才是唯一的。都确定时遍历，遍历的结果才是唯一的。都确定时遍历，遍历的结果才是唯一的。61LOGO（1 1）首先访问）首先访问）首先访问）首先访问指定的起始顶点指定的起始顶点指定的起始顶点指定的起始顶点v v0 0，再访问再访问再访问再访问与与与与v v0 0邻接的任一未访邻接的任一未访邻接的任一未访邻接的任一未访问过的顶点问过的顶点问过的顶点问过的顶点w w1 1；（2 2）从）从）从）从w w1 1出发，访问出发，访问出发，访问出发，访问与与与与w w1 1邻接
99、的任一未访问过的顶点邻接的任一未访问过的顶点邻接的任一未访问过的顶点邻接的任一未访问过的顶点w w2 2；（3 3）从）从）从）从w w2 2出发，重复与（出发，重复与（出发，重复与（出发，重复与（2 2）类似的访问，）类似的访问，）类似的访问，）类似的访问，直到遇到一个所有直到遇到一个所有直到遇到一个所有直到遇到一个所有邻接点都被访问过的顶点为止邻接点都被访问过的顶点为止邻接点都被访问过的顶点为止邻接点都被访问过的顶点为止；（4 4）依次）依次）依次）依次回退到尚有邻接点未被访问过的顶点回退到尚有邻接点未被访问过的顶点回退到尚有邻接点未被访问过的顶点回退到尚有邻接点未被访问过的顶点，重复与（
100、，重复与（，重复与（，重复与（3 3）类）类）类）类似的访问，直到图中似的访问，直到图中似的访问，直到图中似的访问，直到图中所有和所有和所有和所有和v0v0有路径相通的顶点都被访问过有路径相通的顶点都被访问过有路径相通的顶点都被访问过有路径相通的顶点都被访问过；（5 5）如果图中）如果图中）如果图中）如果图中存在未被访问过的顶点存在未被访问过的顶点存在未被访问过的顶点存在未被访问过的顶点，从其中一个未被访问过的，从其中一个未被访问过的，从其中一个未被访问过的，从其中一个未被访问过的顶点出发，重复（顶点出发，重复（顶点出发，重复（顶点出发，重复（1 1）- -（5 5），直至图中所有顶点都被访问
101、完。），直至图中所有顶点都被访问完。），直至图中所有顶点都被访问完。），直至图中所有顶点都被访问完。图的深度优先搜索图的深度优先搜索（Depth First SearchDepth First SearchDepth First SearchDepth First Search，DFSDFSDFSDFS）62LOGO（1 1）从指定顶点）从指定顶点）从指定顶点）从指定顶点v v0 0出发，出发，出发，出发，访问该顶点访问该顶点访问该顶点访问该顶点v v0 0；（2 2）从）从）从）从v v0 0的一个未被访问过的邻接点出发的一个未被访问过的邻接点出发的一个未被访问过的邻接点出发的一个未被访问过
102、的邻接点出发，进行深度优先，进行深度优先，进行深度优先，进行深度优先搜索，直到图中与搜索，直到图中与搜索，直到图中与搜索，直到图中与v v0 0有路径相通的顶点都被访问过；有路径相通的顶点都被访问过；有路径相通的顶点都被访问过；有路径相通的顶点都被访问过；（3 3）若图中还存在未被访问过的顶点，则从其中一个未被）若图中还存在未被访问过的顶点，则从其中一个未被）若图中还存在未被访问过的顶点，则从其中一个未被）若图中还存在未被访问过的顶点，则从其中一个未被访问的顶点出发，重复（访问的顶点出发，重复（访问的顶点出发，重复（访问的顶点出发，重复（1 1）- -（3 3），直至图中所有顶点都被），直至图
103、中所有顶点都被），直至图中所有顶点都被），直至图中所有顶点都被访问过为止。访问过为止。访问过为止。访问过为止。 图的深度优先搜索类似于图的深度优先搜索类似于图的深度优先搜索类似于图的深度优先搜索类似于树的先根遍历树的先根遍历树的先根遍历树的先根遍历。深度优先搜索深度优先搜索（DFSDFS）递归算法思想）递归算法思想63LOGOV V1 1V V2 2V V3 3V V7 7V V6 6V V5 5V V4 4V V8 8 深度优先搜索遍历深度优先搜索遍历深度优先搜索遍历深度优先搜索遍历的结果序列为：的结果序列为：的结果序列为：的结果序列为：V V7 7V V1 1V V2 2V V4 4V V
104、8 8V V5 5V V6 6V V3 3l l 后访问的顶点其邻接点先被访问后访问的顶点其邻接点先被访问后访问的顶点其邻接点先被访问后访问的顶点其邻接点先被访问栈。栈。栈。栈。深度优先搜索示例深度优先搜索示例64LOGO深度优先搜索算法深度优先搜索算法DFSDFSvoid Network:DFS(int v, int reach, int label)void Network:DFS(int v, int reach, int label) / / 深度优先搜索深度优先搜索深度优先搜索深度优先搜索InitializePos( ); / InitializePos( ); / 初始化图遍历器数
105、组初始化图遍历器数组初始化图遍历器数组初始化图遍历器数组dfs ( v, reach, label); / dfs ( v, reach, label); / 执行执行执行执行d f sd f sDeactivatePos( ); / DeactivatePos( ); / 释放图遍历器数组释放图遍历器数组释放图遍历器数组释放图遍历器数组 65LOGO实际执行深度优先搜索的代码实际执行深度优先搜索的代码dfsdfsvoid Network:dfs(int v, int reach, int label)void Network:dfs(int v, int reach, int label)
106、/ /实际执行深度优先搜索的代码实际执行深度优先搜索的代码实际执行深度优先搜索的代码实际执行深度优先搜索的代码reachv = label;reachv = label;int u = Begin(v);int u = Begin(v);while (u)while (u) / u / u邻接至邻接至邻接至邻接至v v if (!reachu) if (!reachu) dfs(u, reach, label)dfs(u, reach, label); ; u = NextVertex ( v ) ; u = NextVertex ( v ) ; 66LOGOu 设置一个栈结构，设置一个栈结构
107、，设置一个栈结构，设置一个栈结构，u 在遍历时，每访问一个顶点在遍历时，每访问一个顶点在遍历时，每访问一个顶点在遍历时，每访问一个顶点w w，就将，就将，就将，就将w w压入栈中，压入栈中，压入栈中，压入栈中，然后访问然后访问然后访问然后访问w w的一个未被访问的邻接顶点的一个未被访问的邻接顶点的一个未被访问的邻接顶点的一个未被访问的邻接顶点u 如果在遍历过程中某顶点的所有邻接顶点都已被访如果在遍历过程中某顶点的所有邻接顶点都已被访如果在遍历过程中某顶点的所有邻接顶点都已被访如果在遍历过程中某顶点的所有邻接顶点都已被访问过，就从栈顶删去该顶点，问过，就从栈顶删去该顶点，问过，就从栈顶删去该顶点
108、，问过，就从栈顶删去该顶点，u 然后继续访问当前栈顶元素的一个未被访问过的邻然后继续访问当前栈顶元素的一个未被访问过的邻然后继续访问当前栈顶元素的一个未被访问过的邻然后继续访问当前栈顶元素的一个未被访问过的邻接顶点，当栈为空时，遍历操作结束。接顶点，当栈为空时，遍历操作结束。接顶点，当栈为空时，遍历操作结束。接顶点，当栈为空时，遍历操作结束。思考：思考：DFSDFS的非递归算法的非递归算法67LOGO能使能使能使能使DFSDFSDFSDFS和和和和BFSBFSBFSBFS产生最好和最坏性能的图例产生最好和最坏性能的图例产生最好和最坏性能的图例产生最好和最坏性能的图例68LOGO 选择题：如图所
109、示，给出由选择题：如图所示，给出由选择题：如图所示，给出由选择题：如图所示，给出由7 7个顶点组成的无向图。从顶点个顶点组成的无向图。从顶点个顶点组成的无向图。从顶点个顶点组成的无向图。从顶点1 1出发，对它进行出发，对它进行出发，对它进行出发，对它进行深度优先遍历深度优先遍历深度优先遍历深度优先遍历得到的顶点序列是得到的顶点序列是得到的顶点序列是得到的顶点序列是 （1 1） ；而进；而进；而进；而进行行行行宽度优先遍历宽度优先遍历宽度优先遍历宽度优先遍历得到的序列是得到的序列是得到的序列是得到的序列是（2 2）。 （1 1）A. 1354267 A. 1354267 （2 2）A. 1534
110、267A. 1534267 B. 1347625 B. 1726453 B. 1347625 B. 1726453 C. 1534276 C. 1354276 C. 1534276 C. 1354276 D. 1247653 D. 1247653 D. 1247653 D. 12476531 12 23 34 47 75 56 6 课堂练习课堂练习69LOGOv 寻找路径寻找路径v 连通图及连通分量连通图及连通分量v 生成树生成树12.11 12.11 应用应用70LOGO12.11.1 12.11.1 寻找路径寻找路径v若从顶点若从顶点若从顶点若从顶点v v 开始搜索（宽度或深度优先）且到达
111、顶开始搜索（宽度或深度优先）且到达顶开始搜索（宽度或深度优先）且到达顶开始搜索（宽度或深度优先）且到达顶点点点点w w 时终止搜索，则可以找到一条从顶点时终止搜索，则可以找到一条从顶点时终止搜索，则可以找到一条从顶点时终止搜索，则可以找到一条从顶点v v 到达顶到达顶到达顶到达顶点点点点w w 的路径。的路径。的路径。的路径。v要实际构造这条路径，需要记住从一个顶点到下一要实际构造这条路径，需要记住从一个顶点到下一要实际构造这条路径，需要记住从一个顶点到下一要实际构造这条路径，需要记住从一个顶点到下一个顶点的边。个顶点的边。个顶点的边。个顶点的边。v对于路径问题，所需要的边的集合已隐含在深度优
112、对于路径问题，所需要的边的集合已隐含在深度优对于路径问题，所需要的边的集合已隐含在深度优对于路径问题，所需要的边的集合已隐含在深度优先的递归过程中，因此可以很容易地先的递归过程中，因此可以很容易地先的递归过程中，因此可以很容易地先的递归过程中，因此可以很容易地利用深度优先利用深度优先利用深度优先利用深度优先策略策略策略策略设计一个寻找路径程序。完成顶点设计一个寻找路径程序。完成顶点设计一个寻找路径程序。完成顶点设计一个寻找路径程序。完成顶点w w 的标记之的标记之的标记之的标记之后展开递归，可以反向建立起从后展开递归，可以反向建立起从后展开递归，可以反向建立起从后展开递归，可以反向建立起从w
113、w 到到到到v v 的路径。的路径。的路径。的路径。71LOGOvvFindPath FindPath 的代码如程序的代码如程序的代码如程序的代码如程序12 - 2112 - 21。这个程序要求把。这个程序要求把。这个程序要求把。这个程序要求把VerticesVertices( )( )定义为定义为定义为定义为Network Network 的一个虚拟成员。的一个虚拟成员。的一个虚拟成员。的一个虚拟成员。findPathfindPath的输入参的输入参的输入参的输入参数是路径的开始顶点数是路径的开始顶点数是路径的开始顶点数是路径的开始顶点( v )( v )和目标顶点和目标顶点和目标顶点和目标
114、顶点( w )( w )。如果没有从。如果没有从。如果没有从。如果没有从v v到到到到ww的路径，的路径，的路径，的路径， findPathfindPath返回返回返回返回falsefalse；否则返回；否则返回；否则返回；否则返回truetrue。当。当。当。当找到路径时，用参数找到路径时，用参数找到路径时，用参数找到路径时，用参数length length 返回路径长度（路径中边的返回路径长度（路径中边的返回路径长度（路径中边的返回路径长度（路径中边的条数），用顶点数组条数），用顶点数组条数），用顶点数组条数），用顶点数组p 0p 0：length length 返回路径，其中返回路径，其
115、中返回路径，其中返回路径，其中p0=v p0=v 且且且且p length = wp length = w。vvfindPathfindPath首先检验首先检验首先检验首先检验v=w v=w 情况。在这种情况下，返回一个情况。在这种情况下，返回一个情况。在这种情况下，返回一个情况。在这种情况下，返回一个长度为长度为长度为长度为0 0的路径。如果的路径。如果的路径。如果的路径。如果vwvw，则调用图的遍历函数，则调用图的遍历函数，则调用图的遍历函数，则调用图的遍历函数InitializePosInitializePos，然后，然后，然后，然后FindPath FindPath 产生并初始化一个数
116、组产生并初始化一个数组产生并初始化一个数组产生并初始化一个数组reachreach，路径的，路径的，路径的，路径的DFSDFS实际上是由实际上是由实际上是由实际上是由NetworkNetwork的私有成员的私有成员的私有成员的私有成员findPathfindPath完成的，当且仅当没有路径时，完成的，当且仅当没有路径时，完成的，当且仅当没有路径时，完成的，当且仅当没有路径时， findPathfindPath返返返返回回回回falsefalse。72LOGOv函数函数函数函数findPathfindPath是一个修改过的是一个修改过的是一个修改过的是一个修改过的DFSDFS，它对标准的，它对标
117、准的，它对标准的，它对标准的DFSDFS作了如下两点修改：作了如下两点修改：作了如下两点修改：作了如下两点修改： 1) 1) 一旦到达了目标顶点一旦到达了目标顶点一旦到达了目标顶点一旦到达了目标顶点ww， findPathfindPath将不再继将不再继将不再继将不再继续搜索可到达顶点；续搜索可到达顶点；续搜索可到达顶点；续搜索可到达顶点； 2) findpath 2) findpath 将开始顶点将开始顶点将开始顶点将开始顶点v v 到当前顶点到当前顶点到当前顶点到当前顶点u u 路径中的路径中的路径中的路径中的顶点记录到数组顶点记录到数组顶点记录到数组顶点记录到数组path path 中。
118、中。中。中。vfindPathfindPath与与与与DFSDFS具有相同的复杂性。具有相同的复杂性。具有相同的复杂性。具有相同的复杂性。73LOGObool Network:FindPath (int v, int w, int &length, int path)bool Network:FindPath (int v, int w, int &length, int path)/ / 寻找一条从寻找一条从寻找一条从寻找一条从v v 到到到到ww的路径的路径的路径的路径, , 返回路径的长度，并将路径存入数组返回路径的长度，并将路径存入数组返回路径的长度，并将路径存入数组返回路径的长度，并
119、将路径存入数组p a t h 0 : l e n g t h p a t h 0 : l e n g t h / /如果不存在路径，则返回如果不存在路径，则返回如果不存在路径，则返回如果不存在路径，则返回falsefalse/ /路径中的第一个顶点总是路径中的第一个顶点总是路径中的第一个顶点总是路径中的第一个顶点总是v v path0 = v; path0 = v; length = 0; / length = 0; /当前路径的长度当前路径的长度当前路径的长度当前路径的长度 if (v = w) return true; if (v = w) return true; / /为路径的递归搜索
120、进行初始化为路径的递归搜索进行初始化为路径的递归搜索进行初始化为路径的递归搜索进行初始化 int n = Vertices ( ) ; int n = Vertices ( ) ; InitializePos( ); / InitializePos( ); / 遍历器遍历器遍历器遍历器 int *reach = new int n+1; int *reach = new int n+1; for (int i = 1; i = n; i+) reachi = 0; for (int i = 1; i = n; i+) reachi = 0; / / 搜索路径搜索路径搜索路径搜索路径 bool
121、x = bool x = findPathfindPath(v, w, length, path, reach);(v, w, length, path, reach); DeactivatePos ( ) ; DeactivatePos ( ) ; delete reach; delete reach; return x; return x; 74LOGObool Network:findPath(int v, int w, int &length, int path, int bool Network:findPath(int v, int w, int &length, int path
122、, int reach)reach) / / 实际搜索实际搜索实际搜索实际搜索v v到到到到ww的路径，其中的路径，其中的路径，其中的路径，其中v != w.v != w./ / 按深度优先方式搜索一条到达按深度优先方式搜索一条到达按深度优先方式搜索一条到达按深度优先方式搜索一条到达ww的路径的路径的路径的路径reachv = 1;reachv = 1;int u = Begin(v);int u = Begin(v);while (u) while (u) if (!reachu) if (!reachu) length+;length+;pathlength = u; / pathleng
123、th = u; / 将将将将u u 加入加入加入加入pathpathif (u = w) if (u = w) return truereturn true; ;if (findPath(u, w, length, path, reach)if (findPath(u, w, length, path, reach)return truereturn true; ;/ / 不存在从不存在从不存在从不存在从u u 到到到到ww的路径的路径的路径的路径length-; /length-; /删除删除删除删除u u u = NextVertex(v) ; u = NextVertex(v) ; re
124、turn false; return false; 75LOGO12.11.2 12.11.2 连通图及连通分量连通图及连通分量v通过从任意顶点开始执行通过从任意顶点开始执行通过从任意顶点开始执行通过从任意顶点开始执行DFSDFS或或或或BFSBFS，并且检验所，并且检验所，并且检验所，并且检验所有顶点是否被标记为已到达顶点，可以有顶点是否被标记为已到达顶点，可以有顶点是否被标记为已到达顶点，可以有顶点是否被标记为已到达顶点，可以判断一个无判断一个无判断一个无判断一个无向图向图向图向图GG是否连通是否连通是否连通是否连通。v假设假设假设假设i i 是搜索的开始顶点并且搜索到达了图中的所有是搜索
125、的开始顶点并且搜索到达了图中的所有是搜索的开始顶点并且搜索到达了图中的所有是搜索的开始顶点并且搜索到达了图中的所有顶点，利用顶点，利用顶点，利用顶点，利用i i 到到到到u u 的反向路径及的反向路径及的反向路径及的反向路径及i i 到到到到v v的路径，可以的路径，可以的路径，可以的路径，可以构造任意两个顶点构造任意两个顶点构造任意两个顶点构造任意两个顶点u u 和和和和v v 之间的路径。如果图不连之间的路径。如果图不连之间的路径。如果图不连之间的路径。如果图不连通，则函数通，则函数通，则函数通，则函数ConnectedConnected返回返回返回返回falsefalse，否则返回，否则
126、返回，否则返回，否则返回truetrue。v由于由于由于由于连通连通连通连通的概念仅针对的概念仅针对的概念仅针对的概念仅针对无向图和网络无向图和网络无向图和网络无向图和网络而言，因此，而言，因此，而言，因此，而言，因此，可以定义一个新类可以定义一个新类可以定义一个新类可以定义一个新类UndirectedUndirected，函数，函数，函数，函数ConnectedConnected是是是是UndirectedUndirected的一个成员。的一个成员。的一个成员。的一个成员。76LOGO确定无向图是否连通确定无向图是否连通确定无向图是否连通确定无向图是否连通class Undirected :
127、 virtual public Network class Undirected : virtual public Network public :public : bool Connected(); bool Connected(); ; ;bool Undirected:Connected()bool Undirected:Connected() / / 当且仅当图是连通的，则返回当且仅当图是连通的，则返回当且仅当图是连通的，则返回当且仅当图是连通的，则返回truetrueint n = Vertices( ) ;int n = Vertices( ) ;/ / 置所有顶点为未到达顶点置所
128、有顶点为未到达顶点置所有顶点为未到达顶点置所有顶点为未到达顶点int *reach = new int n+1;int *reach = new int n+1;for (int i = 1; i = n; i+)for (int i = 1; i = n; i+)reachi = 0;reachi = 0;/ / 对从顶点对从顶点对从顶点对从顶点1 1出发可到达的顶点进行标记出发可到达的顶点进行标记出发可到达的顶点进行标记出发可到达的顶点进行标记DFS(1, reach, 1);DFS(1, reach, 1);/ / 检查是否所有顶点都已经被标记检查是否所有顶点都已经被标记检查是否所有顶点
129、都已经被标记检查是否所有顶点都已经被标记for (int i = 1; i = n; i+)for (int i = 1; i = n; i+)if (!reachi) return false;if (!reachi) return false;return true; return true; 77LOGO 当无向图为当无向图为当无向图为当无向图为非连通图非连通图非连通图非连通图时，从图中某一顶点出发，一次调时，从图中某一顶点出发，一次调时，从图中某一顶点出发，一次调时，从图中某一顶点出发，一次调用深度优先搜索算法或广度优先搜索算法不可能访问到图中用深度优先搜索算法或广度优先搜索算法不可能
130、访问到图中用深度优先搜索算法或广度优先搜索算法不可能访问到图中用深度优先搜索算法或广度优先搜索算法不可能访问到图中的所有顶点，只能访问到该顶点所在的的所有顶点，只能访问到该顶点所在的的所有顶点，只能访问到该顶点所在的的所有顶点，只能访问到该顶点所在的最大连通子图最大连通子图最大连通子图最大连通子图（连通（连通（连通（连通分量）的所有顶点。分量）的所有顶点。分量）的所有顶点。分量）的所有顶点。 若从无向图的每一个连通分量中的一个顶点出发进行遍若从无向图的每一个连通分量中的一个顶点出发进行遍若从无向图的每一个连通分量中的一个顶点出发进行遍若从无向图的每一个连通分量中的一个顶点出发进行遍历，可求得无
131、向图的所有连通分量。历，可求得无向图的所有连通分量。历，可求得无向图的所有连通分量。历，可求得无向图的所有连通分量。 在实际求连通分量的算法中，需要对图的每一个顶点进在实际求连通分量的算法中，需要对图的每一个顶点进在实际求连通分量的算法中，需要对图的每一个顶点进在实际求连通分量的算法中，需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求得的行检测：若已被访问过，则该顶点一定是落在图中已求得的行检测：若已被访问过，则该顶点一定是落在图中已求得的行检测：若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点出发遍历图，可求连通分量上；若还未被访问，则从
132、该顶点出发遍历图，可求连通分量上；若还未被访问，则从该顶点出发遍历图，可求连通分量上；若还未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量。得图的另一个连通分量。得图的另一个连通分量。得图的另一个连通分量。 非连通图有几个连通分量，就要几次调用非连通图有几个连通分量，就要几次调用非连通图有几个连通分量，就要几次调用非连通图有几个连通分量，就要几次调用DFSDFS或或或或BFSBFS才能才能才能才能访问图中所有的顶点。访问图中所有的顶点。访问图中所有的顶点。访问图中所有的顶点。连通分量连通分量 (Connected component)(Connected component)78LOG
133、Oint Undirected:LabelComponents(int L)int Undirected:LabelComponents(int L) / / 构件标识构件标识构件标识构件标识/ / 返回构件的数目，返回构件的数目，返回构件的数目，返回构件的数目， 并用并用并用并用L 1 : n L 1 : n 表示构件标号表示构件标号表示构件标号表示构件标号int n = Vertices( ) ;int n = Vertices( ) ;/ / 初始时，所有顶点都不属于任何构件初始时，所有顶点都不属于任何构件初始时，所有顶点都不属于任何构件初始时，所有顶点都不属于任何构件for (int
134、i = 1; i = n; i+)for (int i = 1; i = n; i+)Li = 0;Li = 0;int label = 0; / int label = 0; / 最后一个构件的最后一个构件的最后一个构件的最后一个构件的IDID/ / 识别构件识别构件识别构件识别构件for (int i = 1; i = n; i+)for (int i = 1; i = n; i+)if (!Li) / if (!Li) / 未到达的顶点未到达的顶点未到达的顶点未到达的顶点/ / 顶点顶点顶点顶点i i 属于一个新的构件属于一个新的构件属于一个新的构件属于一个新的构件label + +la
135、bel + + ; ;BFS(i, L, label); / BFS(i, L, label); / 标记新构件标记新构件标记新构件标记新构件return label;return label; 79LOGO 已知已知已知已知G(V,E)G(V,E)是一个无向连通图，是一个无向连通图，是一个无向连通图，是一个无向连通图，E(G)E(G)为图为图为图为图GG的边集，则从的边集，则从的边集，则从的边集，则从图中任一顶点出发遍历图时，必定将图中任一顶点出发遍历图时，必定将图中任一顶点出发遍历图时，必定将图中任一顶点出发遍历图时，必定将E(G)E(G)分成两个集合分成两个集合分成两个集合分成两个集合T
136、(G)T(G)和和和和B(G):B(G): T(G)T(G)：遍历图：遍历图：遍历图：遍历图GG时所经过的边的集合；时所经过的边的集合；时所经过的边的集合；时所经过的边的集合； B(G)B(G)：遍历图：遍历图：遍历图：遍历图GG时未经过的边的集合；时未经过的边的集合；时未经过的边的集合；时未经过的边的集合；则则则则G=(V, T)G=(V, T)称为称为称为称为GG的一棵生成树。的一棵生成树。的一棵生成树。的一棵生成树。12.11.3 12.11.3 生成树生成树 在一个无向连通图或网络中执行在一个无向连通图或网络中执行在一个无向连通图或网络中执行在一个无向连通图或网络中执行DFSDFS时，
137、到达新顶点的边正时，到达新顶点的边正时，到达新顶点的边正时，到达新顶点的边正好有好有好有好有n - 1n - 1条，这些边组成的子图也是一个生成树，用这种方法条，这些边组成的子图也是一个生成树，用这种方法条，这些边组成的子图也是一个生成树，用这种方法条，这些边组成的子图也是一个生成树，用这种方法所得到的生成树叫作所得到的生成树叫作所得到的生成树叫作所得到的生成树叫作深度优先生成树深度优先生成树深度优先生成树深度优先生成树（depth-first spanning depth-first spanning treetree）。）。）。）。80LOGO81LOGO82LOGOF FHHGGL LM
138、MI IJ JKKE EA AD DC CB Bu 例例例例83LOGOE EA AD DC CB BL LMMI IJ JKKF FHHGG非连通图的非连通图的非连通图的非连通图的深度优先深度优先深度优先深度优先生成森林生成森林生成森林生成森林84LOGOF FHHGG非连通图的非连通图的非连通图的非连通图的广度优先广度优先广度优先广度优先生成森林生成森林生成森林生成森林L LMMI IJ JKKE EA AD DC CB B85LOGO上机实习五：图的遍历上机实习五：图的遍历v以邻接表为存储结构，实现连通无向图的深度以邻接表为存储结构，实现连通无向图的深度优先和宽度优先遍历优先和宽度优先遍历 V V1 1V V2 2V V3 3V V7 7V V6 6V V5 5V V4 4V V8 886LOGOv 要求：要求：v1）构造邻接表：键盘输入点集、边集）构造邻接表：键盘输入点集、边集v2）输出邻接表，格式参照：）输出邻接表，格式参照：P374图图v3）图的深度优先遍历）图的深度优先遍历v4）图的宽度优先遍历）图的宽度优先遍历v5）图遍历时，由用户指定的起始结点，输出每种）图遍历时，由用户指定的起始结点，输出每种遍历下的结点访问序列遍历下的结点访问序列 两种做法可选：两种做法可选：1）找到书上对应类，改造完成；）找到书上对应类，改造完成；2）自己设计并实现类）自己设计并实现类87
