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

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

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

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

4、eight1>>weight2,arcij=weight1,arcji=weight2,并設(shè)定arcii=Max; 同時，weight為0的同樣設(shè)為Max;D. 記錄有效邊的條數(shù)eNum;算法【2】：DFS(int v),DFSing(int v,int *visited)算法功能：無向圖的深度優(yōu)先遍歷算法基本思想：1. 從圖中任一頂點V出發(fā)，標(biāo)記V已訪問；2. 訪問V的第一個未訪問的鄰接點W,標(biāo)記W為已訪問；3. 訪問W的第一個未訪問的鄰接點U,標(biāo)記U為已訪問；4. 若當(dāng)前頂點沒有未訪問的鄰接頂點，則回溯，繼續(xù)深度遍歷。算法復(fù)雜度分析：每訪問一個頂點需要遍歷一行N,遍歷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) /避開間斷邊和已訪問點Cout<<j; /輸出節(jié)點visitedj=true; /設(shè)置j為已訪問DFSing(v,visited) /遞歸遍歷C. deletevisited;算法【3】：BFS(int v)算法功能：無向圖的廣度優(yōu)先遍歷算法基本思想：1. 從圖中任一頂點V出發(fā)，標(biāo)記V已訪問；2. 依次訪問所有未被訪問的鄰

6、接頂點V1,V2,V3并標(biāo)記3. 分別從V1,V2,V3出發(fā)并依次訪問它們未被訪問的鄰接頂點反復(fù)1,2,3直到所有和V相通的頂點都被訪問到算法復(fù)雜度分析：結(jié)合遍歷一行及遞歸，時間復(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()算法功能：從頂點角度選出最小生成樹算法基本思想：N個頂點分屬兩集合U和U-V，U包含已落樹的頂點，U-V包含未落到樹上的頂點。然后不斷尋找U和U-V中各頂點間的最小權(quán)值邊，直到所有頂點落到集合U中。算法復(fù)雜度分析：此算法需要兩次循環(huán)遍歷所有結(jié)點，時間復(fù)雜度為O(N*N)代碼邏輯：A. Bool *U=new boolvNum(=true);Uv=false; /建立并初始化U集合和U-V集合的數(shù)組，這里用一個bool數(shù)組U表示，Ui為true表明頂點i為U

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

9、unt!=N)count+;算法【5】：Kruskal()算法功能：從邊的角度選出最小生成樹算法基本思想：首先對邊從小到大排序，然后依次挑取最小權(quán)值的邊到生成樹中，此過程里每添加一條新邊需要判斷是否會構(gòu)成回路，一旦構(gòu)成回路則放棄此邊。算法復(fù)雜度分析：此算法主要來自于邊的排序，時間復(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) /建立頂點集合數(shù)組vset并用for循環(huán)初始化為自然數(shù)列0,1,2,3N-1；E. for(i=0;i<eNum;i+)遍歷邊集數(shù)組edgelisti，If(vsetfromV=vsetendV) continue; /邊兩頂點同屬一數(shù)組時跳過Cout<<fromV和endVFor(j=0;j<vNum;j+) /遍歷vset集合更新信息 /將所有和頂點fromV具有相同集

11、合的點調(diào)整成endV的集合If(vsetj=vsetfromV) vsetj=vsetendVF. deleteedgelist;deletevset;算法【6】：FloydPath();算法功能：求出任意兩頂點間的最短路徑算法基本思想：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次，則時間復(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; /跳過自身到自身的回路if (distik+distkj < distij)distij = distik+dis

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

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

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

16、，更新最短路徑，更新末頂點minDis = diskminV;lastV = minV;/-/以上為得到單點出發(fā)到各頂點的最短路徑cout << "下面輸出v" << v << "與其他頂點的最短路徑：" << endl;int p, *stack, top(-1),count(1); /使用一個臨時棧將路徑倒序輸出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é)點入棧p = pathp; /跳轉(zhuǎn)到前驅(qū)結(jié)點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無窮大Max1061109567輸出域?qū)抯l5一維數(shù)組對應(yīng)矩陣關(guān)系Matrixij=arck,k=i*N+j;3. 程序運行結(jié)果測試流程：按順序執(zhí)行以下流程1- 構(gòu)建一個有向圖Dgraph對象，輸入一個無向圖（課本P208圖）；2- 打印鄰接矩陣；3- 輸出以各頂點為出發(fā)點的廣度遍歷；4- 輸出以各頂點為出發(fā)點的深度遍歷；5- 輸出以各頂點為出發(fā)點的Dijkstra算法最短路徑；6- 輸出FloydPath算法的各頂點間的最短路徑；7- (清屏)8- 構(gòu)建一個無向圖Ugraph對象，輸入一個有向圖（課本P207圖）；9- 打印鄰接矩陣；10- 輸出以各頂點為出發(fā)點的廣度遍歷；11- 輸出以各頂點為出發(fā)點的深度遍歷；12- 任取一頂點按Prim算法生成最小生成樹；13- 用Kruskal算法生成最小生成樹，并與12的比較是否一致；14- 程序運行完畢。運行結(jié)果(圖片太大，用鏈接存放)：有向圖