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

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

2、graph)：是數(shù)據(jù)結(jié)構(gòu) G=(V,E)，其中V(G)是G中結(jié)點(diǎn)的有限非空集合,結(jié)點(diǎn)的偶對(duì)稱為邊(edge)；E(G)是G中邊的有限集合。圖中的結(jié)點(diǎn)又稱為頂點(diǎn)(vertex)。10.1.1 圖的定義與術(shù)語(yǔ)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)：指圖中代表邊的偶對(duì)是有序的。用代表一條有向邊（又稱為?。瑒tu稱為該邊的始點(diǎn)（尾），v稱為邊的終點(diǎn)（頭）。無(wú)向圖(undirected graph)：指圖中代表邊的偶對(duì)是無(wú)序的 在無(wú)向圖中邊(u，v )

3、和(v，u)是同一條邊。10234(b)有向圖G210234(a)無(wú)向圖G11023410234(a)無(wú)向圖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)=,自回路：如果圖中存在無(wú)向邊(u,u)或有向邊， 則稱這樣的邊為自回路。多重圖：指圖中兩個(gè)頂點(diǎn)間允許有多條相同的邊。自回路和多重圖的例子10231023(b)多重圖 (a)自回路 鄰接:如果(u,v)是無(wú)向圖中的一條邊，則稱頂點(diǎn)u和v相鄰接，并稱邊(u,v)與頂點(diǎn)u和v相關(guān)聯(lián)。例如：頂點(diǎn)1和2是相鄰接的。完全圖：如果

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

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

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

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

8、向無(wú)環(huán)圖（DAG圖）：不包含回路的有向圖。自由樹(shù)：不包含回路的連通圖。10234102342386254ADT 101 Graph 數(shù)據(jù)： 頂點(diǎn)的非空集合V和邊的集合E，每條邊由V中頂點(diǎn)的偶對(duì)表示。運(yùn)算： void CreateGraph( Graph* g, int n, T noedge ) 后置條件: 已構(gòu)造一個(gè)只有n個(gè)結(jié)點(diǎn)，不包含任何邊的有向圖。BOOL Add( Graph *g, int u, int v, T w) 后置條件: 向圖中添加權(quán)值為w(若邊上沒(méi)有權(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ù)返回圖中頂點(diǎn)數(shù)目。 上面列出的只是圖的最基本的運(yùn)算。在以后的各小節(jié)中，我們將通過(guò)添加新運(yùn)算，陸續(xù)擴(kuò)充ADT 101 的圖抽象數(shù)據(jù)類型。主要包括以下圖運(yùn)算： (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) 普里姆算法求最小代價(jià)生成樹(shù)：void Prim(Graph g，int k)； (6) 克魯斯卡爾算法求最小代價(jià)生成樹(shù)：void Kruskal(Graph g，int edges)； (7) 迪杰斯特拉算法求單源最短路徑：void Dijkstra(Graph g，int k, T d, int p)；(8) 弗洛伊德算法求所有頂點(diǎn)之間的最短路徑：void Floyd(Graph g，T*&d, int *&path)。1、圖的矩陣表示法及其實(shí)現(xiàn)2、圖的鄰接表表示法及其實(shí)現(xiàn)

11、10.2 圖的存儲(chǔ)結(jié)構(gòu)10.2.1 圖的矩陣表示法1、鄰接矩陣 一個(gè)有n個(gè)頂點(diǎn)的圖G=(V,E)的鄰接矩陣是一個(gè)nn的矩陣A，A的每個(gè)元素是0或1。課堂提要第10章 圖10.1 圖的基本概念10.2 圖的存儲(chǔ)結(jié)構(gòu)10.3 圖的遍歷10.5 最小代價(jià)生成 樹(shù) 設(shè)V=0,1,2,n-1,如果G是無(wú)向圖，則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) 無(wú)向圖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強(qiáng)連通分量1、鄰接矩陣C語(yǔ)言定義10.2.2 圖的鄰接矩陣實(shí)現(xiàn)typedef struct

13、 graph T NoEdge; /兩結(jié)點(diǎn)間無(wú)邊時(shí)的值(0或) int Vertices; /圖中頂點(diǎn)數(shù) T* A; /指向存儲(chǔ)鄰接矩陣的二維數(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是否有邊？有邊!無(wú)邊!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 鄰接表表示法要點(diǎn)：1、為圖中每一個(gè)頂點(diǎn)建立一個(gè)單鏈表；2、頂點(diǎn)u的單鏈表中的每一個(gè)結(jié)點(diǎn)指示u的一個(gè)鄰接點(diǎn)v ， 即代表一條邊(u,v) 或 頂點(diǎn)u的單鏈表記錄了與u相鄰接(鄰接自u(píng))的所有頂點(diǎn)。每個(gè)單鏈表相當(dāng)于鄰接矩陣的一行,它指示了該行中的非零的元素。01320123 1 3 0 0 2 3、邊結(jié)點(diǎn)的結(jié)構(gòu)adjVex W nextArc(b) 帶權(quán)的邊結(jié)點(diǎn)adjVex nextArc(a) 邊結(jié)點(diǎn)指示頂點(diǎn)

17、u的一個(gè)鄰接點(diǎn)指向u的下一個(gè)邊結(jié)點(diǎn)邊上的權(quán)值 u 1 3 v 0 2 element firstArc(c) 頂點(diǎn)結(jié)點(diǎn)存放頂點(diǎn)的名稱及其他信息指向u的第一個(gè)邊結(jié)點(diǎn) u 1 3 v 0 2 4、每個(gè)單鏈表可設(shè)立一個(gè)存放頂點(diǎn)u的有關(guān)信息的表頭結(jié)點(diǎn)，也稱頂點(diǎn)結(jié)點(diǎn)。頂點(diǎn)結(jié)點(diǎn)存入一個(gè)一維數(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é)點(diǎn)的結(jié)構(gòu)類型圖中的頂點(diǎn)數(shù)0123 1 3 0 0 2 A鄰接表的表頭組成一維指針數(shù)組，A是指向該數(shù)組的指針3. 建立鄰接表 函數(shù)CreateGraph構(gòu)造一個(gè)有n個(gè)頂點(diǎn)，但不包含邊的有向圖。由于圖的頂點(diǎn)數(shù)事先并不知道，所以我們使用動(dòng)態(tài)存儲(chǔ)分配的一維指針數(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. 搜索、插入或刪除從頂點(diǎn)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é)點(diǎn)10.3 圖的遍歷圖的遍歷: 指從圖G的任意一個(gè)頂點(diǎn)v出發(fā)，訪問(wèn)圖中所有結(jié)點(diǎn)且每個(gè)結(jié)點(diǎn)僅訪問(wèn)一次的過(guò)程。圖遍歷的方法:深度優(yōu)先搜索（類似于樹(shù)的先序遍歷）和寬度優(yōu)先搜索（類似于樹(shù)的按層次遍歷）課堂提要第10章 圖10.1 圖的基本概念10.2 圖的存儲(chǔ)結(jié)構(gòu)10.3 圖的遍歷10.5 最小代價(jià)生成 樹(shù)10.3.2 深度優(yōu)先遍歷圖遍歷與樹(shù)遍歷的差異: 1、從圖中任意一個(gè)頂點(diǎn)出發(fā)未必能到達(dá)其它所有頂點(diǎn)； 2、圖中存在回路時(shí)，又可能多次經(jīng)過(guò)

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

24、圖，上述DFS算法必定可以系統(tǒng)地訪問(wèn)圖中的全部頂點(diǎn)。一條無(wú)向邊被視作兩條有向邊，被查看兩次。(a) 有向圖GBFDEACG對(duì)有向圖G，從A出發(fā)DFS，訪問(wèn)的次序是A,B,D,C；遍歷了所有從A出發(fā)可到達(dá)的頂點(diǎn)，即A的可達(dá)集。另選一個(gè)頂點(diǎn)出發(fā)搜索圖G的其余部分。0 2 3 0123456ABCDFGE4 1 5 3 40 2 (b) 圖G的鄰接表1ABDCFGE(a) 有向圖GBFDEACGBFDEACG(c) 圖G深度優(yōu)先搜索的生成森林思考:圖的DFS序列是否惟一？(指從同一頂點(diǎn)出發(fā))ABDCFGE圖中所有頂點(diǎn)，以及在遍歷時(shí)經(jīng)過(guò)的邊構(gòu)成的子圖，稱為圖的深度優(yōu)先搜索生成樹(shù)(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的鄰接頂點(diǎn)入隊(duì)訪問(wèn)隊(duì)頭元素u的所有未訪問(wèn)過(guò)的鄰接點(diǎn)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算法的特點(diǎn)：1、每

27、個(gè)頂點(diǎn)進(jìn)出隊(duì)列各一次。2、對(duì)于每個(gè)出隊(duì)的頂點(diǎn)，都要檢查其所有的鄰接點(diǎn)，對(duì)于無(wú)向圖每條邊被檢查2次。3、n個(gè)頂點(diǎn)，e條邊的圖采用鄰接表存儲(chǔ)，BFS算法的時(shí)間為O(n+e),而采用鄰接矩陣表示，時(shí)間為O(n2)。 如同二叉樹(shù)的遍歷算法，圖的DFS和BFS算法是最重要、最基本的算法，許多有關(guān)圖的算法都可以對(duì)它們稍加修改得到。例如，求無(wú)向圖的連通分量、有向圖的強(qiáng)連通分量、生成樹(shù)(森林)等。已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖所示，請(qǐng)問(wèn)：每個(gè)頂點(diǎn)的入度和出度，并給出從頂點(diǎn)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頂點(diǎn)1出發(fā)的深度優(yōu)先遍歷：ACDEB頂點(diǎn)1出發(fā)的寬度優(yōu)先遍歷：ACBDE10.4 最小代價(jià)生成樹(shù)問(wèn)題的引入：在n個(gè)城市之間架設(shè)通信線路。已知每?jī)蓚€(gè)城市間架設(shè)線路的代價(jià)，問(wèn)如何選擇n-1條線路，可以使總代價(jià)最小？10.4.1 基本概念0132351278構(gòu)造一個(gè)連通圖的最小代價(jià)生成樹(shù)。一個(gè)連通圖的生成樹(shù)是：（1）一個(gè)極小連通子圖（2）它包括圖中全部頂點(diǎn)（3）有盡可能少的邊，只有足以構(gòu)成一棵樹(shù)的n1條邊。一棵生成樹(shù)的代價(jià)是各條邊上的代價(jià)之和。一個(gè)網(wǎng)絡(luò)的生成樹(shù)中具有最小代價(jià)的生成樹(shù)稱為該網(wǎng)絡(luò)的最小代價(jià)生成樹(shù)。 構(gòu)造最小代價(jià)生成樹(shù)的兩種算法： 普里姆算法（

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

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

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