1、本節內容圖王道考研/CSKAOYAN.COM王道考研/CSKAOYAN.COM圖ACEBD樹是N（N0）個結點的有限集合，N=0時，稱為空樹，這是一種特殊情況。在任意一棵非空樹中應滿足：1）有且僅有一個特定的稱為根的結點。2）當N1時，其余結點可分為m（m0）個互不相交的有限集合T1，T2，Tm，其中每一個集合本身又是一棵樹，并且稱為根結點的子樹。F圖G由頂點集V和邊集E組成，記為G=(V，E)V(G)表示圖G中頂點的有限非空集。用|V|表示圖G中頂點的個數，也稱為圖G的階。E(G)表示圖G中頂點之間的關系（邊）集合。用|E|表示圖G中邊的條數。VertexEdge圖不可為空，一個圖中就算是一

2、條邊都沒有，也就是邊集為空，但是頂點集一定不為空。王道考研/CSKAOYAN.COM圖的基本概念ABCABC無向圖G2有向圖G1G1=(V1，E1)V1=A，B，CE1=，G2=(V2，E2)V2=A，B，CE2=(A，B)，(A，C)， (B，C)王道考研/CSKAOYAN.COM圖的基本概念ABCABC王道考研/CSKAOYAN.COM圖的基本概念ABCABC對于n個頂點每個頂點都與其他n-1個頂點有一條邊，由于重復，所以一共有n*(n-1)/2條邊每個頂點都與其他n-1個頂點有一條邊，由于有方向不重復，所以一共有n*(n-1) 條邊王道考研/CSKAOYAN.COM圖的基本概念若有滿足V

3、(G)=V(G)的子圖G，則為G的生成子圖ACA并非V和E的任何子集都能構成G的子圖，因為這樣的子集可能不是圖，也就是說，E的子集中的某些邊關聯的頂點可能不在這個V的子集中。G=(V，E)V=A，B，CE=，ABCG=(V，E)V=CE=，子圖(a)子圖(b)B王道考研/CSKAOYAN.COM圖的基本概念ABDCEFG=(V，E)V=A，B，C，D，E，FE=(A，B)，(B，C)，(C，D)， (D，A)， (E，F)如果右圖看成一個圖則是不連通的找連通分量的方法：從選取一個頂點開始，以這個頂點作為一個子圖，然后逐個添加與這個子圖相連的頂點和邊直到所有相連的頂點都加入該子圖結論1:如果一個

4、圖有n個頂點，并且有小于n-1條邊，則此圖必是非連通圖。王道考研/CSKAOYAN.COM圖的基本概念ABCDG=(V，E)V=A，B，C，DE=， 不連通ABCD強連通分量王道考研/CSKAOYAN.COM圖的基本概念ABCDEF6個頂點，7條邊ABCDEF6個頂點，5條邊結論2:生成樹去掉一條邊則變成非連通圖，加上一條邊就會形成回路。王道考研/CSKAOYAN.COM圖的基本概念ABC無向圖ABC有向圖無向圖：有向圖：TD(v)=ID(v)+OD(v)ABC有向樹王道考研/CSKAOYAN.COM圖的基本概念ABCD1000A-B-C-D-A 路徑長度為4A-B-C-A-D 和 A-B-C

5、-DB和D的距離為2王道考研/CSKAOYAN.COM圖的基本概念本節內容圖的存儲結構王道考研/CSKAOYAN.COM王道考研/CSKAOYAN.COM圖的存儲結構圖的存儲結構相比線性表和樹顯得更復雜圖中頂點沒有次序之分圖中邊和頂點的數量任意王道考研/CSKAOYAN.COM鄰接矩陣頂點：用一維數組來存儲邊或?。河枚S數組來存儲二維數組就是一維數組的拓展，相當于一維數組中每個元素也是一個一維數組。二維數組也叫做鄰接矩陣a0a1a2a00a01a02a10a11a12a20a21a223*3 二維數組ABCD頂點數組：ABCD邊或弧數組：ABCDABCD0000aij=1 若(vi,vj)或是

6、E(G)中的邊0 若(vi,vj)或不是E(G)中的邊111111111010無向圖的鄰接矩陣是一個對稱矩陣1.判定兩個頂點是否有邊2.求某個頂點的度3.找到某個頂點的所有鄰接點因此可以只存儲上半部分矩陣王道考研/CSKAOYAN.COM鄰接矩陣ABCD頂點數組：ABCD邊或弧數組：ABCDABCD00001010111100001.頂點的入度是頂點所在這一列的各數之和；出度是頂點所在這一行的各數之和。2.判定兩個頂點是否有邊3.找到某個頂點的所有鄰接點對于帶權圖(網)可以在矩陣中存儲邊的權值ABCD586732ABCDABCD00005867321、帶權邊存儲權值2、行和列相同結點權值為03

7、、不存在的邊權值為無限大王道考研/CSKAOYAN.COM鄰接矩陣#define MaxVertexNum l00 /頂點數目的最大值typedef char VertexType;/頂點的數據類型 不同情況不一樣typedef int EdgeType; /整數表示權值或者連通性typedef structVertexType VexMaxVertexNum;/頂點表EdgeType EdgeMaxVertexNumMaxVertexNum;/鄰接矩陣(二維數組)，邊表int vexnum,arcnum; /圖的當前頂點數和弧數MGraph;由于鄰接矩陣基于二維數組，所以利用二維數組創建圖的

8、時間復雜度為O(n2) ，其中n為圖的頂點數。所以當頂點數較多時，鄰接矩陣的復雜度也會比較大。王道考研/CSKAOYAN.COM鄰接表對于稀疏圖(|E|遠小于|V|2)ABCDABCDABCD0000100000000000浪費存儲空間順序存儲結構存在預先分配內存可能浪費的問題，按照經驗會想到鏈式存儲結構adbcefdataabcdef下標012345firstchild13524孩子表示法王道考研/CSKAOYAN.COM鄰接表dataABCD下標0123firstedge1ABCD230201302圖中的頂點用一個一維數組存儲。同時每個元素還要存儲指向第一個鄰接點的指針(鏈表的頭指針)。存

9、儲頂點和頭指針的表叫頂點表圖中每個頂點的所有鄰接點構成一個單鏈表。對于無向圖，這個表稱為該結點的邊表，對于有向圖稱為該結點的出邊表頂點表邊表王道考研/CSKAOYAN.COM鄰接表dataABCD下標0123firstedge1ABCD2230注意是以頂點為弧尾需要設計兩種結點結構類型：一是頂點表的頂點，二是單鏈表的結點#define MaxVertexNum 100 /圖中頂點數目的最大值typedef struct ArcNode /邊表結點int adjvex; /該弧所指向的頂點的位置struct ArcNode *next; /指向下一條弧的指針ArcNode; typedef st

10、ruct VNode/頂點表結點VertexType data; /頂點信息ArcNode *firstedge; /單鏈表頭指針VNode,AdjListMaxVertexNum;/AdjList是結構體數組類型typedef structAdjList vertices; /鄰接表int vexnum,arcnum; /圖的頂點數和弧數 ALGraph; /ALGraph是以鄰接表存儲的圖類型王道考研/CSKAOYAN.COM十字鏈表dataABCD下標0123firstedge1ABCD2230注意是以頂點為弧尾有向圖的鄰接表關心了有向圖的出邊問題，我們通過有向圖很容易找到頂點的出邊比如

11、從每個頂點表的firstedge指針找到第一條邊的頂點，再通過next指針依次找到下一條邊的頂點直到空指針。但是，如果要找到其他頂點到該頂點的邊，或者說考慮一個頂點的入度問題，則需要遍歷整個圖。這是鄰接表存儲有向圖的缺陷。王道考研/CSKAOYAN.COM十字鏈表十字鏈表是針對有向圖的存儲方式，對應于有向圖中的每條弧有一個結點，對應于每個頂點也有一個結點datafirstoutfirstin頂點結點headvextaillinkheadlinktailvex邊表結點圖中頂點的數據該頂點的入邊表的頭指針該頂點的出邊表的頭指針這條弧的弧尾(起點)所在頂點表下標這條弧的弧頭(終點)所在頂點表下標指向

12、弧頭(終點)相同的下一條邊指向弧尾(起點)相同的下一條邊其實十字鏈表是在鄰接表的基礎上進行了優化。在十字鏈表中不僅包含了鄰接表本身就包含的結點出度結點，而且還包含了入度結點的信息。王道考研/CSKAOYAN.COM十字鏈表ABCDABCD01下標0123入邊表出邊表02弧尾弧頭相同弧頭相同弧尾12(A-B)(A-C)(B-C)21(C-B)30(D-A)23(C-D)該頂點的出邊該頂點的入邊十字鏈表的存儲形式不唯一王道考研/CSKAOYAN.COM十字鏈表datafirstoutfirstin頂點結點headvextaillinkheadlinktailvex邊表結點圖中頂點的數據該頂點的入邊

13、表的頭指針該頂點的出邊表的頭指針這條弧的弧尾(起點)所在頂點表下標這條弧的弧頭(終點)所在頂點表下標指向弧頭(終點)相同的下一條邊指向弧尾(起點)相同的下一條邊typedef struct ArcNodeint tailvex, headvex;struct ArcNode *hlink, *tlink;ArcNode; typedef struct VNodeVertexType data; ArcNode *firstin, *firstout; VNode;typedef structVNode xlistMaxVertexNum; /頂點依舊用順序存儲(數組)int vexnum,ar

14、cnum; /圖的頂點數和弧數 GLGraph; /十字鏈表存儲的圖類型王道考研/CSKAOYAN.COM鄰接多重表ABCDdataABCD下標0123firstedge1230201302頂點表邊表鄰接表存儲的無向圖中查找頂點是比較容易的，但是如果要修改圖中的邊或者是查詢邊,則需要遍歷鏈表。這是鄰接表的缺陷。仿照十字鏈表，對鄰接表的邊表進行改造，得到專門針對存儲無向圖的鄰接多重表王道考研/CSKAOYAN.COM鄰接多重表ABCDdataABCD下標0123firstedge1230201302頂點表邊表ilinkjlinkjvexivex鄰接多重表邊表結點這條邊依附的兩個頂點在頂點表的下標

15、指向依附頂點ivex的下一條邊指向依附頂點jvex的下一條邊王道考研/CSKAOYAN.COM鄰接多重表ABCDilinkjlinkjvexivex這條邊依附的兩個頂點在頂點表的下標指向依附頂點ivex的下一條邊指向依附頂點jvex的下一條邊ABCD下標01230102301223datafirstedge（A-B）（A-C）（D-A）（B-C）（C-D）本節內容圖的遍歷王道考研/CSKAOYAN.COM王道考研/CSKAOYAN.COM圖的遍歷圖的遍歷：從圖中某一頂點出發訪遍圖中其余頂點，且使每一個頂點僅被訪問一次，這個過程就叫做圖的遍歷。圖中頂點沒有特殊性，可能存在沿著某條路徑搜索后回到原

16、起點，而有些頂點沒有訪問到。解決辦法：設置一個訪問數組,記錄遍歷過程中訪問過的頂點。王道考研/CSKAOYAN.COMBFS廣度優先搜索(BFS:Breadth-First-Search):廣度優先搜索類似于樹的層序遍歷算法ABCDEFGABCDEFG第一層第二層第三層第四層層序遍歷序列：A B C E F D G王道考研/CSKAOYAN.COMBFSvoid BFS(Graph G,int v) ArcNode *p; /工作指針p InitQueue(Q); /初始化一個隊列 visit(v); /訪問第一個頂點v 具體可以是Print visitedv=TRUE; /對v做已訪問標記

17、Enqueue(Q,v); /頂點v入隊列 while(!isEmpty(Q) /只要隊列不空DeQueue(Q,v); /頂點v出隊列p=G-adjListv.firstedge; /指針p指向當前頂點的邊表鏈表頭指針 while(p) if(!visitedp-adjvex) /p所指向頂點如果未被訪問 visit(p-adjvex); /訪問p所指向的頂點visitedp-adjvex=TRUE; /對這個頂點做已訪問標記EnQueue(Q,p-adjvex); /這個頂點入隊列 p=p-next；/p指向該頂點的下一條邊 void BFSTraverse(Graph G) int i;

18、 /單獨定義是為了方便多個循環中使用 for(i=0; ivexnum; i+）visitedi=false; /將標志數組初始化 (全局數組) for(i=0; ivexnum; i+) if(!visitedi)BFS(G,i); /為了避免非連通圖一些頂點訪問不到 若是連通圖只會執行一次 #define MaxSize 100;bool visitedMaxSize；王道考研/CSKAOYAN.COMBFSvoid BFS(Graph G,int v) ArcNode *p; InitQueue(Q); visit(v); visitedv=TRUE; Enqueue(Q,v); whi

19、le(!isEmpty(Q) DeQueue(Q,v); p=G-adjListv.firstedge; while(p) If(!visitedp-adjvex) visit(p-adjvex); visitedp-adjvex=TRUE; EnQueue(Q, p-adjvex); p=p-next； ABCD頂點訪問序列：AABCD訪問標記數組是否訪問falsefalsefalsefalse頂點truetruetruetrueAdataABCD下標0123firstedge1230201302BBCCDDE4E1Efalse4EtrueEp王道考研/CSKAOYAN.COMBFS空間復雜

20、度：BFS需要借助一個隊列，n個頂點均需要入隊一次，所以最壞情況下n個頂點在隊列，那么 則需要O(|V|)的空間復雜度。 void BFS(Graph G,int v) ArcNode *p; /工作指針p InitQueue(Q); /初始化一個隊列 visit(v); /訪問第一個頂點v 具體可以是Print visitedv=TRUE; /對v做已訪問標記 Enqueue(Q,v); /頂點v入隊列 while(!isEmpty(Q) /只要隊列不空DeQueue(Q,v); /頂點v出隊列p=G-adjListv.firstedge; /指針p指向當前頂點的邊表鏈表頭指針 while(

21、p) if(!visitedp-adjvex) /p所指向結點如果未被訪問 visit(p-adjvex); /訪問p所指向的頂點visitedp-adjvex=TRUE; /對這個頂點做已訪問標記EnQueue(Q,p-adjvex); /這個頂點入隊列 p=p-next；/指向該頂點的下一條邊 王道考研/CSKAOYAN.COMBFS時間復雜度：1)鄰接表：每個頂點入隊一次，時間復雜度為O(|V|),對于每個頂點，搜索它的鄰接點，就需要訪問這個頂點的所有邊，所以時間復雜度為O(|E|)。所以總的時間復雜度為O(|V|+|E|)2)鄰接矩陣：每個頂點入隊一次，時間復雜度為O(|V|),對于每

22、個頂點，搜索它的鄰接點，需要遍歷一遍矩陣的一行，所以時間復雜度為O(|V|),所以總的時間復雜度為O(|V|2)void BFS(Graph G,int v) ArcNode *p; /工作指針p InitQueue(Q); /初始化一個隊列 visit(v); /訪問第一個頂點v 具體可以是Print visitedv=TRUE; /對v做已訪問標記 Enqueue(Q,v); /頂點v入隊列 while(!isEmpty(Q) /只要隊列不空DeQueue(Q,v); /頂點v出隊列p=G-adjListv.firstedge; /指針p指向當前頂點的邊表鏈表頭指針 while(p) if

23、(!visitedp-adjvex) /p所指向結點如果未被訪問 visit(p-adjvex); /訪問p所指向的頂點visitedp-adjvex=TRUE; /對這個頂點做已訪問標記EnQueue(Q,p-adjvex); /這個頂點入隊列 p=p-next；/指向該頂點的下一條邊 王道考研/CSKAOYAN.COMBFS應用void BFS_MIN_Distance(Graph G,int u) /di表示從u到i結點的最短路徑for(i=0;iadjListu.firstedge; while(p) If(!visitedp-adjvex) visitedp-adjvex=TRUE;

24、 /路徑長度加1 dp-adjvex=du+1; EnQueue(Q, p-adjvex); p=p-next； ABCDEdA=0dB=dA+1=1dC=dA+1=1dD=dA+1=1dE=dB+1=2BFS解決單源非帶權圖最短路徑問題：按照距離由近到遠來遍歷圖中每個頂點王道考研/CSKAOYAN.COM廣度優先生成樹ABCDE如果圖是鄰接矩陣存儲的，廣度優先生成樹唯一。如果圖是鄰接矩陣存儲的，廣度優先生成樹則不唯一。ABCDEACBDE王道考研/CSKAOYAN.COMDFS深度優先搜索(DFS:Depth-First-Search):深度優先搜索類似于樹的先序遍歷算法首先訪問圖中某一起始

25、頂點v，然后由v出發，訪問與v鄰接且未被訪問的任一頂點w1，再訪問與w1鄰接且未被訪問的任一頂點w2，重復上述過程。當不能再繼續向下訪問時，依次退回到最近被訪問的頂點，若它還有鄰接頂點未被訪問過，則從該點開始繼續上述搜索過程，直到圖中所有頂點均被訪問過為止ABCDEABECD王道考研/CSKAOYAN.COMDFSvoid DFS(Graph G,int v) ArcNode *p; /工作指針pvisit(v); /訪問頂點v(一般是打印，即printf)visitedv=TRUE;/修改訪問標記p=G-adjlistv.firstarc; /指針p開始指向該頂點的第一條邊 while(p!

26、=NULL) /沒遍歷完頂點的所有鄰接頂點if(!visitedp-adjvex) /如果該頂點沒被訪問 DFS(G,p-adjvex); /遞歸訪問該頂點 p=p-nextarc; /看還有沒有其他未訪問的頂點void DFSTraverse(Graph G) int i; /單獨定義是為了方便多個循環中使用 for(i=0; ivexnum; i+）visitedi=false; /將標志數組初始化 (全局數組) for(i=0; ivexnum; i+) if(!visitedi)DFS(G,i); /對所有#define MaxSize 100;bool visitedMaxSize；

27、王道考研/CSKAOYAN.COMDFS#define MaxSize 100;bool visitedMaxSize；void DFS(Graph G,int v) ArcNode *p; visit(v); visitedv=TRUE;p=G-adjlistv.firstarc; while(p!=NULL) if(!visitedp-adjvex) DFS(G,p-adjvex); p=p-nextarc; ABCDE頂點訪問序列：AABCD訪問標記數組是否訪問falsefalsefalsefalse頂點truetruetruetrueEfalsetruedataABCD0123firs

28、tedge12302013024E14下標pBCDE王道考研/CSKAOYAN.COMDFSvoid DFS(Graph G,int v) ArcNode *p; /工作指針pvisit(v); /訪問頂點v(一般是遍歷，即printf)visitedv=TRUE;/修改訪問標記p=G-adjlistv.firstarc; /指針p開始指向該頂點的第一條邊 while(p!=NULL) /沒遍歷完頂點的所有鄰接頂點if(!visitedp-adjvex) /如果該頂點沒被訪問 DFS(G,p-adjvex); /遞歸訪問該頂點 p=p-nextarc; /看還有沒有其他未訪問的頂點空間復雜度：

29、由于DFS是一個遞歸算法，遞歸是需要一個工作棧來輔助工作，最多需要圖中所有頂點進棧，所以時間復雜度為O(|V|)時間復雜度：1)鄰接表：遍歷過程的主要操作是對頂點遍歷它的鄰接點，由于通過訪問邊表來查找鄰接點，所以時間復雜度為O(|E|),訪問頂點時間為O(|V|),所以總的時間復雜度為O(|V|+|E|) 2)鄰接矩陣：查找每個頂點的鄰接點時間復雜度為O(|V|),對每個頂點都進行查找，所以總的時間復雜度為O(|V|2)王道考研/CSKAOYAN.COM深度優先生成樹ABCDEABECD如果是一個非連通圖，則是深度優先森林ABCDEABEDC深度優先生成樹深度優先森林本節內容圖的應用(1)最小

30、生成樹王道考研/CSKAOYAN.COM王道考研/CSKAOYAN.COM最小生成樹我們之前講過連通圖的生成樹，它是一個極小的連通子圖。它包含圖中全部的頂點，但只有足以構成一棵樹的n-1條邊。ABCDEF生成樹不唯一6個頂點，7條邊王道考研/CSKAOYAN.COM最小生成樹ABCDEFG51122015841831224A鎮51122015841831224B鎮C鎮D鎮E鎮F鎮G鎮選擇總權值最小的修路成本自然最小王道考研/CSKAOYAN.COM普利姆算法普利姆(Prim)算法:從圖中找第一個起始頂點v0，作為生成樹的第一個頂點，然后從這個頂點到其他頂點的所有邊中選一條權值最小的邊。然后把這

31、條邊的另一個頂點v和這條邊加入到生成樹中。對剩下的其他所有頂點，分別檢查這些頂點與頂點v的權值是否比這些頂點在lowcost數組中對應的權值小，如果更小，則用較小的權值更新lowcost數組。從更新后的lowcost數組中繼續挑選權值最小而且不在生成樹中的邊，然后加入到生成樹。反復執行直到所有所有頂點都加入到生成樹中。需要維護兩個數組：lowcostn adjvexn（n是圖中的頂點數）王道考研/CSKAOYAN.COM普利姆算法普利姆(Prim)算法012345651122015841831224Void MiniSpanTree_Prim(MGraph G) int min,i,j,k;

32、int adjvexMAXVEX; /保存鄰接頂點下標的數組 int lowcostMAXVEX; /記錄當前生成樹到剩余頂點的最小權值 lowcost0=0; /將0號頂點(以0號頂點作為第一個頂點)加入生成樹 adjvex0=0; /由于剛開始生成樹只有一個頂點 不存在邊 干脆都設為0 for(i=1;iG.vexnum;i+) /除下標為0以外的所有頂點 lowcosti=G.arc0i; /將與下標為0的頂點有邊的權值存入Lowcost數組 adjvexi=0; /這些頂點的adjvex數組全部初始化為0 Lowcosti=0表示i號頂點在生成樹中下標0123456lowcost051

33、1adjvex0000000初始化初始化王道考研/CSKAOYAN.COM普利姆算法普利姆(Prim)算法012345651122015841831224Void MiniSpanTree_Prim(MGraph G) int min,i,j,k; int adjvexMAXVEX; /保存鄰接頂點下標的數組 int lowcostMAXVEX; /記錄當前生成樹到剩余頂點的最小權值 lowcost0=0; /將0號頂點(以0號頂點作為第一個頂點)加入生成樹 adjvex0=0; /由于剛開始生成樹只有一個頂點 不存在邊 干脆都設為0 for(i=1;iG.vexnum;i+) /除下標為0以

34、外的所有頂點 lowcosti=G.arc0i; /將與下標為0的頂點有邊的權值存入Lowcost數組 adjvexi=0; /這些頂點的adjvex數組全部初始化為0 /算法核心 for(i=1;iG.vexnum;i+)/只需要循環N-1次，N為頂點數 min=65535; /tip：因為要找最小值，不妨先設取一個最大的值來比較 j=0;k=0; /找出lowcost最小的 最小權值給min，下標給k while(jG.vexnum) /從1號頂點開始找 if(lowcostj!=0 & lowcostj%d)”,adjvexk,k); /打印權值最小的邊 lowcostk=0; /將這個

35、頂點加入生成樹 /生成樹加入了新的頂點 從下標為1的頂點開始更新lowcost數組值 for(j=0;jG.vexnum;j+) if(lowcostj!=0 & G.arckjlowcostj) /如果新加入樹的頂點k使得權值變小 lowcostj=G.arckj; /更新更小的權值 adjvexj=k; /修改這條邊鄰接的頂點 也就是表示這條邊是 從選出的頂點k指過來的 方便打印 Lowcosti=0表示i號頂點在生成樹中下標0123456lowcost0511adjvex0000000找頂點更新數組i=1王道考研/CSKAOYAN.COM普利姆算法普利姆(Prim)算法012345651

36、122015841831224Void MiniSpanTree_Prim(MGraph G) int min,i,j,k; int adjvexMAXVEX; /保存鄰接頂點下標的數組 int lowcostMAXVEX; /記錄當前生成樹到剩余頂點的最小權值 lowcost0=0; /將0號頂點(以0號頂點作為第一個頂點)加入生成樹 adjvex0=0; /由于剛開始生成樹只有一個頂點 不存在邊 干脆都設為0 for(i=1;iG.vexnum;i+) /除下標為0以外的所有頂點 lowcosti=G.arc0i; /將與下標為0的頂點有邊的權值存入Lowcost數組 adjvexi=0;

37、 /這些頂點的adjvex數組全部初始化為0 /算法核心 for(i=1;iG.vexnum;i+)/只需要循環N-1次，N為頂點數 min=65535; /tip：因為要找最小值，不妨先設取一個最大的值來比較 j=0;k=0; /找出lowcost最小的 最小權值給min，下標給k while(jG.vexnum) /從1號頂點開始找 if(lowcostj!=0 & lowcostj%d)”,adjvexk,k); /打印權值最小的邊 lowcostk=0; /將這個頂點加入生成樹 /生成樹加入了新的頂點 從下標為1的頂點開始更新lowcost數組值 for(j=0;jG.vexnum;j

38、+) if(lowcostj!=0 & G.arckj1）更新數組i=1王道考研/CSKAOYAN.COM普利姆算法普利姆(Prim)算法012345651122015841831224Void MiniSpanTree_Prim(MGraph G) int min,i,j,k; int adjvexMAXVEX; /保存鄰接頂點下標的數組 int lowcostMAXVEX; /記錄當前生成樹到剩余頂點的最小權值 lowcost0=0; /將0號頂點(以0號頂點作為第一個頂點)加入生成樹 adjvex0=0; /由于剛開始生成樹只有一個頂點 不存在邊 干脆都設為0 for(i=1;iG.ve

39、xnum;i+) /除下標為0以外的所有頂點 lowcosti=G.arc0i; /將與下標為0的頂點有邊的權值存入Lowcost數組 adjvexi=0; /這些頂點的adjvex數組全部初始化為0 /算法核心 for(i=1;iG.vexnum;i+)/只需要循環N-1次，N為頂點數 min=65535; /tip：因為要找最小值，不妨先設取一個最大的值來比較 j=0;k=0; /找出lowcost最小的 最小權值給min，下標給k while(jG.vexnum) /從1號頂點開始找 if(lowcostj!=0 & lowcostj%d)”,adjvexk,k); /打印權值最小的邊

40、lowcostk=0; /將這個頂點加入生成樹 /生成樹加入了新的頂點 從下標為1的頂點開始更新lowcost數組值 for(j=0;jG.vexnum;j+) if(lowcostj!=0 & G.arckjlowcostj) /如果新加入樹的頂點k使得權值變小 lowcostj=G.arckj; /更新更小的權值 adjvexj=k; /修改這條邊鄰接的頂點 也就是表示這條邊是 從選出的頂點k指過來的 方便打印 Lowcosti=0表示i號頂點在生成樹中下標0123456lowcost00111228adjvex0001110找頂點更新數組i=1王道考研/CSKAOYAN.COM普利姆算法

41、普利姆(Prim)算法012345651122015841831224Void MiniSpanTree_Prim(MGraph G) int min,i,j,k; int adjvexMAXVEX; /保存鄰接頂點下標的數組 int lowcostMAXVEX; /記錄當前生成樹到剩余頂點的最小權值 lowcost0=0; /將0號頂點(以0號頂點作為第一個頂點)加入生成樹 adjvex0=0; /由于剛開始生成樹只有一個頂點 不存在邊 干脆都設為0 for(i=1;iG.vexnum;i+) /除下標為0以外的所有頂點 lowcosti=G.arc0i; /將與下標為0的頂點有邊的權值存入

42、Lowcost數組 adjvexi=0; /這些頂點的adjvex數組全部初始化為0 /算法核心 for(i=1;iG.vexnum;i+)/只需要循環N-1次，N為頂點數 min=65535; /tip：因為要找最小值，不妨先設取一個最大的值來比較 j=0;k=0; /找出lowcost最小的 最小權值給min，下標給k while(jG.vexnum) /從1號頂點開始找 if(lowcostj!=0 & lowcostj%d)”,adjvexk,k); /打印權值最小的邊 lowcostk=0; /將這個頂點加入生成樹 /生成樹加入了新的頂點 從下標為1的頂點開始更新lowcost數組值

43、 for(j=0;jG.vexnum;j+) if(lowcostj!=0 & G.arckjlowcostj) /如果新加入樹的頂點k使得權值變小 lowcostj=G.arckj; /更新更小的權值 adjvexj=k; /修改這條邊鄰接的頂點 也就是表示這條邊是 從選出的頂點k指過來的 方便打印 Lowcosti=0表示i號頂點在生成樹中下標0123456lowcost00111228adjvex0001110找頂點更新數組i=2王道考研/CSKAOYAN.COM普利姆算法普利姆(Prim)算法012345651122015841831224Void MiniSpanTree_Prim(

44、MGraph G) int min,i,j,k; int adjvexMAXVEX; /保存鄰接頂點下標的數組 int lowcostMAXVEX; /記錄當前生成樹到剩余頂點的最小權值 lowcost0=0; /將0號頂點(以0號頂點作為第一個頂點)加入生成樹 adjvex0=0; /由于剛開始生成樹只有一個頂點 不存在邊 干脆都設為0 for(i=1;iG.vexnum;i+) /除下標為0以外的所有頂點 lowcosti=G.arc0i; /將與下標為0的頂點有邊的權值存入Lowcost數組 adjvexi=0; /這些頂點的adjvex數組全部初始化為0 /算法核心 for(i=1;i

45、G.vexnum;i+)/只需要循環N-1次，N為頂點數 min=65535; /tip：因為要找最小值，不妨先設取一個最大的值來比較 j=0;k=0; /找出lowcost最小的 最小權值給min，下標給k while(jG.vexnum) /從1號頂點開始找 if(lowcostj!=0 & lowcostj%d)”,adjvexk,k); /打印權值最小的邊 lowcostk=0; /將這個頂點加入生成樹 /生成樹加入了新的頂點 從下標為1的頂點開始更新lowcost數組值 for(j=0;jG.vexnum;j+) if(lowcostj!=0 & G.arckj4）i=2王道考研/C

46、SKAOYAN.COM普利姆算法普利姆(Prim)算法012345651122015841831224Void MiniSpanTree_Prim(MGraph G) int min,i,j,k; int adjvexMAXVEX; /保存鄰接頂點下標的數組 int lowcostMAXVEX; /記錄當前生成樹到剩余頂點的最小權值 lowcost0=0; /將0號頂點(以0號頂點作為第一個頂點)加入生成樹 adjvex0=0; /由于剛開始生成樹只有一個頂點 不存在邊 干脆都設為0 for(i=1;iG.vexnum;i+) /除下標為0以外的所有頂點 lowcosti=G.arc0i; /

47、將與下標為0的頂點有邊的權值存入Lowcost數組 adjvexi=0; /這些頂點的adjvex數組全部初始化為0 /算法核心 for(i=1;iG.vexnum;i+)/只需要循環N-1次，N為頂點數 min=65535; /tip：因為要找最小值，不妨先設取一個最大的值來比較 j=0;k=0; /找出lowcost最小的 最小權值給min，下標給k while(jG.vexnum) /從1號頂點開始找 if(lowcostj!=0 & lowcostj%d)”,adjvexk,k); /打印權值最小的邊 lowcostk=0; /將這個頂點加入生成樹 /生成樹加入了新的頂點 從下標為1的

48、頂點開始更新lowcost數組值 for(j=0;jG.vexnum;j+) if(lowcostj!=0 & G.arckjlowcostj) /如果新加入樹的頂點k使得權值變小 lowcostj=G.arckj; /更新更小的權值 adjvexj=k; /修改這條邊鄰接的頂點 也就是表示這條邊是 從選出的頂點k指過來的 方便打印 Lowcosti=0表示i號頂點在生成樹中下標0123456lowcost0011120415adjvex0001144找頂點更新數組i=2王道考研/CSKAOYAN.COM普利姆算法普利姆(Prim)算法012345651122015841831224Void

49、MiniSpanTree_Prim(MGraph G) int min,i,j,k; int adjvexMAXVEX; /保存鄰接頂點下標的數組 int lowcostMAXVEX; /記錄當前生成樹到剩余頂點的最小權值 lowcost0=0; /將0號頂點(以0號頂點作為第一個頂點)加入生成樹 adjvex0=0; /由于剛開始生成樹只有一個頂點 不存在邊 干脆都設為0 for(i=1;iG.vexnum;i+) /除下標為0以外的所有頂點 lowcosti=G.arc0i; /將與下標為0的頂點有邊的權值存入Lowcost數組 adjvexi=0; /這些頂點的adjvex數組全部初始化

50、為0 /算法核心 for(i=1;iG.vexnum;i+)/只需要循環N-1次，N為頂點數 min=65535; /tip：因為要找最小值，不妨先設取一個最大的值來比較 j=0;k=0; /找出lowcost最小的 最小權值給min，下標給k while(jG.vexnum) /從1號頂點開始找 if(lowcostj!=0 & lowcostj%d)”,adjvexk,k); /打印權值最小的邊 lowcostk=0; /將這個頂點加入生成樹 /生成樹加入了新的頂點 從下標為1的頂點開始更新lowcost數組值 for(j=0;jG.vexnum;j+) if(lowcostj!=0 &

51、G.arckjlowcostj) /如果新加入樹的頂點k使得權值變小 lowcostj=G.arckj; /更新更小的權值 adjvexj=k; /修改這條邊鄰接的頂點 也就是表示這條邊是 從選出的頂點k指過來的 方便打印 Lowcosti=0表示i號頂點在生成樹中下標0123456lowcost0011120415adjvex0001144找頂點更新數組i=3王道考研/CSKAOYAN.COM普利姆算法普利姆(Prim)算法012345651122015841831224Void MiniSpanTree_Prim(MGraph G) int min,i,j,k; int adjvexMAX

52、VEX; /保存鄰接頂點下標的數組 int lowcostMAXVEX; /記錄當前生成樹到剩余頂點的最小權值 lowcost0=0; /將0號頂點(以0號頂點作為第一個頂點)加入生成樹 adjvex0=0; /由于剛開始生成樹只有一個頂點 不存在邊 干脆都設為0 for(i=1;iG.vexnum;i+) /除下標為0以外的所有頂點 lowcosti=G.arc0i; /將與下標為0的頂點有邊的權值存入Lowcost數組 adjvexi=0; /這些頂點的adjvex數組全部初始化為0 /算法核心 for(i=1;iG.vexnum;i+)/只需要循環N-1次，N為頂點數 min=65535

53、; /tip：因為要找最小值，不妨先設取一個最大的值來比較 j=0;k=0; /找出lowcost最小的 最小權值給min，下標給k while(jG.vexnum) /從1號頂點開始找 if(lowcostj!=0 & lowcostj%d)”,adjvexk,k); /打印權值最小的邊 lowcostk=0; /將這個頂點加入生成樹 /生成樹加入了新的頂點 從下標為1的頂點開始更新lowcost數組值 for(j=0;jG.vexnum;j+) if(lowcostj!=0 & G.arckj5）i=3王道考研/CSKAOYAN.COM普利姆算法普利姆(Prim)算法01234565112

54、2015841831224Void MiniSpanTree_Prim(MGraph G) int min,i,j,k; int adjvexMAXVEX; /保存鄰接頂點下標的數組 int lowcostMAXVEX; /記錄當前生成樹到剩余頂點的最小權值 lowcost0=0; /將0號頂點(以0號頂點作為第一個頂點)加入生成樹 adjvex0=0; /由于剛開始生成樹只有一個頂點 不存在邊 干脆都設為0 for(i=1;iG.vexnum;i+) /除下標為0以外的所有頂點 lowcosti=G.arc0i; /將與下標為0的頂點有邊的權值存入Lowcost數組 adjvexi=0; /

55、這些頂點的adjvex數組全部初始化為0 /算法核心 for(i=1;iG.vexnum;i+)/只需要循環N-1次，N為頂點數 min=65535; /tip：因為要找最小值，不妨先設取一個最大的值來比較 j=0;k=0; /找出lowcost最小的 最小權值給min，下標給k while(jG.vexnum) /從1號頂點開始找 if(lowcostj!=0 & lowcostj%d)”,adjvexk,k); /打印權值最小的邊 lowcostk=0; /將這個頂點加入生成樹 /生成樹加入了新的頂點 從下標為1的頂點開始更新lowcost數組值 for(j=0;jG.vexnum;j+)

56、 if(lowcostj!=0 & G.arckjlowcostj) /如果新加入樹的頂點k使得權值變小 lowcostj=G.arckj; /更新更小的權值 adjvexj=k; /修改這條邊鄰接的頂點 也就是表示這條邊是 從選出的頂點k指過來的 方便打印 Lowcosti=0表示i號頂點在生成樹中下標0123456lowcost001112003adjvex0001145找頂點更新數組i=3王道考研/CSKAOYAN.COM普利姆算法普利姆(Prim)算法012345651122015841831224Void MiniSpanTree_Prim(MGraph G) int min,i,j

57、,k; int adjvexMAXVEX; /保存鄰接頂點下標的數組 int lowcostMAXVEX; /記錄當前生成樹到剩余頂點的最小權值 lowcost0=0; /將0號頂點(以0號頂點作為第一個頂點)加入生成樹 adjvex0=0; /由于剛開始生成樹只有一個頂點 不存在邊 干脆都設為0 for(i=1;iG.vexnum;i+) /除下標為0以外的所有頂點 lowcosti=G.arc0i; /將與下標為0的頂點有邊的權值存入Lowcost數組 adjvexi=0; /這些頂點的adjvex數組全部初始化為0 /算法核心 for(i=1;iG.vexnum;i+)/只需要循環N-1

58、次，N為頂點數 min=65535; /tip：因為要找最小值，不妨先設取一個最大的值來比較 j=0;k=0; /找出lowcost最小的 最小權值給min，下標給k while(jG.vexnum) /從1號頂點開始找 if(lowcostj!=0 & lowcostj%d)”,adjvexk,k); /打印權值最小的邊 lowcostk=0; /將這個頂點加入生成樹 /生成樹加入了新的頂點 從下標為1的頂點開始更新lowcost數組值 for(j=0;jG.vexnum;j+) if(lowcostj!=0 & G.arckjlowcostj) /如果新加入樹的頂點k使得權值變小 lowc

59、ostj=G.arckj; /更新更小的權值 adjvexj=k; /修改這條邊鄰接的頂點 也就是表示這條邊是 從選出的頂點k指過來的 方便打印 Lowcosti=0表示i號頂點在生成樹中下標0123456lowcost001112003adjvex0001145找頂點更新數組i=4王道考研/CSKAOYAN.COM普利姆算法普利姆(Prim)算法012345651122015841831224Void MiniSpanTree_Prim(MGraph G) int min,i,j,k; int adjvexMAXVEX; /保存鄰接頂點下標的數組 int lowcostMAXVEX; /記錄

60、當前生成樹到剩余頂點的最小權值 lowcost0=0; /將0號頂點(以0號頂點作為第一個頂點)加入生成樹 adjvex0=0; /由于剛開始生成樹只有一個頂點 不存在邊 干脆都設為0 for(i=1;iG.vexnum;i+) /除下標為0以外的所有頂點 lowcosti=G.arc0i; /將與下標為0的頂點有邊的權值存入Lowcost數組 adjvexi=0; /這些頂點的adjvex數組全部初始化為0 /算法核心 for(i=1;iG.vexnum;i+)/只需要循環N-1次，N為頂點數 min=65535; /tip：因為要找最小值，不妨先設取一個最大的值來比較 j=0;k=0; /