圖的算法實現(xiàn)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告設(shè)計題目：圖的算法實現(xiàn)班 級：學(xué) 號： 姓 名:數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告內(nèi)容課 程設(shè)計題目圖的算法實現(xiàn)【基本要求】（ 1）建立一文件，將圖的信息存在此文件中；（ 2）從此文件讀入圖的信息，建立鄰接矩陣和鄰接表；（ 3）實現(xiàn)Prim、 Kruskal 、 Dijkstra 和拓?fù)渑判蛩惴ā６惴ㄔO(shè)計思想（ 1）圖的存儲結(jié)構(gòu)：鄰接矩陣：用兩個數(shù)組分別存儲數(shù)據(jù)元素（頂點）的信息和數(shù)據(jù)元素之間的關(guān)系（邊或?。┑男畔?。鄰接表：對圖中的每個頂點建立一個單鏈表，第 i 個單鏈表中的結(jié)點表示依附于頂點 Vi 的邊（對有向圖是以頂點 Vi 為尾的?。?。每個結(jié)點由 3個域組成，其中鄰接點域指示與頂

2、點Vi 鄰接的點在圖中的位置，鏈域指示下一條邊或弧的結(jié)點；數(shù)據(jù)域存儲和邊或弧相關(guān)的信息。每個鏈表上附設(shè)一個表頭結(jié)點。在表頭結(jié)點中，除了設(shè)有鏈域指向鏈表中第一個結(jié)點之外，還設(shè)有存儲頂點 Vi 的名或其他相關(guān)信息的數(shù)據(jù)域。prim 算法是一種求圖的最小生成樹的算法。假設(shè)N=（V, E）是連通網(wǎng)，TEM Nk最小生成樹中邊的集合。算 法從U= u0 （u0 6V）、TE= 開始。重復(fù)執(zhí)行下列操作：在所有u6U, v6V UW邊（u, v） 6 E中找一條權(quán)彳1最小的邊（u0,v0）并入集合TE中， 同時v0并入U,直到丫= Ufe止。此時，TE中必有n-1條邊，T=（V, TE）為G 的最小生成樹。

3、Prim算法的核心：始終保持TE中的邊集構(gòu)成一棵生成樹。Kruskal 算法Kruskal 算法是另一種求最小生成樹的算法他的基本思想是以邊為主導(dǎo)地位，始終選擇當(dāng)前可用（所選的邊不能構(gòu)成回路）的最小權(quán)植邊。所以 Kruskal 算法的第一步是給所有的邊 按照從小到大的順序排序。具體實現(xiàn)過程如下：設(shè)一個有n個頂點的連通網(wǎng)絡(luò)為G （V,E）,最初先構(gòu)造一個只 有n個頂點，沒有邊的非連通圖T=V,空,圖中每個頂點自成一格連通 分量。在E中選擇一條具有最小權(quán)植的邊時，若該邊的兩個頂點落 在不同的連通分量上，則將此邊加入到T中；否則，即這條邊的兩個頂 點落到同一連通分量上，則將此邊舍去（此后永不選用這條

4、邊），重新 選擇一條權(quán)植最小的邊。 如此重復(fù)下去，直到所有頂點在同一連通分量上為止 。（4） Dijkstar 算法Dijkstra 算法是典型最短路徑算法， 用于計算一個節(jié)點到其他節(jié)點 的最短路徑。它的主要特點是以起始點為中心向外層層擴(kuò)展直到擴(kuò)展到終點為 止?；舅枷胪ㄟ^Dijkstra計算圖G的最短路徑時，需要指定起點s（即從頂點s 開始計算 ） 。此外，引進(jìn)兩個集合 纖口U。S的作用是記錄已求出最短路徑的頂點 （以及相應(yīng)的最短路徑長度），而UM是記錄還未求出最短路徑的頂點（以 及該頂點到起點s 的距離） 。初始時，S中只有起點s; U中是除s之外的頂點，并且U中頂點的路 徑是”起點s到該

5、頂點的路徑”。然后，從U中找出路徑最短的頂點，并 將其加入到S中；接著，更新U中的頂點和頂點對應(yīng)的路徑。 然后，再 從U中找出路徑最短的頂點，并將其加入到 S中；接著，更新U中的頂點 和頂點對應(yīng)的路徑。 重復(fù)該操作，直到遍歷完所有頂點。操作步驟1初始時，S只包含起點s; U包含除s外的其他頂點，且U中頂點的 距離為起點s到該頂點的距離”例如，U中頂點v的距離為（s,v）的長 度，然后s和v不相鄰，則v的距離為00 。2從U中選出”距離最短的頂點k，并將頂點k加入到S中；同時, 從U中移除頂點k。3更新Lfr各個頂點到起點s的距離。之所以更新U+頂點的距離， 是由于上一步中確定了 k是求出最短路

6、徑的頂點，從而可以利用k來更新 其它頂點的距離；例如，(s,v)的距離可能大于(s,k)+(k,v) 的距離。4重復(fù)步驟(2)和(3),直到遍歷完所有頂點。(5)拓?fù)渑判?在有向圖中選一個沒有直接前驅(qū)的頂點，并輸出之；2從圖中刪去該頂點，同時刪去所有它發(fā)出的有向邊；重復(fù)以上步驟，直到全部頂點均已輸出，拓?fù)溆行蛐蛄行纬?，拓?fù)?排序完成；或圖中還有未輸出的頂點，但已跳出處理循環(huán)。這說明圖中 還剩下一些頂點，它們都有直接前驅(qū)，再也找不到?jīng)]有前驅(qū)的頂點了。 這時有向圖中必定存在有向環(huán)。二.程序結(jié)構(gòu)此工程包含一個頭文件，和六個源文件f graph.cppprim.cpp D Dijstar.cppGra

7、ph.hKruskal.cppTopologicalSort.cpp（創(chuàng)建鄰接表）主函數(shù)main.cppprintALGraph（輸出鄰接表）CreatALGraph （創(chuàng)建鄰接表）CreatMGraph（創(chuàng)建鄰接矩陣）printMGraph（輸出鄰接矩陣）freopenprim（包含在stdio.h頭文件中，用于保證不改 變原代碼的情況下，進(jìn)行文件的輸入與輸 出）Dijstar（快速排序）Kruskal sort funTopologicalSort四.實驗結(jié)果與分析.用戶使用說明打開圖的項目運(yùn)行或打開圖.exe文件運(yùn)行在prim求最小生成樹時輸入（A-E）一個大寫的起源頂點Dijkstar

8、求最短路徑時同上如果需要更改圖請打開graphin.txt按如下格式更改第一行：輸入頂點和邊數(shù)（格式：4,3）第二行：輸入頂點（格式：abcd）第三行：輸入頂點間的邊關(guān)系（格式：a,b,1 一行一條邊信息，回車結(jié)束）樣例：4,3abcda,b,1b,c,2a,d,3. 測試結(jié)果測試數(shù)據(jù)：5,7ABCDEA,B,1A,C,6A,D,2B,C,5B,D,8D,E,3C,E,4 圖的鄰接表與鄰接矩陣存儲圖的鄰接表,-CC-E（4）b-E（3）圖的鄰接矩陣信息如下:A B C D E0 1 6 2 0B 0 0 5 2 0C 0 0 0 0 4D 0 CJ 0 0 3E 0 0 0 0 0Prim算法

9、求最小生成樹用pti異法求題小生成樹 情棚入起源頂點=A選 BKA, D) 0,E) SC)Kruskal算法求最小生成樹Kruskal算法求出的最小生成樹3（星 B） 1 CA, D） 2 （D, E） 3 （C,E） 4Dijkstar算法求最短路徑Di jkstaz求最短路徑,輸入起源頂點；A-B 1t-C 6f-D 2k-E 5拓?fù)渑判蛲負(fù)渑判虻慕Y(jié)果A-B-C-D-E測試數(shù)據(jù)4,4ABCDA,B,1A,C,6A,D,2B,C,5圖的鄰接表與鄰接矩陣存儲圖的鄰接表:AOD -XX6”E B-C I-I圖的鄰接矩陣信息1如下:C65OOB 1 o o O A o o o OD2000Pri

10、m算法求最小生成樹用”萬方法求甌小生成樹 請輸入起旗放點;A0 B)& D) (B, C)Kruskal算法求最小生成樹Kmsk式算法求出的最小生成樹：(A, B) 1 0, D) 2 (B, C) 5Dijkstar算法求最短路徑入1 6 2輸中c?拓?fù)渑判?.調(diào)試分析在文件的讀入中，會出現(xiàn)字符的讀取出錯，將回車讀入，在經(jīng)過 網(wǎng)上的搜索和查閱之后，我找到并學(xué)會了freopen函數(shù)（包含在在頭文件 stdio.h 中），比如 freopen（graphin.txt,r,stdin）的作用就是把標(biāo) 準(zhǔn)輸入流stdin重定向到graphin.txt文件中，這樣在用scanf輸入時便 不會從標(biāo)準(zhǔn)輸入

11、流讀取數(shù)據(jù)，而是從graphin.txt文件中獲取輸入。這樣 就可以直接在graphin.txt文件中更改數(shù)據(jù)，方便讀入。五.總結(jié)（收獲與體會）在一周的實驗課程后，我加深了對數(shù)據(jù)結(jié)構(gòu)的理解，熟練了對圖 和四個算法的操作。加強(qiáng)了查閱相關(guān)文獻(xiàn)書籍的能力；加深對于所學(xué) 內(nèi)容的理解，并能將其實踐出，或許會有許多瑕疵但也十分不錯。在 這次的實驗中，我遇到了很多困難，在請教同學(xué)和網(wǎng)上查閱之后將其 一一解決，從中我汲取了同學(xué)的意見網(wǎng)上的講解，有了自己對各種算 法新的認(rèn)識與見解，并能將其程序化實現(xiàn)。在寫代碼的過程中，有著許多的 bug,其中有邏輯錯誤和語法錯 誤，苦惱著我，一次次的改動也磨礪著我的內(nèi)心。尤其是

12、邏輯錯誤， 在調(diào)試的過程中，一次又一次更改邏輯錯誤，讓人很是暴躁所以在這 次的實驗中，也磨礪了我浮躁的內(nèi)心，只有耐心冷靜才能將代碼的錯 誤找出，也只有冷靜才能使大腦清晰，邏輯順暢。在這一周的實驗，讓我收獲頗多，有了程序員的一些素養(yǎng)，磨礪了自己的心性，做事變得有規(guī)劃。六 源程序Graph.h#include#include#includedefine MaxVertices 100define INF 65999define MVNUM 100define OK 1#define ERROR -1/* 鄰接矩陣 */typedef struct graph/ 圖的鄰接矩陣的定義char Vert

13、icesMaxVertices;/ 頂點信息int EdgeMaxVerticesMaxVertices;/ 邊信息int numV;/ 頂點數(shù)int numE;/ 邊數(shù)MGraph;/* 鄰接表 */typedef int InfoType;typedef char VertexType;typedef struct ArcNode/邊結(jié)點的類型定義int adjvex;/ 邊的另一頂點在數(shù)組的位置struct ArcNode *next;/指向下一邊的指針int info;/ 邊的信息ArcNode;typedef struct VNode/ 頂點結(jié)點int in;VertexType d

14、ata;/ 頂點信息ArcNode *firstarc;/ 指向關(guān)聯(lián)該頂點的邊鏈表VNode,AdjListMVNUM;typedef structAdjList vertices;int vexnum,arcnum;/ 圖的當(dāng)前頂點數(shù)和邊數(shù)ALGraph;typedef structchar begin;char end;int weight;closeEdge;/ 鄰接矩陣void search(MGraph &G,char v1,char v2,int w);/ 尋找頂點位置，存入邊信息void CreatMGraph(MGraph &G,FILE *fp);/ 生成圖 (鄰接矩陣 )v

15、oid printMGraph(MGraph G);/ 輸出圖/ 鄰接表int locateMGraph(MGraph G,char u);/ 確定頂點位置int LocateALGraph(ALGraph G,VertexType x);/尋找頂點的位置void CreatALGraph(ALGraph &G,FILE *fp);/ 建立鄰接表void printALGraph(ALGraph G);/ 輸出鄰接表/primvoid prim(MGraph G);/pirm 求最小生成樹/Kruskalint Find(int *parent,int i);int fun(closeEdge

16、 *arr,int low,int high);/快排void sort(closeEdge *arr,int low,int high); /快排void Kruskal(MGraph G);/Kruskal 算法/ 拓?fù)渑判騣nt TopologicalSort(ALGraph G);/ 拓?fù)渑判蛩惴?Dijkstarvoid Dijkstar(MGraph G);/ Dijkstar 算法prim.cpp#includeGraph.h求最小生成樹void prim(MGraph G)/pirmn);printf(nprintf(nt 用 prim 算法求最小生成樹n);char u; p

17、rintf( 請輸入起源頂點： ); scanf(%c,&u); getchar(); char adjvexMaxVertices;/頂點int lowcostMaxVertices;/邊的權(quán)值int k,i,j,min;k=locateMGraph(G,u);for(i=1;i=G.numV;i+)/ 初始化輔助數(shù)組 if(i!=k) adjvexi=u; lowcosti=G.Edgeki;/ 到 u 點的距離 adjvexk=u;lowcostk=0;for(i=1;iG.numV;i+)/ 構(gòu)造最小生成樹 min=INF;/ 初始化最小權(quán)值為 inf 不可能數(shù)值 j=1; k=0;

18、while(j=G.numV)/ 遍歷全部頂點 if(lowcostj!=0&lowcostjmin)/ 找出 lowcost 數(shù) 組已存入的最小權(quán)值 min=lowcostj; k=j;/ 下標(biāo)存入 k ；j+;printf(%c,%c),adjvexk,G.Verticesk);/打印當(dāng)前頂點中權(quán)值最小的邊lowcostk=0;/ 將當(dāng)前頂點的權(quán)值設(shè)置為0，表示此頂點已經(jīng)完成任務(wù)for(j=1;j=G.numV;j+)/ 圖的 k 行依次遍歷全部頂點if(lowcostj!=0&G.Edgekj0)i=parenti;return i;int fun(closeEdge *arr,int

19、low,int high)int key;closeEdge lowx;lowx=arrlow;key=arrlow.weight;while(lowhigh)while(low=key)high-;if(lowhigh)arrlow+=arrhigh;while(lowhigh & arrlow.weight=key)low+;if(lowhigh)arrhigh-=arrlow;arrlow=lowx;return low;void sort(closeEdge *arr,int low,int high)/快排int temp;if(lowhigh)temp=fun(arr,low,hi

20、gh);sort(arr,low,temp-1);sort(arr,temp+1,high);void Kruskal(MGraph G)printf(nn);printf(ntKruskal 算法求出的最小生成樹： n);int i,j,n,m,flag=1;closeEdge edgesMaxVertices;/ 定義邊數(shù)組int parentMaxVertices;/ 用來判斷是夠形成環(huán)路for(i=1;i=G.numV;i+)/ 存入邊信息for(j=i;j=G.numV;j+)if(G.Edgeij!=INF)edgesflag.begin=G.Verticesi;edgesflag

21、.end=G.Verticesj;edgesflag.weight=G.Edgeij;flag+;sort(edges,1,G.numE);for(i=1;i=G.numV;i+)/ 初始化為 0parenti=0;for(i=1;i=G.numE;i+)n=Find(parent,locateMGraph(G,edgesi.begin);m=Find(parent,locateMGraph(G,edgesi.end);if(n!=m)/ 如果門=m!就形成環(huán)路parentn=m;/ 將此邊的結(jié)尾頂點放入下標(biāo)為起點的parent 數(shù)組中，表示此頂點已經(jīng)在生成樹集合中printf(%c,%c)

22、%d,edgesi.begin,edgesi.end,edgesi.weight);printf(n);Dijkstar.cpp#includeGraph.hvoid Dijkstar(MGraph G)printf(nn);printf(ntDijkstar char V0;求最短路徑n);printf( 請輸入起源頂點： );scanf(%c,&V0);getchar();int i,j,k,min,n;n=locateMGraph(G,V0);int finalMaxVertices;/finalw表示已經(jīng)求得頂點 V0-Vw的最短路徑int PMaxVertices;/ 用于存儲最短路

23、徑下標(biāo)的數(shù)組int DMaxVertices; / 用于存儲到各點最短路徑的權(quán)值和for(i=1;i=G.numV;i+)/ 初始化數(shù)據(jù)finali=0;/ 全部頂點初始化為未找到的最短路徑Di=G.Edgeni; 將于V0有連線的頂點加上權(quán)值Pi=0;/ 初始化路徑數(shù)組p 為 0Dn=0;/V0-V0 的路徑為0finaln=1; /V0-V0 不需要求路徑for(i=1;i=G.numV;i+)/每次循環(huán)求得V0到某個點的最短路徑 min=INF;for(j=1;j=G.numV;j+) if(!finalj&Djmin) k=j; min=Dj;finalk=1;/ 將目前找到的最近的頂點置為 1for(j=1;j=G.numV;j+) if(!finalj&(min+G.Edgekj)Dj)/如果經(jīng)過 v頂點的路徑比現(xiàn)在這條路經(jīng)短的話，更新Dj=min+G.Edgekj;/ 修改當(dāng)前路徑長度Pj=k; / 存放前驅(qū)頂點for(i=1;i%c %dn,V0,G.Verticesi,Di);TopologicalSort.cpp#includeGraph.hint TopologicalSort(ALGraph G)printf(nn);printf(nt 拓?fù)渑判虻慕Y(jié)果n);ArcNode *e;e=(ArcNode*)malloc(siz