數(shù)據(jù)結(jié)構(gòu)圖實(shí)現(xiàn)

1、北京郵電大學(xué)信息與通信工程學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱： 實(shí)驗(yàn)二圖學(xué)生姓名： 班 級(jí)： 11111班內(nèi)序號(hào)： 學(xué) 號(hào)： 2014日 期： 1實(shí)驗(yàn)要求根據(jù)圖的抽象數(shù)據(jù)類型的定義，使用鄰接矩陣或鄰接表實(shí)現(xiàn)一個(gè)圖。圖的基本功能：1、圖的建立2、圖的銷毀3、深度優(yōu)先遍歷圖4、廣度優(yōu)先遍歷圖 5、使用普里姆算法生成最小生成樹(shù)6、使用克魯斯卡爾算法生成最小生成樹(shù)7、求指定頂點(diǎn)到其他各頂點(diǎn)的最短路徑8、其他：比如連通性判斷等自定義操作編寫測(cè)試main()函數(shù)測(cè)試圖的正確性2. 程序分析基類-圖（Graph）² Graph() /圖的初始化² Graph() /圖的銷毀² Pri

2、nt() /圖矩陣的打印² vNum /頂點(diǎn)個(gè)數(shù)² arc /鄰接矩陣² eNum /邊的條數(shù)² Empty(); /置空?qǐng)D² DFS(); /深度優(yōu)先遍歷² BFS(); /廣度優(yōu)先遍歷派生類-無(wú)向圖（Ugraph）Ø creatGraph(); Ø Prim();Ø Kruskal();Ø isConnected()； 派生類-有向圖（Dgraph）Ø creatGraph();Ø FloydPath(); Ø DijkstraPath(int); Ø

3、 isConnected()； 主函數(shù)-main()2.1 存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)結(jié)構(gòu)實(shí)現(xiàn)圖順序表一維數(shù)組2.2 關(guān)鍵算法分析算法【1】：creatGraph()算法功能：創(chuàng)建一個(gè)有向圖或無(wú)向圖算法基本思想：在堆在申請(qǐng)一個(gè)N*N的一維數(shù)組存儲(chǔ)各邊權(quán)值算法復(fù)雜度分析：N個(gè)頂點(diǎn)需要設(shè)置O(N*N)次代碼邏輯：A. cin>>vNum,arc=new intN*N,輸入頂點(diǎn)數(shù)并建立鄰接矩陣arcB. 如果是無(wú)向圖，則cin>>weight,arcij=arcji，并設(shè)定arcii=Max;同時(shí)，weight為0的同樣設(shè)為Max;C. 如果是有向圖，則cin>>w

4、eight1>>weight2,arcij=weight1,arcji=weight2,并設(shè)定arcii=Max; 同時(shí)，weight為0的同樣設(shè)為Max;D. 記錄有效邊的條數(shù)eNum;算法【2】：DFS(int v),DFSing(int v,int *visited)算法功能：無(wú)向圖的深度優(yōu)先遍歷算法基本思想：1. 從圖中任一頂點(diǎn)V出發(fā)，標(biāo)記V已訪問(wèn)；2. 訪問(wèn)V的第一個(gè)未訪問(wèn)的鄰接點(diǎn)W,標(biāo)記W為已訪問(wèn)；3. 訪問(wèn)W的第一個(gè)未訪問(wèn)的鄰接點(diǎn)U,標(biāo)記U為已訪問(wèn)；4. 若當(dāng)前頂點(diǎn)沒(méi)有未訪問(wèn)的鄰接頂點(diǎn)，則回溯，繼續(xù)深度遍歷。算法復(fù)雜度分析：每訪問(wèn)一個(gè)頂點(diǎn)需要遍歷一行N,遍歷N個(gè)頂點(diǎn)則

5、為O(N*N)代碼邏輯：A. bool *visited=new intvNum(=false);visitedv=true /初始化B. for(j=0;j<vNum;j+)If(arcij!=Max && visitedj=false) /避開(kāi)間斷邊和已訪問(wèn)點(diǎn)Cout<<j; /輸出節(jié)點(diǎn)visitedj=true; /設(shè)置j為已訪問(wèn)DFSing(v,visited) /遞歸遍歷C. deletevisited;算法【3】：BFS(int v)算法功能：無(wú)向圖的廣度優(yōu)先遍歷算法基本思想：1. 從圖中任一頂點(diǎn)V出發(fā)，標(biāo)記V已訪問(wèn)；2. 依次訪問(wèn)所有未被訪問(wèn)的鄰

6、接頂點(diǎn)V1,V2,V3并標(biāo)記3. 分別從V1,V2,V3出發(fā)并依次訪問(wèn)它們未被訪問(wèn)的鄰接頂點(diǎn)反復(fù)1,2,3直到所有和V相通的頂點(diǎn)都被訪問(wèn)到算法復(fù)雜度分析：結(jié)合遍歷一行及遞歸，時(shí)間復(fù)雜度為O(N+e)，空間則為O(N)代碼邏輯：A. Bool *visited=new boolvNum(=false);visitedv=true;B. Int *queue =new intvNum,f=0,r=0,queuer+=v;C. While(f!=r)Cout<<queuef+;For(i=0;i<vNum;i+)If(arcij!=Max && visitedj=f

7、alse)Queuer+=j;visitedj=true;D. Deletequeue;deletevisited;算法【4】：Prim()算法功能：從頂點(diǎn)角度選出最小生成樹(shù)算法基本思想：N個(gè)頂點(diǎn)分屬兩集合U和U-V，U包含已落樹(shù)的頂點(diǎn)，U-V包含未落到樹(shù)上的頂點(diǎn)。然后不斷尋找U和U-V中各頂點(diǎn)間的最小權(quán)值邊，直到所有頂點(diǎn)落到集合U中。算法復(fù)雜度分析：此算法需要兩次循環(huán)遍歷所有結(jié)點(diǎn)，時(shí)間復(fù)雜度為O(N*N)代碼邏輯：A. Bool *U=new boolvNum(=true);Uv=false; /建立并初始化U集合和U-V集合的數(shù)組，這里用一個(gè)bool數(shù)組U表示，Ui為true表明頂點(diǎn)i為U

8、-V集合，為false表明頂點(diǎn)i為U集合；B. Int min3;min2=Max;min0=min1=v;/設(shè)定一個(gè)數(shù)組min3,前兩位保存最小邊的兩頂點(diǎn)，第3位保存邊權(quán)值,將min2初始化為MaxC. For(找到U集合的頂點(diǎn)，即Ui=true)For(找到U-V集合的頂點(diǎn)，即Uj=false)If(arcij<min2)Min0=i;min1=j,min2=arcij;/更新數(shù)組min3)每次循環(huán)完后必能找到最小值，將j頂點(diǎn)從U-V集合中刪除并添加到U集合，即Ui=false;D. 反復(fù)執(zhí)行C步驟，N個(gè)頂點(diǎn)需要執(zhí)行N-1次，用一個(gè)count變量和while循環(huán)計(jì)數(shù)。Whlie(co

9、unt!=N)count+;算法【5】：Kruskal()算法功能：從邊的角度選出最小生成樹(shù)算法基本思想：首先對(duì)邊從小到大排序，然后依次挑取最小權(quán)值的邊到生成樹(shù)中，此過(guò)程里每添加一條新邊需要判斷是否會(huì)構(gòu)成回路，一旦構(gòu)成回路則放棄此邊。算法復(fù)雜度分析：此算法主要來(lái)自于邊的排序，時(shí)間復(fù)雜度為O(N*N)代碼邏輯：A. 準(zhǔn)備好struct Vedge int fromV,endV,weight;Vedge *edgelist=new VedgevNum.B. For(i=0;i<vNum;i+)For(j=0;j<vNum;j+;count+)Edgelistcount(fromV=i,

10、endV=j,weight=arcij;C. bubblesort(edgelist)，用冒泡排序邊集數(shù)組，排序代碼此處省略D. int *vset=new intvNum(0,1,2,3,N-1) /建立頂點(diǎn)集合數(shù)組vset并用for循環(huán)初始化為自然數(shù)列0,1,2,3N-1；E. for(i=0;i<eNum;i+)遍歷邊集數(shù)組edgelisti，If(vsetfromV=vsetendV) continue; /邊兩頂點(diǎn)同屬一數(shù)組時(shí)跳過(guò)Cout<<fromV和endVFor(j=0;j<vNum;j+) /遍歷vset集合更新信息 /將所有和頂點(diǎn)fromV具有相同集

11、合的點(diǎn)調(diào)整成endV的集合If(vsetj=vsetfromV) vsetj=vsetendVF. deleteedgelist;deletevset;算法【6】：FloydPath();算法功能：求出任意兩頂點(diǎn)間的最短路徑算法基本思想：1. 若<Vi,Vj>存在，則路徑存在<Vi,Vj>；2. 若<Vi,Vl>，<Vl,Vj>存在，則存在路徑<Vi,Vl,Vj>；3. 若<Vi,V2>，<V2,Vj>存在，則存在路徑<Vi,V2,Vj>；依次類推，直到選出所有路徑中的最小值。算法復(fù)雜度分析：核心的

12、3重循環(huán)每一層需遍歷N次，則時(shí)間復(fù)雜度為O(N3)代碼邏輯：int *dist(new intN*N)(arcN*N);int *path(new intN*N)(判斷通路則設(shè)為arcij中的i,斷路則設(shè)為Max);/-/以上為初始化路徑矩陣for (int k = 0; k < vNum; k+) for (int i = 0; i < vNum; i+)for (int j = 0; j < vNum; j+) if (i = j) continue; /跳過(guò)自身到自身的回路if (distik+distkj < distij)distij = distik+dis

13、tkj;pathij = k; /此時(shí)k為i->j的中轉(zhuǎn)頂點(diǎn)/-/以上Floyd核心的三重循環(huán)，k必須在外層輸出路徑矩陣diskij用兩層for循環(huán)即可輸出路徑信息同Dijkstra算法deletedist;deletepath;deletestack;算法【7】：DijkstraPath(int)算法功能：求出一個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑算法基本思想：1. 首先找出源點(diǎn)能直達(dá)的最短路徑頂點(diǎn)和邊2. 然后以上一頂點(diǎn)為中轉(zhuǎn)頂點(diǎn)，找出經(jīng)過(guò)此中轉(zhuǎn)頂點(diǎn)后的最短路徑，此時(shí)如果從源點(diǎn)到目的點(diǎn)路徑更短，則不必中轉(zhuǎn)3. 重復(fù)執(zhí)行2，直到找出所有頂點(diǎn)的路徑為止。算法復(fù)雜度分析：每個(gè)頂點(diǎn)需要一次O(N)的迭

14、代，N個(gè)點(diǎn)需要N-1次，時(shí)間復(fù)雜度為O(N*N)代碼邏輯：int *path = new intvNum(Max); /路徑數(shù)組,初始化為Maxint *disk = new intvNum(Max); /路程數(shù)組,初始化為Maxbool *visited = new boolvNum(false); /訪問(wèn)數(shù)組,初始化為falsevisitedv = true; /設(shè)置源點(diǎn)為trueint minV(v), minDis(0), lastV(v), newDis;for (int count = 1; count != vNum; count+) /n個(gè)頂點(diǎn)需要n-1次迭代for (int

15、j = 0; j < vNum; j+)if (visitedj = true) continue;minV = j; /minV要在找最小前初始化為一個(gè)沒(méi)被visit的頂點(diǎn) if (arcik+arckj < diskj) /lastV表示當(dāng)前節(jié)點(diǎn)的前驅(qū) diskj = arcik+arckj; pathj = lastV;for (int j = 0; j < vNum; j+) /找最小路徑和頂點(diǎn)if (visitedj = false && diskj < diskminV)minV = j;visitedminV = true; /更新最小頂點(diǎn)

16、，更新最短路徑，更新末頂點(diǎn)minDis = diskminV;lastV = minV;/-/以上為得到單點(diǎn)出發(fā)到各頂點(diǎn)的最短路徑cout << "下面輸出v" << v << "與其他頂點(diǎn)的最短路徑：" << endl;int p, *stack, top(-1),count(1); /使用一個(gè)臨時(shí)棧將路徑倒序輸出stack = new intvNum;for (int i = 0; i < vNum; i+)if (pathi = Max) continue; /如果是斷路，則不用輸出路徑p =

17、i;while (pathp != Max)stack+top = p; /前驅(qū)結(jié)點(diǎn)入棧p = pathp; /跳轉(zhuǎn)到前驅(qū)結(jié)點(diǎn)cout << '(' << count+ << ") " << "v" << v << ""while (top != -1) /有棧將路徑倒序輸出cout << "->v" << stacktop- << ""cout << &

18、quot; | Distance = " << diski << endl;/-/以上為多此一舉的輸出路徑deletestack;deletepath;deletevisited;deletedisk;2.3 其他編譯環(huán)境Visual Studio 2013無(wú)窮大Max1061109567輸出域?qū)抯l5一維數(shù)組對(duì)應(yīng)矩陣關(guān)系Matrixij=arck,k=i*N+j;3. 程序運(yùn)行結(jié)果測(cè)試流程：按順序執(zhí)行以下流程1- 構(gòu)建一個(gè)有向圖Dgraph對(duì)象，輸入一個(gè)無(wú)向圖（課本P208圖）；2- 打印鄰接矩陣；3- 輸出以各頂點(diǎn)為出發(fā)點(diǎn)的廣度遍歷；4- 輸出以各頂點(diǎn)為出發(fā)點(diǎn)的深度遍歷；5- 輸出以各頂點(diǎn)為出發(fā)點(diǎn)的Dijkstra算法最短路徑；6- 輸出FloydPath算法的各頂點(diǎn)間的最短路徑；7- (清屏)8- 構(gòu)建一個(gè)無(wú)向圖Ugraph對(duì)象，輸入一個(gè)有向圖（課本P207圖）；9- 打印鄰接矩陣；10- 輸出以各頂點(diǎn)為出發(fā)點(diǎn)的廣度遍歷；11- 輸出以各頂點(diǎn)為出發(fā)點(diǎn)的深度遍歷；12- 任取一頂點(diǎn)按Prim算法生成最小生成樹(shù)；13- 用Kruskal算法生成最小生成樹(shù)，并與12的比較是否一致；14- 程序運(yùn)行完畢。運(yùn)行結(jié)果(圖片太大，用鏈接存放)：有向圖