1、7.2 7.2 圖的存儲結構圖的存儲結構n圖的數組圖的數組( (鄰接矩陣鄰接矩陣) )存儲表示存儲表示n圖的鄰接表存儲表示圖的鄰接表存儲表示n有向圖的十字鏈表存儲表示有向圖的十字鏈表存儲表示n無向圖的鄰接多重表存儲表示無向圖的鄰接多重表存儲表示鄰接矩陣是用于描述圖中頂點之間關系鄰接矩陣是用于描述圖中頂點之間關系( (即弧或邊即弧或邊的權的權) )的矩陣。的矩陣。 鄰接表類似樹的孩子鏈表。即對圖中的每個頂點鄰接表類似樹的孩子鏈表。即對圖中的每個頂點vivi建立一個單鏈表，表中結點表示依附于該頂點建立一個單鏈表，表中結點表示依附于該頂點vivi的的邊或弧。邊或弧。鄰接點域鄰接點域鏈域鏈域數據域數據

2、域數據域數據域鏈域鏈域表結點表結點表頭結點表頭結點V1V3V2V4例：例： 4 3 2 1211134423.3.有向圖的十字鏈表存儲表示有向圖的十字鏈表存儲表示兩種結點結構：兩種結點結構：尾域尾域tailvextailvex頭域頭域headvexheadvex鏈域鏈域hlinkhlink鏈域鏈域tlinktlink信息域信息域infoinfo數據域數據域datadata鏈域鏈域firstinfirstin鏈域鏈域firstoutfirstout頂點結點頂點結點弧結點弧結點v1v1v2v2v3v3v4v4 0 1 2 3 10/20v3v1 v4v2 /03/13/2302/32例：例：dat

3、adatafirstinfirstinfirstoutfirstouttailvexheadvex hlinktlink/標志域標志域邊頂點邊頂點i i邊頂點邊頂點j j鏈域鏈域i i 鏈域鏈域j j 信息域信息域數據域數據域邊鏈域邊鏈域4.4.無向圖的鄰接多重表存儲表示無向圖的鄰接多重表存儲表示邊結點邊結點頂點結點頂點結點1 3 4 2 例：例：1234121324第第7 7章章 圖圖7.1 7.1 圖的定義和術語圖的定義和術語7.2 7.2 圖的存儲結構圖的存儲結構7.3 7.3 圖的遍歷圖的遍歷7.4 7.4 圖的連通性問題圖的連通性問題7.5 7.5 有向無環(huán)圖及其應用有向無環(huán)圖及其應

4、用7.6 7.6 最短路徑最短路徑7.3 7.3 圖的遍歷圖的遍歷 從圖中某一頂點出發(fā)訪遍圖中其余頂點，且使每一個頂點僅被訪問一次。這一過程從圖中某一頂點出發(fā)訪遍圖中其余頂點，且使每一個頂點僅被訪問一次。這一過程就叫做圖的遍歷。就叫做圖的遍歷。 通常有兩條遍歷圖的路徑：通常有兩條遍歷圖的路徑：深度優(yōu)先搜索深度優(yōu)先搜索廣度優(yōu)先搜索廣度優(yōu)先搜索1.1.深度優(yōu)先搜索深度優(yōu)先搜索(DFS)(DFS)基本思想：基本思想： 從圖中某頂點從圖中某頂點V0V0出發(fā)，訪問此頂點，然后依次出發(fā)，訪問此頂點，然后依次從從V0V0的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖，直

5、至圖中所有和歷圖，直至圖中所有和V0V0有路徑相通的頂點都被訪有路徑相通的頂點都被訪問到；問到； 若此時圖中尚有頂點未被訪問，則另選圖中一若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點；個未曾被訪問的頂點作起始點； 重復上述過程，直至圖中所有頂點都被訪問到重復上述過程，直至圖中所有頂點都被訪問到為止。為止。 例：從頂點例：從頂點v1v1出發(fā)，出發(fā)，DFSDFS下圖。下圖。頂點訪問序列為：頂點訪問序列為：v1,v2,v4,v8,v5,v3,v6,v7v1,v2,v4,v8,v5,v3,v6,v7v1v1v6v6v2v2v5v5v3v3v8v8v4v4v7v7圖的圖的DFS算法

6、一般描述算法一般描述int visitedMAXVEX; /訪問標志數組訪問標志數組void DFSgraph(Graph G, Visit() /對圖對圖G作深度優(yōu)先遍歷作深度優(yōu)先遍歷 for( v=0; vG.vexnum; +v ) visitedv=FALSE; /訪問標志數組初始化訪問標志數組初始化 for( v=0; v=0; w=NextAdjVex(G,v,w)for(w=FirstAdjVex(G,v); w=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS(G,w); if (!visitedw) DFS(G,w); / /對對v v的尚未

7、訪問的鄰接頂點的尚未訪問的鄰接頂點w w遞歸調用遞歸調用DFS DFS 用鄰接表實現(xiàn)圖的深度優(yōu)先搜索用鄰接表實現(xiàn)圖的深度優(yōu)先搜索v1v1v6v6v2v2v5v5v3v3v8v8v4v4v7v7v9v9v10v1012345678 2 8 2 8 3 7 3 6 4 5 2 3 2 3 1 6 7 1 4 5910 9 / 10 /分析：分析： 在遍歷圖時，對圖中每個頂點至多調用一次在遍歷圖時，對圖中每個頂點至多調用一次DFSDFS函數，因為一旦某個頂點被標志成已被訪問，函數，因為一旦某個頂點被標志成已被訪問，就不再從它出發(fā)進行搜索。就不再從它出發(fā)進行搜索。 因此，遍歷圖的過程實質上是對每個頂點

8、查因此，遍歷圖的過程實質上是對每個頂點查找其鄰接點的過程。其耗費的時間則取決于所采找其鄰接點的過程。其耗費的時間則取決于所采用的存儲結構。用的存儲結構。 2.2.廣度優(yōu)先搜索廣度優(yōu)先搜索(BFS)(BFS)基本思想：基本思想： 從圖中某個頂點從圖中某個頂點V0V0出發(fā)，并在訪問此頂點后依出發(fā)，并在訪問此頂點后依次訪問次訪問V0V0的所有未被訪問過的鄰接點，之后按這些的所有未被訪問過的鄰接點，之后按這些頂點被訪問的先后次序依次訪問它們的鄰接點，直頂點被訪問的先后次序依次訪問它們的鄰接點，直至圖中所有和至圖中所有和V0V0有路徑相通的頂點都被訪問到；有路徑相通的頂點都被訪問到； 若此時圖中尚有頂點

9、未被訪問，則另選圖中一若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點；個未曾被訪問的頂點作起始點； 重復上述過程，直至圖中所有頂點都被訪問到重復上述過程，直至圖中所有頂點都被訪問到為止。為止。 例：從頂點例：從頂點v1v1出發(fā)，出發(fā)，BFSBFS下圖。下圖。頂點訪問序列為：頂點訪問序列為：v1,v2,v3,v4,v5,v6,v7,v8v1,v2,v3,v4,v5,v6,v7,v8v1v1v6v6v2v2v5v5v3v3v8v8v4v4v7v7用鄰接表實現(xiàn)圖的廣度優(yōu)先搜索用鄰接表實現(xiàn)圖的廣度優(yōu)先搜索12345678 2 8 2 8 3 7 3 6 4 5 2 3 2 3 1

10、6 7 1 4 5v1v1v6v6v2v2v5v5v3v3v8v8v4v4v7v7BFSBFS非遞歸算法非遞歸算法void BFSTraverse(Graph G, Status (void BFSTraverse(Graph G, Status (* *Visit)(int v)Visit)(int v)/使用輔助隊列使用輔助隊列Q Q和訪問標志數組和訪問標志數組visitedv visitedv for (v=0; vG.vexnum; +v) visitedv = FALSE; for (v=0; vG.vexnum; +v) visitedv = FALSE; InitQueue(Q)

11、; / InitQueue(Q); / 置空的輔助隊列置空的輔助隊列Q Q for ( v=0; vG.vexnum; +v ) for ( v=0; v=0;w=NextAdjVex(G,u,w)(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w)） if ( ! visitedw) if ( ! visitedw) /w /w為為u u的尚未訪問的鄰接頂點的尚未訪問的鄰接頂點 visitedw = TRUE; Visit(w);visitedw = TRUE; Visit(w); EnQueue(Q, w); EnQueue(Q, w); /if /if

12、/while /while if if / BFSTraverse / BFSTraverse分析：分析： 每個頂點至多進一次隊列。遍歷圖的過程實每個頂點至多進一次隊列。遍歷圖的過程實質上是通過邊或弧找鄰接點的過程，因此廣度優(yōu)質上是通過邊或弧找鄰接點的過程，因此廣度優(yōu)先搜索遍歷圖的時間復雜度和深度優(yōu)先搜索遍歷先搜索遍歷圖的時間復雜度和深度優(yōu)先搜索遍歷相同，兩者不同之處僅僅在于對頂點訪問的順序相同，兩者不同之處僅僅在于對頂點訪問的順序不同。不同。 第第7 7章章 圖圖7.1 7.1 圖的定義和術語圖的定義和術語7.2 7.2 圖的存儲結構圖的存儲結構7.3 7.3 圖的遍歷圖的遍歷7.4 7.4

13、 圖的連通性問題圖的連通性問題7.5 7.5 有向無環(huán)圖及其應用有向無環(huán)圖及其應用7.6 7.6 最短路徑最短路徑7.4 7.4 圖的連通性問題圖的連通性問題1 1無向圖的連通分量和生成樹無向圖的連通分量和生成樹2 2最小生成樹最小生成樹3 3普里姆算法普里姆算法4 4克魯斯卡爾算法克魯斯卡爾算法1.1.無向圖的連通分量和生成樹無向圖的連通分量和生成樹基本概念基本概念連通分量的頂點集：即從該連通分量連通分量的頂點集：即從該連通分量的某一頂點出發(fā)進行搜索所得到的頂的某一頂點出發(fā)進行搜索所得到的頂點訪問序列；點訪問序列；生成樹：某連通分量的極小連通子圖；生成樹：某連通分量的極小連通子圖；生成森林：

14、非連通圖的各個連通分量生成森林：非連通圖的各個連通分量的極小連通子圖構成的集合。的極小連通子圖構成的集合。 設設E(G)E(G)為連通子圖為連通子圖G G中所有邊的集合，則從圖中所有邊的集合，則從圖中任一頂點出發(fā)遍歷圖時，必定將中任一頂點出發(fā)遍歷圖時，必定將E(G)E(G)分成兩個分成兩個集合集合T(G)T(G)和和B(G)B(G)，其中，其中T(G)T(G)是遍歷過程中歷經的是遍歷過程中歷經的邊的集合。顯然，邊的集合。顯然，T(G)T(G)和圖和圖G G中所有頂點一起構中所有頂點一起構成連通圖成連通圖G G的極小連通子圖，按照的極小連通子圖，按照7.17.1節(jié)的定義，節(jié)的定義，它是連通圖的一

15、棵生成樹，并且稱由深度優(yōu)先搜它是連通圖的一棵生成樹，并且稱由深度優(yōu)先搜索得到的為深度優(yōu)先生成樹；由廣度優(yōu)先搜索得索得到的為深度優(yōu)先生成樹；由廣度優(yōu)先搜索得到的為廣度優(yōu)先生成樹。到的為廣度優(yōu)先生成樹。例：求下圖的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。例：求下圖的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。v1v1v6v6v2v2v5v5v3v3v8v8v4v4v7v7 對非連通圖，每個連通分量中的頂點集和遍對非連通圖，每個連通分量中的頂點集和遍歷時走過的邊一起構成若干棵生成樹，這些連通歷時走過的邊一起構成若干棵生成樹，這些連通分量的生成樹組成非連通圖的生成森林。分量的生成樹組成非連通圖的生成森林。例：例：生成非連

16、通圖的深度優(yōu)先生成森林的算法生成非連通圖的深度優(yōu)先生成森林的算法void DFSForest (Graph Gvoid DFSForest (Graph G，CSTree &T) CSTree &T) /建立無向圖建立無向圖G G的深度優(yōu)先生成森林的的深度優(yōu)先生成森林的( (左左) )孩子孩子( (右右) )兄弟鏈表兄弟鏈表T T。 T=NULLT=NULL； for( v=0for( v=0； vG.vexnumvG.vexnum； +v) visitedv=FALSE+v) visitedv=FALSE； for( v=0for( v=0；vG.vexnumvnextsib

17、ling = p ; else qnextsibling = p ; / /是其它生成樹的根是其它生成樹的根( (前一棵的根的前一棵的根的“兄弟兄弟”) ) q = p; /q q = p; /q指示當前生成樹的根指示當前生成樹的根 DFSTree(G,v,p); /DFSTree(G,v,p); /建立以建立以p p為根的生成樹為根的生成樹 /DFSForest/DFSForestvoid DFSTree (Graph Gvoid DFSTree (Graph G，int vint v，CSTree &T) CSTree &T) /從第從第v v個頂點出發(fā)深度優(yōu)先遍歷圖個頂點

18、出發(fā)深度優(yōu)先遍歷圖Q Q，建立以，建立以T T為根的生成樹。為根的生成樹。 visitedv=TRUEvisitedv=TRUE； first=TRUEfirst=TRUE； for(w=FisrtAdjVex(G,v); w=0; w=NextAdjVex(G, v, w)for(w=FisrtAdjVex(G,v); w=0; w=NextAdjVex(G, v, w) if(!visitedw) if(!visitedw) p=(CSTree)malloc(sizeof(CSNode); / p=(CSTree)malloc(sizeof(CSNode); /分配孩子結點分配孩子結點 * *p=GetVex(G,w)p=GetVex(G,w)，NULLNULL，NULLNULL； if(first) /wif(first) /w是是v v的第一個未被訪問的鄰接頂點的第一個未被訪問的鄰接頂