數(shù)據(jù)結(jié)構(gòu)圖習(xí)題

1、第8章 圖8-1 畫出1個(gè)頂點(diǎn)、2個(gè)頂點(diǎn)、3個(gè)頂點(diǎn)、4個(gè)頂點(diǎn)和5個(gè)頂點(diǎn)的無(wú)向完全圖。試證明在n個(gè)頂點(diǎn)的無(wú)向完全圖中，邊的條數(shù)為n(n-1)/2。【解答】2個(gè)頂點(diǎn)的無(wú)向完全圖1個(gè)頂點(diǎn)的無(wú)向完全圖5個(gè)頂點(diǎn)的無(wú)向完全圖4個(gè)頂點(diǎn)的無(wú)向完全圖3個(gè)頂點(diǎn)的無(wú)向完全圖【證明】在有n個(gè)頂點(diǎn)的無(wú)向完全圖中，每一個(gè)頂點(diǎn)都有一條邊與其它某一頂點(diǎn)相連，所以每一個(gè)頂點(diǎn)有n-1條邊與其他n-1個(gè)頂點(diǎn)相連，總計(jì)n個(gè)頂點(diǎn)有n(n-1)條邊。但在無(wú)向圖中，頂點(diǎn)i到頂點(diǎn)j與頂點(diǎn)j到頂點(diǎn)i是同一條邊，所以總共有n(n-1)/2條邊。DA8-2 右邊的有向圖是強(qiáng)連通的嗎？請(qǐng)列出所有的簡(jiǎn)單路徑。EB【解答】FC判斷一個(gè)有向圖是否強(qiáng)連通，

2、要看從任一頂點(diǎn)出發(fā)是否能夠回到該頂點(diǎn)。右面的有向圖做不到這一點(diǎn)，它不是強(qiáng)連通的有向圖。各個(gè)頂點(diǎn)自成強(qiáng)連通分量。所謂簡(jiǎn)單路徑是指該路徑上沒有重復(fù)的頂點(diǎn)。從頂點(diǎn)A出發(fā)，到其他的各個(gè)頂點(diǎn)的簡(jiǎn)單路徑有AB，ADB，ABC，ADBC，AD，ABE，ADE，ADBE，ABCFE，ADBCFE，ABCF，ADBCF。從頂點(diǎn)B出發(fā)，到其他各個(gè)頂點(diǎn)的簡(jiǎn)單路徑有BC，BCF，BE，BCFE。從頂點(diǎn)C出發(fā)，到其他各個(gè)頂點(diǎn)的簡(jiǎn)單路徑有CF，CFE。從頂點(diǎn)D出發(fā)，到其他各個(gè)頂點(diǎn)的簡(jiǎn)單路徑有DB，DBC，DBCF，DE，DBE，DBCFE。從頂點(diǎn)E出發(fā)，到其他各個(gè)頂點(diǎn)的簡(jiǎn)單路徑無(wú)。從頂點(diǎn)F出發(fā)，到其他各個(gè)頂點(diǎn)的簡(jiǎn)單路徑有

3、FE。8-3 給出右圖的鄰接矩陣、鄰接表和鄰接多重表表示。DA【解答】(1) 鄰接矩陣EBFC310 A1 B2 C3 D4 E5 F(2) 鄰接表42（出邊表）54140 A1 B2 C3 D4 E5 F（入邊表）30105312data fin fout(3) 鄰接多重表（十字鏈表）i j ilink jlink0 1 (A, B)0 A1 B2 C3 D4 E5 F0 3 (A, D)1 2 (B, C)1 4 (B, E)2 5 (C, F)3 1 (D, B)3 4 (D, E)5 4 (F, E)8-4 用鄰接矩陣表示圖時(shí)，若圖中有1000個(gè)頂點(diǎn)，1000條邊，則形成的鄰接矩陣有多

4、少矩陣元素？有多少非零元素？是否稀疏矩陣？【解答】一個(gè)圖中有1000個(gè)頂點(diǎn)，其鄰接矩陣中的矩陣元素有10002 = 1000000個(gè)。它有1000個(gè)非零元素（對(duì)于有向圖）或2000個(gè)非零元素（對(duì)于無(wú)向圖），因此是稀疏矩陣。8-5 用鄰接矩陣表示圖時(shí)，矩陣元素的個(gè)數(shù)與頂點(diǎn)個(gè)數(shù)是否相關(guān)？與邊的條數(shù)是否相關(guān)？【解答】用鄰接矩陣表示圖，矩陣元素的個(gè)數(shù)是頂點(diǎn)個(gè)數(shù)的平方，與邊的條數(shù)無(wú)關(guān)。矩陣中非零元素的個(gè)數(shù)與邊的條數(shù)有關(guān)。8-6 有n個(gè)頂點(diǎn)的無(wú)向連通圖至少有多少條邊？有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖至少有多少條邊？試舉例說(shuō)明?！窘獯稹縩個(gè)頂點(diǎn)的無(wú)向連通圖至少有n-1條邊，n個(gè)頂點(diǎn)的有向強(qiáng)連通圖至少有n條邊。例如：

5、特例情況是當(dāng)n = 1時(shí)，此時(shí)至少有0條邊。8-7對(duì)于有n個(gè)頂點(diǎn)的無(wú)向圖，采用鄰接矩陣表示，如何判斷以下問題： 圖中有多少條邊？任意兩個(gè)頂點(diǎn)i和j之間是否有邊相連？任意一個(gè)頂點(diǎn)的度是多少？【解答】用鄰接矩陣表示無(wú)向圖時(shí)，因?yàn)槭菍?duì)稱矩陣，對(duì)矩陣的上三角部分或下三角部分檢測(cè)一遍，統(tǒng)計(jì)其中的非零元素個(gè)數(shù)，就是圖中的邊數(shù)。如果鄰接矩陣中Aij 不為零，說(shuō)明頂點(diǎn)i與頂點(diǎn)j之間有邊相連。此外統(tǒng)計(jì)矩陣第i行或第i列的非零元素個(gè)數(shù)，就可得到頂點(diǎn)i的度數(shù)。8-8對(duì)于如右圖所示的有向圖，試寫出：(1) 從頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2) 從頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹； 【

6、解答】(1) 以頂點(diǎn)為根的深度優(yōu)先生成樹（不唯一）： 或 (2) 以頂點(diǎn)為根的廣度優(yōu)先生成樹：8-9 試擴(kuò)充深度優(yōu)先搜索算法，在遍歷圖的過(guò)程中建立生成森林的左子女-右兄弟鏈表。算法的首部為void Graph:DFS ( const int v, int visited , TreeNode<int> * t ) 其中，指針t指向生成森林上具有圖頂點(diǎn)v信息的根結(jié)點(diǎn)。（提示：在繼續(xù)按深度方向從根v的某一未訪問過(guò)的鄰接頂點(diǎn)w向下遍歷之前，建立子女結(jié)點(diǎn)。但需要判斷是作為根的第一個(gè)子女還是作為其子女的右兄弟鏈入生成樹。）【解答】為建立生成森林，需要先給出建立生成樹的算法，然后再在遍歷圖的過(guò)

7、程中，通過(guò)一次次地調(diào)用這個(gè)算法，以建立生成森林。te mplate<Type> void Graph<Type> : DFS_Tree ( const int v, int visited , TreeNode<Type> *t ) /從圖的頂點(diǎn)v出發(fā), 深度優(yōu)先遍歷圖, 建立以t (已在上層算法中建立)為根的生成樹。 Visitedv = 1; int first = 1; TreeNode<Type> * p, * q; int w = GetFirstNeighbor ( v ); /取第一個(gè)鄰接頂點(diǎn) while ( w != -1 ) /

8、若鄰接頂點(diǎn)存在 if ( vositedw = 0 ) /且該鄰接結(jié)點(diǎn)未訪問過(guò) p = new TreeNode<Type> ( GetValue (w) );/建立新的生成樹結(jié)點(diǎn) if ( first = 1 )/若根*t還未鏈入任一子女 t->setFirstChild ( p ); first = 0; /新結(jié)點(diǎn)*p成為根*t的第一個(gè)子女 else q->setNextSibling ( p );/否則新結(jié)點(diǎn)*p成為*q的下一個(gè)兄弟 q = p;/指針q總指示兄弟鏈最后一個(gè)結(jié)點(diǎn) DFS_Tree ( w, visited, q );/從*q向下建立子樹 w = G

9、etNextNeighbor ( v, w );/取頂點(diǎn)v排在鄰接頂點(diǎn)w的下一個(gè)鄰接頂點(diǎn) 下一個(gè)算法用于建立以左子女-右兄弟鏈表為存儲(chǔ)表示的生成森林。template<Type> void Graph<Type> : DFS_Forest ( Tree<Type> & T ) /從圖的頂點(diǎn)v出發(fā), 深度優(yōu)先遍歷圖, 建立以左子女-右兄弟鏈表表示的生成森林T。 T.root = NULL; int n = NumberOfVertices ( );/頂點(diǎn)個(gè)數(shù) TreeNode<Type> * p, * q; int * visited =

10、new int n ;/建立訪問標(biāo)記數(shù)組 for ( int v = 0; v < n; v+ ) visitedv = 0; for ( v = 0; v < n; v+ ) /逐個(gè)頂點(diǎn)檢測(cè) if ( visitedv = 0 ) /若尚未訪問過(guò) p = new TreeNode<Type> ( GetValue ( v ) );/建立新結(jié)點(diǎn)*p if ( T.root = NULL ) T.root = p;/原來(lái)是空的生成森林, 新結(jié)點(diǎn)成為根 else q-> setNextSibling ( p );/否則新結(jié)點(diǎn)*p成為*q的下一個(gè)兄弟 q = p; DF

11、S_Tree ( v, visited, p );/建立以*p為根的生成樹 8-10 用鄰接表表示圖時(shí)，頂點(diǎn)個(gè)數(shù)設(shè)為n，邊的條數(shù)設(shè)為e，在鄰接表上執(zhí)行有關(guān)圖的遍歷操作時(shí)，時(shí)間代價(jià)是O(n*e)？還是O(n+e)？或者是O(max(n,e)？【解答】在鄰接表上執(zhí)行圖的遍歷操作時(shí)，需要對(duì)鄰接表中所有的邊鏈表中的結(jié)點(diǎn)訪問一次，還需要對(duì)所有的頂點(diǎn)訪問一次，所以時(shí)間代價(jià)是O(n+e)。8-11 右圖是一個(gè)連通圖，請(qǐng)畫出 (1) 以頂點(diǎn)為根的深度優(yōu)先生成樹；(2) 如果有關(guān)節(jié)點(diǎn)，請(qǐng)找出所有的關(guān)節(jié)點(diǎn)。(3) 如果想把該連通圖變成重連通圖，至少在圖中加幾條邊？如何加？【解答】(1) 以頂點(diǎn)為根的深度優(yōu)先生成樹

12、：(2) 關(guān)節(jié)點(diǎn)為 ,(3) 至少加四條邊 (1, 10), (3, 4), (4, 5), (5, 6)。從的子孫結(jié)點(diǎn)到的祖先結(jié)點(diǎn)引一條邊，從的子孫結(jié)點(diǎn)到根的另一分支引一條邊，并將的子孫結(jié)點(diǎn)、與結(jié)點(diǎn)連結(jié)起來(lái)，可使其變?yōu)橹剡B通圖。8-12試證明在一個(gè)有n個(gè)頂點(diǎn)的完全圖中，生成樹的數(shù)目至少有2n-1-1?！咀C明】略71110758698-13 編寫一個(gè)完整的程序，首先定義堆和并查集的結(jié)構(gòu)類型和相關(guān)操作，再定義Kruskal求連通網(wǎng)絡(luò)的最小生成樹算法的實(shí)現(xiàn)。并以右圖為例，寫出求解過(guò)程中堆、并查集和最小生成樹的變化?！窘獯稹壳蠼膺^(guò)程的第一步是對(duì)所有的邊，按其權(quán)值大小建堆：3 4 51 2 71 2

13、71 2 72 3 102 3 102 4 92 3 101 3 111 3 11加(1, 2), (1, 3), (2,3)2 4 91 3 11加(3, 4)加(2, 4)3 4 53 4 53 5 71 2 71 2 73 5 73 6 82 3 102 4 91 3 111 3 112 3 102 4 9加(3, 5)加(3, 6)3 4 53 5 75 6 6加(5, 6)3 6 82 3 102 4 91 2 71 3 11求解過(guò)程中并查集與堆的變化：1 2 75 6 63 6 83 5 73 5 71 2 72 3 102 4 91 3 11選(5,6,6)3 6 82 3 10

14、2 4 91 3 11選(3,4,5)3 6 83 5 72 3 103 6 82 4 92 3 101 3 11選(3,5,7)2 4 91 3 11選(1,2,7)2 3 102 4 91 3 112 3 101 3 11選(2,4,9), 結(jié)束選(3,6,8), 在同一連通分量上, 不加最后得到的生成樹如下0 1 2 3 4 5 63 1 -6 3 3 5 7567并查集的存儲(chǔ)表示9完整的程序如下:#include <iostream.h>template <class Type> class MinHeap public: enum MaxHeapSize =

15、50 ; MinHeap ( int Maxsize = MaxHeapSize ); MinHeap ( Type Array , int n ); void Insert ( const Type &ele ); void RemoveMin ( Type &Min ); void Output (); private: void FilterDown ( int start, int end ); void FilterUp ( int end ); Type*pHeap; int HMaxSize; int CurrentSize;class UFSets public

16、: enum MaxUnionSize = 50 ; UFSets ( int MaxSize = MaxUnionSize ); UFSets () delete m_pParent; void Union ( int Root1, int Root2 ); int Find ( int x );private: int m_iSize; int *m_pParent;class Graph public: enum MaxVerticesNum = 50 ; Graph( int Vertices = 0) CurrentVertices = Vertices; InitGraph();

17、void InitGraph (); void Kruskal (); int GetVerticesNum () return CurrentVertices; private: int EdgeMaxVerticesNumMaxVerticesNum; int CurrentVertices;class GraphEdge public: int head, tail; int cost; int operator <= ( GraphEdge &ed );GraphEdge : operator <= ( GraphEdge &ed ) return this

18、->cost <= ed.cost;UFSets : UFSets ( int MaxSize ) m_iSize = MaxSize; m_pParent = new intm_iSize; for ( int i = 0; i < m_iSize; i+ ) m_pParenti = -1;void UFSets : Union ( int Root1, int Root2 ) m_pParentRoot2 = Root1;int UFSets : Find ( int x ) while ( m_pParentx >= 0 ) x = m_pParentx; re

19、turn x;template <class Type> MinHeap<Type> : MinHeap ( int Maxsize ) HMaxSize = Maxsize; pHeap = new TypeHMaxSize; CurrentSize = -1;template <class Type> MinHeap<Type> : MinHeap ( Type Array, int n ) HMaxSize = ( n < MaxHeapSize ) ? MaxHeapSize : n; pHeap = new TypeHMaxSiz

20、e; for ( int i = 0; i < n; i+ ) pHeapi = Arrayi; CurrentSize = n-1; int iPos = ( CurrentSize - 1 ) / 2; while ( iPos >= 0 ) FilterDown ( iPos, CurrentSize ); iPos-; template <class Type> void MinHeap<Type> : FilterDown ( int start, int end ) int i = start, j = 2 * start + 1; Type T

21、emp = pHeapi; while ( j <= end ) if ( j < end && pHeapj+1 <= pHeapj ) j+; if ( Temp <= pHeapj ) break; pHeapi = pHeapj; i = j; j = 2 * j + 1; pHeapi = Temp;template <class Type> void MinHeap<Type> : FilterUp ( int end ) int i = end, j = ( end - 1 ) / 2; Type Temp = pH

22、eapi; while ( i > 0 ) if ( pHeapj <= Temp ) break; pHeapi = pHeapj; i = j; j = ( j - 1 ) / 2; pHeapi = Temp;template <class Type> void MinHeap<Type> : Insert ( const Type &ele ) CurrentSize+; if ( CurrentSize = HMaxSize ) return; pHeapCurrentSize = ele; FilterUp ( CurrentSize )

23、;template <class Type> void MinHeap<Type> : RemoveMin ( Type &Min ) if ( CurrentSize < 0 ) return; Min = pHeap0; pHeap0 = pHeapCurrentSize-; FilterDown ( 0, CurrentSize );template <class Type> void MinHeap<Type> : Output ( ) for ( int i = 0; i <= CurrentSize; i+ ) c

24、out << pHeapi << " " cout << endl;void Graph : InitGraph( ) Edge00 = -1; Edge01 = 28; Edge02 = -1; Edge03 = -1; Edge04 = -1; Edge05 = 10; Edge06 = -1; Edge11 = -1; Edge12 = 16; Edge13 = -1; Edge14 = -1; Edge15 = -1; Edge16 = 14; Edge22 = -1; Edge23 = 12; Edge24 = -1; Edge

25、25 = -1; Edge26 = -1; Edge33 = -1; Edge34 = 22; Edge35 = -1; Edge36 = 18; Edge44 = -1; Edge45 = 25; Edge46 = 24; Edge55 = -1; Edge56 = -1; Edge66 = -1; for ( int i = 1; i < 6; i+ ) for ( int j = 0; j < i; j + ) Edgeij = Edgeji;void Graph : Kruskal( ) GraphEdge e; int VerticesNum = GetVerticesN

26、um ( ); int i, j, count; MinHeap<GraphEdge> heap ( VerticesNum *VerticesNum ); UFSets set ( VerticesNum ); for ( i = 0; i < VerticesNum; i+ ) for ( j = i + 1; j < VerticesNum; j+ ) if ( Edgeij > 0 ) e.head = i; e.tail = j; e.cost = Edgeij;heap.Insert ( e ); count = 1; while ( count &l

27、t; VerticesNum ) heap.RemoveMin ( e ); i = set.Find ( e.head ); j = set.Find ( e.tail ); if ( i != j ) set.Union ( i, j );count+;cout << "( " << e.head << ", " << e.tail << ", " <<e.cost << " )" << endl; 8-14 利用D

28、ijkstra算法的思想，設(shè)計(jì)一個(gè)求最小生成樹的算法。【解答】計(jì)算連通網(wǎng)絡(luò)的最小生成樹的Dijkstra算法可描述如下：將連通網(wǎng)絡(luò)中所有的邊以方便的次序逐步加入到初始為空的生成樹的邊集合T中。每次選擇并加入一條邊時(shí)，需要判斷它是否會(huì)與先前加入T的邊構(gòu)成回路。如果構(gòu)成了回路，則從這個(gè)回路中將權(quán)值最大的邊退選。 下面以鄰接矩陣作為連通網(wǎng)絡(luò)的存儲(chǔ)表示，并以并查集作為判斷是否出現(xiàn)回路的工具，分析算法的執(zhí)行過(guò)程。165192192614611181616´215211419149并查集, 表明4個(gè)結(jié)點(diǎn)在同一連通分量上1616´5195´1914914116616最終得到的最

29、小生成樹為561411實(shí)現(xiàn)算法的過(guò)程為const int MaxNum = 10000;void Graph : Dijkstra ( ) GraphEdge e; int VerticesNum = GetVerticesNum ( ); int i, j, p, q, k; int disJointVerticesNum;/并查集 for ( i = 0; i < VerticesNum; i+ ) disJointi = -1; /并查集初始化 for ( i = 0; i < VerticesNum-1; i+ )/檢查所有的邊 for ( j = i + 1; j <

30、; VerticesNum; j+ ) if ( Edgeij < MaxNum ) /邊存在 p = i; q = j;/判結(jié)點(diǎn)i與j是否在同一連通分量上 while ( disJointp >= 0 ) p = disJointp; while ( disJointq >= 0 ) p = disJointq; if ( p != q ) disJointj = i;/ i與j不在同一連通分量上, 連通之 else / i與j在同一連通分量上 p = i;/尋找離結(jié)點(diǎn)i與j最近的祖先結(jié)點(diǎn) while ( disJointp >= 0 ) /每變動(dòng)一個(gè)p, 就對(duì)q到根

31、的路徑檢測(cè)一遍 q = j; while ( disJointq >= 0 && disJointq = disJointp )q = disJointq; if ( disJointq = disJointp ) break; else p = disJointp; k = disJointp;/結(jié)點(diǎn)k是i和j的最近的共同祖先 p = i; q = disJointp; max = -MaxNum;/從i到k找權(quán)值最大的邊(s1, s2) while ( q <= k ) if ( Edgeqp > max ) max = Edgeqp; s1 = p; s

32、2 = q; p =q; q = disJointp; p = j; q = disJointp; max = -MaxNum;/從j到k找權(quán)值最大的邊(t1, t2) while ( q <= k ) if ( Edgeqp > max ) max = Edgeqp; t1 = p; t2 = q; p =q; q = disJointp; max = Edgeij; k1 = i; k2 = j; if ( max < Edges1s2 ) max = Edges1s2; k1 = s1; k2 = s2; if ( max < Edget1t2 ) max = E

33、dget1t2; k1 = t1; k2 = t2; if ( max != Edgeij ) /當(dāng)Edgeij = max時(shí)邊不改 if ( disJointk1 = k2 ) disJointk1 = -1; else disJointk2 = -1;/刪除權(quán)值最大的邊 disJointj = i;/加入新的邊 Edgeji = - Edgeji; 8-15以右圖為例，按Dijkstra算法計(jì)算得到的從頂點(diǎn)(A)到其它各個(gè)頂點(diǎn)的最短路徑和最短路徑長(zhǎng)度。A1810【解答】源點(diǎn)終點(diǎn)最短路徑最短路徑長(zhǎng)度CB5 A B(A,B)(A,B)(A,B)(A,B)10101010225 C(A,C)(A

34、,C)(A,C)(A,C)18181818 D ¾(A,B,D)(A,B,D)(A,B,D)¥151515ED2 E ¾¾(A,B,D,E)(A,B,D,E)¥¥17178-16 在以下假設(shè)下，重寫Dijkstra算法：(1) 用鄰接表表示帶權(quán)有向圖G，其中每個(gè)邊結(jié)點(diǎn)有3個(gè)域：鄰接頂點(diǎn)vertex，邊上的權(quán)值length和邊鏈表的鏈接指針link。(2) 用集合T = V(G) - S代替S (已找到最短路徑的頂點(diǎn)集合)，利用鏈表來(lái)表示集合T。試比較新算法與原來(lái)的算法，計(jì)算時(shí)間是快了還是慢了，給出定量的比較?！窘獯稹?1) 用鄰接表表

35、示的帶權(quán)有向圖的類定義：const int DefaultSize = 10;/缺省頂點(diǎn)個(gè)數(shù)class Graph;/圖的前視類定義struct Edge /邊的定義friend class Graph; int vertex;/邊的另一頂點(diǎn)位置 float length;/邊上的權(quán)值 Edge *link;/下一條邊鏈指針 Edge ( ) /構(gòu)造函數(shù) Edge ( int num, float wh ) : vertex (num), length (wh), link (NULL) /構(gòu)造函數(shù) int operator < ( const Edge & E ) const

36、return length != E.length; /判邊上權(quán)值小否struct Vertex /頂點(diǎn)的定義friend class Graph; char data;/頂點(diǎn)的名字 Edge *adj;/邊鏈表的頭指針class Graph /圖的類定義private: Vertex *NodeTable;/頂點(diǎn)表 (各邊鏈表的頭結(jié)點(diǎn)) int NumVertices;/當(dāng)前頂點(diǎn)個(gè)數(shù) int NumEdges;/當(dāng)前邊數(shù) int GetVertexPos ( const Type vertex );/給出頂點(diǎn)vertex在圖中的位置public: Graph ( int sz );/構(gòu)造函數(shù)

37、 Graph ( );/析構(gòu)函數(shù) int NumberOfVertices ( ) return NumVertices; /返回圖的頂點(diǎn)數(shù) int NumberOfEdges ( ) return NumEdges; /返回圖的邊數(shù) char GetValue ( int i )/取位置為i的頂點(diǎn)中的值 return i >= 0 && i < NumVertices ? NodeTablei.data : ; float GetWeight ( int v1, int v2 );/返回邊(v1, v2)上的權(quán)值 int GetFirstNeighbor ( in

38、t v );/取頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn) int GetNextNeighbor ( int v, int w );/取頂點(diǎn)v的鄰接頂點(diǎn)w的下一個(gè)鄰接頂點(diǎn)(2) 用集合T = V(G) - S代替S (已找到最短路徑的頂點(diǎn)集合)，利用鏈表來(lái)表示集合T。 8-17 試證明：對(duì)于一個(gè)無(wú)向圖G = (V, E)，若G中各頂點(diǎn)的度均大于或等于2，則G中必有回路。【解答】反證法：對(duì)于一個(gè)無(wú)向圖G=（V，E），若G中各頂點(diǎn)的度均大于或等于2，則G中沒有回路。此時(shí)從某一個(gè)頂點(diǎn)出發(fā)，應(yīng)能按拓?fù)溆行虻捻樞虮闅v圖中所有頂點(diǎn)。但當(dāng)遍歷到該頂點(diǎn)的另一鄰接頂點(diǎn)時(shí)，又可能回到該頂點(diǎn)，沒有回路的假設(shè)不成立。8-18 設(shè)有一個(gè)

39、有向圖存儲(chǔ)在鄰接表中。試設(shè)計(jì)一個(gè)算法，按深度優(yōu)先搜索策略對(duì)其進(jìn)行拓?fù)渑判?。并以右圖為例檢驗(yàn)?zāi)愕乃惴ǖ恼_性。【解答】(1) 利用題8-16定義的鄰接表結(jié)構(gòu)。增加兩個(gè)輔助數(shù)組和一個(gè)工作變量：w 記錄各頂點(diǎn)入度 int indegreeNumVertices。w 記錄各頂點(diǎn)訪問順序 int visitedNumVertices，初始時(shí)讓visitedi = 0, i = 1, 2, ¼, NumVertices。w 訪問計(jì)數(shù)int count，初始時(shí)為0。(2) 拓?fù)渑判蛩惴╲oid Graph : dfs ( int visited , int indegree , int v, in

40、t & count ) count+; visitedv = count; cout << NodeTablev.data << endl; Edge *p = NodeTablev.adj; while ( p != NULL ) int w = p->vertex; indegreew-; if ( visitedw = 0 && indegreew = 0 ) dfs ( visited, indegree, w, count ); p = p->link; 主程序int i, j; Edge *p; float w;cin >> NumVertices;int * visited = new intNumVertices+1;int * indegree = new intNumVertices+1;for ( i = 1; i <= NumVertices; i+ ) NodeTablei.adj = NULL; cin >> NodeTablei.data; cout << endl; visitedi = 0; indegreei = 0; int