圖的基本概念和主要結(jié)構(gòu)

1、圖的基本概念和主要結(jié)構(gòu)內(nèi)容提要1、圖的基本概念2、圖的存儲結(jié)構(gòu) 包括圖的鄰接矩陣表示和鄰接表表示法及其實現(xiàn)3、圖的遍歷：深度優(yōu)先和寬度優(yōu)先遍歷4、最小代價生成樹：普里姆算法10.1 圖的基本概念 與線性表、樹和集合不同，在圖結(jié)構(gòu)中，每個數(shù)據(jù)元素都可以與任何其它數(shù)據(jù)元素相關(guān)。圖在許多方面都有所應(yīng)用。課堂提要第10章 圖10.1 圖的基本概念10.2 圖的存儲結(jié)構(gòu)10.3 圖的遍歷10.5 最小代價生成 樹n1 L1 n2 C2 n3 L2 n4R1 C2 C3 R2n5(b) (a)的圖表示(a) 電路示例圖10-1 電路示例及對應(yīng)的圖表示n1R1V1L1n2C2n3L2n4C2R2C3n5圖(

2、graph)：是數(shù)據(jù)結(jié)構(gòu) G=(V,E)，其中V(G)是G中結(jié)點的有限非空集合,結(jié)點的偶對稱為邊(edge)；E(G)是G中邊的有限集合。圖中的結(jié)點又稱為頂點(vertex)。10.1.1 圖的定義與術(shù)語10234(a)圖G1圖中 :V(G1)=0,1,2,3,4E(G1)=(0,1),(0,2),(0,4),(1,2),(2,3),(2,4),(3,4)有向圖(directed graph)：指圖中代表邊的偶對是有序的。用代表一條有向邊（又稱為弧），則u稱為該邊的始點（尾），v稱為邊的終點（頭）。無向圖(undirected graph)：指圖中代表邊的偶對是無序的 在無向圖中邊(u，v )

3、和(v，u)是同一條邊。10234(b)有向圖G210234(a)無向圖G11023410234(a)無向圖G1(b)有向圖G2圖中 V(G1)=V(G2)=0,1,2,3,4E(G1)=(0,1),(0,2),(0,4),(1,2),(2,3),(2,4),(3,4)E(G2)=,自回路：如果圖中存在無向邊(u,u)或有向邊， 則稱這樣的邊為自回路。多重圖：指圖中兩個頂點間允許有多條相同的邊。自回路和多重圖的例子10231023(b)多重圖 (a)自回路 鄰接:如果(u,v)是無向圖中的一條邊，則稱頂點u和v相鄰接，并稱邊(u,v)與頂點u和v相關(guān)聯(lián)。例如：頂點1和2是相鄰接的。完全圖：如果

4、一個圖有最多的邊數(shù)，稱為完全圖。無向完全圖有n(n-1)/2條邊，有向完全圖有n(n-1)條邊。例如：左圖是一個完全圖。有6條邊。 無向完全圖 0123 如果是有向圖中的一條邊，則稱頂點u鄰接到v；稱頂點v鄰接自u ,并稱邊與頂點u和v相關(guān)聯(lián)。子圖：圖G的一個子圖是圖G=(V,E)，其中V(G)V(G), E(G)E(G).1024圖G1的子圖10234圖G2的子圖1023410234G1G2路徑：在無向圖G中，一條從s到t的路徑是存在一個頂點序 列(s,v1,v2,vk,t),使得(s,v1),(v1,v2),(vk,t) 都是圖G中的邊。 對于有向圖頂點序列s,v1,v2,vk,t,應(yīng)使,

5、 ,都是圖G中的邊。路徑長度: 指路徑上邊的數(shù)目。簡單路徑: 除起點和終點可以相同外，路徑上其余頂點各不相同?；芈? 起點和終點相同的簡單路徑。 1023410234G1G2(0,1,2,3)；(0,1,2,3,4,2,0)；(0,1,2,3,4,0)都是路徑，它們的路徑長度分別為3,6,5。其中(0,1,2,3)和(0,1,2,3,4,0)是簡單路徑， (0,1,2,3,4,0)又是回路。 無向圖中如果兩個頂點u和v之間存在一條路徑，則稱頂點u和v是連通的，否則是不連通的。連通圖:無向圖中如果任意兩個頂點之間是連通的。連通分量:無向圖的極大連通子圖。10234 0和3是連通的。實際上該圖任意

6、兩個頂點都是連通的，故該圖是連通圖。10234651023465 0和6是不連通的。該圖是非連通圖，但它存在兩個連通分量。注意極大的含義：如果某個連通子圖再加上一個頂點后，仍然是連通的，則它不是連通分量。31024強連通圖：有向圖中如果任意兩個頂點u和v之間，存在一條從u到v的路徑，同時存在一條從v到u的路徑，則稱該有向圖為強連通圖。強連通分量：有向圖的極大強連通子圖。10234102341023434102410233102例如左圖中，頂點1,2度分別為2和4。 右圖中，頂點0的入度和出度分別為3和1，頂點0的度為41023410234頂點2的入度和出度分別為？頂點的度：與該頂點相關(guān)聯(lián)的邊的

7、數(shù)目。入度：有向圖中頂點v的入度指以v為頭的弧的數(shù)目；出度：有向圖中頂點v的出度指以v為尾的弧的數(shù)目。 有向圖中，頂點的度=入度+出度。生成樹：無向圖的生成樹是一個極小連通子圖，它包含圖中所有頂點，但只有足以構(gòu)成一棵樹的(n-1)條邊。去掉一條就不連通，再加上一條邊將構(gòu)成回路。有向圖的生成森林：是一個子圖，由若干棵互不相交的有根有向樹組成，包含圖中所有的頂點。10234圖G1的生成樹10234圖G1有根有向樹：是一個有向圖，它恰有一個頂點的入度為0，其余頂點的入度為1。如果略去邊的方向，處理成無向圖后，則圖是連通的。網(wǎng)：在圖的每條邊上加上一個數(shù)字稱為權(quán)，也稱代價, 帶權(quán)的圖稱為網(wǎng)。10234有

8、向無環(huán)圖（DAG圖）：不包含回路的有向圖。自由樹：不包含回路的連通圖。10234102342386254ADT 101 Graph 數(shù)據(jù)： 頂點的非空集合V和邊的集合E，每條邊由V中頂點的偶對表示。運算： void CreateGraph( Graph* g, int n, T noedge ) 后置條件: 已構(gòu)造一個只有n個結(jié)點，不包含任何邊的有向圖。BOOL Add( Graph *g, int u, int v, T w) 后置條件: 向圖中添加權(quán)值為w(若邊上沒有權(quán)，則w0)的邊，若插入成功，則函數(shù)返回TRUE，否則返回FALSE。BOOL Delete( Graph *g, int

9、u, int v) 后置條件：從圖中刪除邊，若刪除成功，則函數(shù)返回TRUE，否則返回FALSE。BOOL Exist( Graph g, int u, int v) 后置條件：如果圖中存在邊，則函數(shù)返回TRUE，否則返回FALSE。 int Vertices Graph g) 后置條件：函數(shù)返回圖中頂點數(shù)目。 上面列出的只是圖的最基本的運算。在以后的各小節(jié)中，我們將通過添加新運算，陸續(xù)擴充ADT 101 的圖抽象數(shù)據(jù)類型。主要包括以下圖運算： (1) 深度優(yōu)先搜索圖：void DFS(Graph g)； (2) 寬度優(yōu)先搜索圖：void BFS(Graph g)； (3) 拓?fù)渑判颍簐oid

10、TopoSort(Graph g)； (4) 關(guān)鍵路徑：void CriticalPath(Graph g)； (5) 普里姆算法求最小代價生成樹：void Prim(Graph g，int k)； (6) 克魯斯卡爾算法求最小代價生成樹：void Kruskal(Graph g，int edges)； (7) 迪杰斯特拉算法求單源最短路徑：void Dijkstra(Graph g，int k, T d, int p)；(8) 弗洛伊德算法求所有頂點之間的最短路徑：void Floyd(Graph g，T*&d, int *&path)。1、圖的矩陣表示法及其實現(xiàn)2、圖的鄰接表表示法及其實現(xiàn)

11、10.2 圖的存儲結(jié)構(gòu)10.2.1 圖的矩陣表示法1、鄰接矩陣 一個有n個頂點的圖G=(V,E)的鄰接矩陣是一個nn的矩陣A，A的每個元素是0或1。課堂提要第10章 圖10.1 圖的基本概念10.2 圖的存儲結(jié)構(gòu)10.3 圖的遍歷10.5 最小代價生成 樹 設(shè)V=0,1,2,n-1,如果G是無向圖，則A的元素定義為：如果G是有向圖，則A的元素定義為： 1 (u,v)E或(v,u)E Auv= 0 其它 1 E Auv= 0 其它如果G是帶權(quán)的有向圖(網(wǎng))，那么A中的元素定義如下：(e) 圖G2的鄰接矩陣 0 1 2 30 0 0 0 01 1 0 1 02 0 0 0 13 1 1 0 0(b

12、) 有向圖G20132(c) 網(wǎng)G30132 1 1 5 43 0 1 2 30 0 1 4 0 5 2 0 33 1 1 0(f) 網(wǎng)G3的鄰接矩陣0132(a) 無向圖G1(d) 圖G1的鄰接矩陣 0 1 2 30 0 1 0 11 1 0 1 12 0 1 0 13 1 1 1 0圖 10.7 圖的鄰接矩陣0鄰接矩陣?yán)纾?1245312453450123451230如果G是有向圖，則A的元素定義為： 1 E Auv= 0 其它111111110000000000000000000000000000強連通分量1、鄰接矩陣C語言定義10.2.2 圖的鄰接矩陣實現(xiàn)typedef struct

13、 graph T NoEdge; /兩結(jié)點間無邊時的值(0或) int Vertices; /圖中頂點數(shù) T* A; /指向存儲鄰接矩陣的二維數(shù)組的指針 Graph;建立鄰接矩陣（ 【程序101】 ）。 void CreateGraph(Graph* g, int n, T noedge ) int i, j; g-NoEdge=noedge; g-Vertices=n; g-A=(T*)malloc(n*sizeof(T*); for(i=0; iAi=(T*)malloc(n*sizeof(T); for (j=0; jAij=noedge; g-Aii=0; -11nna-1101nan

14、ajia-11na11a01a-10na10a00aLOMMOLL0000noedgenoedgenoedgenoedgenoedgenoedgeBOOL Exist(Graph g, int u,int v) if(u0|vn-1|vn-1|u=v|auv=noEdge) return false; return true;3、邊的搜索、插入和刪除0132 0 1 2 30 0 0 0 01 1 0 1 02 0 0 0 13 1 1 0 0/判邊是否存在3,1是否有邊？1,3是否有邊？有邊!無邊!BOOL Add(Graph *g, int u, int v, T w) int n=g-V

15、ertices; if(u0 | vn-1 | vn-1 | u=v | g-Auv!=g-NoEdge) printf(BadInputn); return FALSE; g-Auv=w; return TRUE; /邊的插入0132 0 1 2 30 0 0 0 01 1 0 1 02 0 0 0 13 1 1 0 01插入0,2邊/邊的刪除BOOL Delete(Graph *g, int u, int v) int n=g-Vertices; if(u0 | vn-1 | vn-1 | u=v | g-Auv=g-NoEdge)printf(BadInputn); return FAL

16、SE; g-Auv=g-NoEdge; return TRUE; 0132 0 1 2 30 0 0 0 01 1 0 1 02 0 0 0 13 1 1 0 01刪除0,2邊10.2.3 鄰接表表示法要點：1、為圖中每一個頂點建立一個單鏈表；2、頂點u的單鏈表中的每一個結(jié)點指示u的一個鄰接點v ， 即代表一條邊(u,v) 或 頂點u的單鏈表記錄了與u相鄰接(鄰接自u)的所有頂點。每個單鏈表相當(dāng)于鄰接矩陣的一行,它指示了該行中的非零的元素。01320123 1 3 0 0 2 3、邊結(jié)點的結(jié)構(gòu)adjVex W nextArc(b) 帶權(quán)的邊結(jié)點adjVex nextArc(a) 邊結(jié)點指示頂點

17、u的一個鄰接點指向u的下一個邊結(jié)點邊上的權(quán)值 u 1 3 v 0 2 element firstArc(c) 頂點結(jié)點存放頂點的名稱及其他信息指向u的第一個邊結(jié)點 u 1 3 v 0 2 4、每個單鏈表可設(shè)立一個存放頂點u的有關(guān)信息的表頭結(jié)點，也稱頂點結(jié)點。頂點結(jié)點存入一個一維數(shù)組。01232 1 0 3 1 3 1 3 2 0 (a)圖G1的鄰接表0132圖G10123 1 3 0 0 2 (b)圖G2的鄰接表0132圖G20123 3 3 0 1 1 1 2 5 0 4 (c)圖G3的鄰接表40132圖G33115typedef struct enode int AdjVex; T W;

18、struct enode * NextArc; ENode; typedef struct graph int Vertices ; ENode* A; Graph;邊結(jié)點的結(jié)構(gòu)類型圖中的頂點數(shù)0123 1 3 0 0 2 A鄰接表的表頭組成一維指針數(shù)組，A是指向該數(shù)組的指針3. 建立鄰接表 函數(shù)CreateGraph構(gòu)造一個有n個頂點，但不包含邊的有向圖。由于圖的頂點數(shù)事先并不知道，所以我們使用動態(tài)存儲分配的一維指針數(shù)組。void CreateGraph(Graph* g, int n) int i; g-Vertices=n; g-A=(ENode*)malloc(n*sizeof(ENo

19、de*); for(i=0; iAi=NULL; 01.n-1. 搜索、插入或刪除從頂點u發(fā)出的邊，只在Au所指向的單鏈表中操作。程序如下：3、邊的搜索、插入和刪除01232 1 0 3 1 3 1 3 2 0 1,2是否有邊？/搜索邊的函數(shù)BOOL Exist(Graph g, int u, int v) int n; ENode* p; n=g.Vertices; if(un-1) return FALSE; for(p=g.Au; p&p-AdjVex!=v; ) p=p-NextArc; if (!p) return FALSE; return TRUE; /插入邊的函數(shù)BOOL Ad

20、d(Graph *g, int u, int v, T w) int n; ENode *p; n=g-Vertices; if (u0 | vn-1 | vn-1 | u=v | Exist(*g, u, v) printf(BadInputn); return FALSE; p=NewENode(v, w, g-Au); g-Au=p; return TRUE; 0123 1 3 0 0 2 p30132插入鄰接表中由指針Au所指示的單鏈表的最前面ENode* NewENode( int vex, T weight, ENode* nextarc)ENode* p; p=(ENode*)m

21、alloc(sizeof(ENode); p-AdjVex=vex; p-W=weight; p-NextArc=nextarc; return p; /刪除邊的函數(shù)BOOL Delete(Graph *g, int u, int v) int n=g-Vertices;ENode* p, *q; if(u-1 & uAu; q=NULL; while (p& p-AdjVex!=v) q=p; p=p-NextArc; if (p) if (q) q-NextArc=p-NextArc; else g-Au=p-NextArc; free(p); return TRUE; printf(Ba

22、dInputn); return FALSE; 0123 1 3 0 0 2 01323Pq=NULL在由指針Au所指示的單鏈表中，搜索AdjVex域的值為v的邊結(jié)點10.3 圖的遍歷圖的遍歷: 指從圖G的任意一個頂點v出發(fā)，訪問圖中所有結(jié)點且每個結(jié)點僅訪問一次的過程。圖遍歷的方法:深度優(yōu)先搜索（類似于樹的先序遍歷）和寬度優(yōu)先搜索（類似于樹的按層次遍歷）課堂提要第10章 圖10.1 圖的基本概念10.2 圖的存儲結(jié)構(gòu)10.3 圖的遍歷10.5 最小代價生成 樹10.3.2 深度優(yōu)先遍歷圖遍歷與樹遍歷的差異: 1、從圖中任意一個頂點出發(fā)未必能到達其它所有頂點； 2、圖中存在回路時，又可能多次經(jīng)過

23、同一個頂點。 為了避免發(fā)生上述兩種情況，圖的搜索算法通常為圖的每個頂點保留一個標(biāo)志位(mark bit)。 算法開始時，所有頂點的標(biāo)志位清零。 在遍歷過程中，當(dāng)某個頂點被訪問時，其標(biāo)志位被標(biāo)記。在搜索中遇到被標(biāo)記過的頂點則不再訪問它。 搜索結(jié)束后，如果還有未標(biāo)記過的頂點，遍歷算法可以選一個未標(biāo)記的頂點，從它出發(fā)開始繼續(xù)搜索。1、深度優(yōu)先搜索算法 從圖G中某個頂點v出發(fā),深度優(yōu)先搜索圖的DFS算法如下： 1、訪問頂點v并打上標(biāo)記。 2、依次從v的未訪問過的鄰接點出發(fā)，深度優(yōu)先搜索圖G.從A出發(fā)將訪問走過的邊保留，去掉訪問時未走過的邊，就得到以A為根的DFS生成樹。如果是連通的無向圖或強連通的有向

24、圖，上述DFS算法必定可以系統(tǒng)地訪問圖中的全部頂點。一條無向邊被視作兩條有向邊，被查看兩次。(a) 有向圖GBFDEACG對有向圖G，從A出發(fā)DFS，訪問的次序是A,B,D,C；遍歷了所有從A出發(fā)可到達的頂點，即A的可達集。另選一個頂點出發(fā)搜索圖G的其余部分。0 2 3 0123456ABCDFGE4 1 5 3 40 2 (b) 圖G的鄰接表1ABDCFGE(a) 有向圖GBFDEACGBFDEACG(c) 圖G深度優(yōu)先搜索的生成森林思考:圖的DFS序列是否惟一？(指從同一頂點出發(fā))ABDCFGE圖中所有頂點，以及在遍歷時經(jīng)過的邊構(gòu)成的子圖，稱為圖的深度優(yōu)先搜索生成樹(dfs spannin

25、g tree)(或生成森林)。DFS遞歸算法（ 【程序105】 ）。void DFS(Graph g, int v, BOOL *visited) ENode *w; visitedv=TRUE; printf(%d , v); for ( w=g.Av; w; w=w-NextArc) if (!visitedw-AdjVex ) DFS(g, w-AdjVex, visited); void Traversal_DFS(Graph g) BOOL visitedMaxSize; int i, n=g.Vertices; for(i=0; in; i+) visitedi=FALSE; fo

26、r (i=0; iNextArc) if (!visitedw-AdjVex) printf(%d , w-AdjVex); visitedw-AdjVex=TRUE; Append(&q, w-AdjVex); u的鄰接頂點入隊訪問隊頭元素u的所有未訪問過的鄰接點void Traversal_BFS(Graph g)BOOL visitedMaxSize; int i, n=g.Vertices; for(i=0; in; i+) visitedi=FALSE; for (i=0; in; i+) if (!visitedi) BFS(g, i, visited); BFS算法的特點：1、每

27、個頂點進出隊列各一次。2、對于每個出隊的頂點，都要檢查其所有的鄰接點，對于無向圖每條邊被檢查2次。3、n個頂點，e條邊的圖采用鄰接表存儲，BFS算法的時間為O(n+e),而采用鄰接矩陣表示，時間為O(n2)。 如同二叉樹的遍歷算法，圖的DFS和BFS算法是最重要、最基本的算法，許多有關(guān)圖的算法都可以對它們稍加修改得到。例如，求無向圖的連通分量、有向圖的強連通分量、生成樹(森林)等。已知一有向圖的鄰接表存儲結(jié)構(gòu)如下圖所示，請問：每個頂點的入度和出度，并給出從頂點1出發(fā)的深度優(yōu)先遍歷和寬度優(yōu)先遍歷序列。1 01234ABCDE3 13 32 4 A B C D E 出度：3 0 2 0 2A B

28、C D E 入度：0 2 1 3 1ABCDE頂點1出發(fā)的深度優(yōu)先遍歷：ACDEB頂點1出發(fā)的寬度優(yōu)先遍歷：ACBDE10.4 最小代價生成樹問題的引入：在n個城市之間架設(shè)通信線路。已知每兩個城市間架設(shè)線路的代價，問如何選擇n-1條線路，可以使總代價最??？10.4.1 基本概念0132351278構(gòu)造一個連通圖的最小代價生成樹。一個連通圖的生成樹是：（1）一個極小連通子圖（2）它包括圖中全部頂點（3）有盡可能少的邊，只有足以構(gòu)成一棵樹的n1條邊。一棵生成樹的代價是各條邊上的代價之和。一個網(wǎng)絡(luò)的生成樹中具有最小代價的生成樹稱為該網(wǎng)絡(luò)的最小代價生成樹。 構(gòu)造最小代價生成樹的兩種算法： 普里姆算法（

29、Prim) 克魯斯卡爾算法(Kruskal)0132127013235701323120132351278 設(shè)G=(V,E)是帶權(quán)的連通圖，T=(V,E)是正在構(gòu)造中的生成樹。初始狀態(tài)下，這棵生成樹只有一個頂點，沒有邊，即V=u0，E= ，u0是任意選定的起始頂點。 從初始狀態(tài)開始，重復(fù)執(zhí)行下列運算： 在所有uV，vV-V的邊(u,v)，(u,v)E中找一條代價最小的邊(u,v)， 邊(u,v)并入集合E，將頂點v并入集合V。 直到V=V為止。 這時E中必有n-1條邊，T=(V,E)是圖G的一棵最小代價生成樹。1.普里姆算法（Prim)10.4.2 普里姆算法(u,v)的含義是：一端在樹上，另

30、一端不在樹上的最小權(quán)值邊0312453666555421圖10-15 普里姆算法構(gòu)造最小代價生成樹的過程0312453666555421圖G構(gòu)造中的最小代價生成樹T普里姆算法演示2.實現(xiàn)普里姆算法 為實現(xiàn)Prim算法,定義兩個一維數(shù)組,用于存放中間構(gòu)造過程和最終結(jié)果。 nearest lowcost設(shè)v是當(dāng)前尚未選入生成樹的頂點，nearestv中保存邊(u, v)在生成樹上的那個頂點u，邊(u, v)是所有u V的邊中權(quán)值最小的邊。uvu10387655nearest01vnlowcostVnearestv定義一個一維數(shù)組mark，用于表示某個頂點是否在生成樹上。如果markv=false,

31、表示v未加入生成樹，反之，v已選入。初始時： nearestv=-1,lowcostv=MaxNum, markv=FALSE(nearestv,v,lowcostv)代表一條權(quán)值為lowcostv，兩個頂點分別為nearestv和v的一條邊(nearestv,v)。如（2，1，5）: 邊(2,1)的代價為5， 其中 nearest1=2； lowcost1=5它記錄當(dāng)前對v而言，與生成樹上頂點相鄰的所有邊中權(quán)值最小者。031245366655542112345 0 -1nearestlowcost1 -1 2 -1 3 -1 4 -1 5 -16155000064232252001VV-V025314普里姆算法的C語言程序(【程序1010】 )。void Prim(Graph g, int k, int *nearest, T* lowcost) int i, j, min, n=g.Vert