算法與數(shù)據(jù)結構課程設計報告

1、算法與數(shù)據(jù)結構課程設計報告題目：拓撲排序院 （系）： 計算機科學與工程學院 專 業(yè)： 計算機科學與技術 班 級： 學 生： 學 號： 302 指導教師： 2010年 12 月1. 問題描述 圖不同于線性結構，也不同于樹形結構，圖包含若干個頂點，且其中任何兩個頂點都可能存在鄰接關系，這種關系用邊或弧表示，圖在存儲結構主要有兩種：鄰接矩陣和鄰接表，進行拓撲排序的方法如下：1) 在圖中選一個沒有直接前驅(qū)（入度為0）的頂點, 并把該頂點輸出，令 n 為頂點個數(shù)；2) 從圖中刪去該頂點, 同時刪去所有它發(fā)出的有向邊；3) 重復以上(1)、(2)步, 直到全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成；

2、若圖中還有未輸出的頂點，但已跳出處理循環(huán)。這說明圖中還剩下一些頂點，它們都有直接前驅(qū)，再也找不到?jīng)]有前驅(qū)的頂點了，這時aov網(wǎng)絡中必定存在有向環(huán)。2. 算法設計一、拓撲排序設計思想 在拓撲排序的過程之中，輸入入度為零（即沒有前趨）的頂點，同時將該頂點的直接后繼的入度減1。（1）、查鄰接矩陣中入度為零的頂點，并進棧。（2）、當棧為空時，進行拓撲排序。（a）、退棧，輸出棧頂元素v。（b）、在鄰接矩陣中查找vj的直接后繼vk，將vk的入度減1，并令入度減至零的頂點進棧。（3）、若?？諘r輸出的頂點數(shù)不是n個則說明有向回路，否則拓撲排序結束。二、拓撲排序采用的數(shù)據(jù)結構設g=(v，e)是具有n個頂點的圖，

3、則g的鄰接矩陣是具有如下性質(zhì)的n階方陣： （1）對于n個頂點的無向圖，有a（i，i）=0，1in。（2）無向圖的鄰接矩陣是對稱的，即a（i，j）=a（j，i），1in，1jn。（3）有向圖的鄰接矩陣不一定對稱的。因此用鄰接矩陣來表示一個具有n個頂點的有向圖時需要n2個單位來存儲鄰接矩陣；對有n個頂點的無向圖則需存入上（下）三角形，故只需n（n+1）/2個單位。（4）無向圖的鄰接矩陣的第i行（或第i列）非零元素的個數(shù)正好是第i個頂點的度td（vi）。（5）有向圖的鄰接矩陣的第i行（或第i列）非零元素的個數(shù)正好是第i個頂點的出度od（vi）。3. 算法實現(xiàn)一、開發(fā)環(huán)境操作系統(tǒng)編譯環(huán)境生成文件win

4、dows xpmyeclipse 7.0node.javatopologysort.javatesttopology.javawindows vistamicrosoft visiotopologysort.vsd二、拓撲排序算法流程圖三、源程序清單1. node.javapackage com.xatu.topologysort;/* * * author * */public class node public string label;public boolean wasvisited;public node(string label) this.label = label;this.w

5、asvisited = false;public string getlabel() return label;public void setlabel(string label) this.label = label;public boolean iswasvisited() return wasvisited;public void setwasvisited(boolean wasvisited) this.wasvisited = wasvisited;2. topologysort.javapackage com.xatu.topologysort;import java.util.

6、scanner;/* * 用鄰接矩陣實現(xiàn)拓撲排序算法 * * author * */public class topologysort private int nodenum = 0;private node nodelist; / 圖中的所有頂點private int adjmat; / 鄰接矩陣private int indegree;/ 每個頂點入度的數(shù)組private int outdegree;/ 每個頂點出度的數(shù)組private int nverts; / 實際頂點數(shù)private string sortedarray; / 拓撲排序用public int getnodenum()

7、 return nodenum;public void setnodenum(int nodenum) this.nodenum = nodenum;public node getnodelist() return nodelist;public void setnodelist(node nodelist) nodelist = nodelist;public int getadjmat() return adjmat;public void setadjmat(int adjmat) this.adjmat = adjmat;public int getindegree() return

8、indegree;public void setindegree(int indegree) this.indegree = indegree;public int getoutdegree() return outdegree;public void setoutdegree(int outdegree) this.outdegree = outdegree;public int getnverts() return nverts;public void setnverts(int verts) nverts = verts;public string getsortedarray() re

9、turn sortedarray;public void setsortedarray(string sortedarray) this.sortedarray = sortedarray;public topologysort() scanner scan = new scanner(system.in);system.out.println(請輸入頂點的個數(shù)：);nodenum = scan.nextint();nodelist = new nodenodenum;adjmat = new intnodenumnodenum;sortedarray = new stringnodenum;

10、indegree = new intnodenum;outdegree = new intnodenum;nverts = 0;/ 當前頂點個數(shù)/ 初始化鄰接矩陣for (int i = 0; i nodenum; i+)for (int j = 0; j nodenum; j+) adjmatij = 0;/* * 添加頂點 * * param label */public void addnode(string label) nodelistnverts+ = new node(label);/* * 添加邊 * * param start * param end */public voi

11、d addedge(int start, int end) adjmatstart - 1end - 1 = 1;/* * 查看頂點v的鄰接點是否已經(jīng)全部訪問 * * param v * return */public int getadjunvisitedvertex(int v) for (int i = 1; i 0) int v = nosuccessors();if (v = -1) system.out.println(nn該有向圖有回路！);return;sortedarraynverts - 1 = nodelistv.label;deletevertex(v); / 刪除沒有

12、后繼的節(jié)點/ 輸出結果system.out.println(nn拓撲排序有序序列為：);for (int i = 0; i temp; i+) system.out.print(t + sortedarrayi);/* * 計算每個頂點的入度 */public void calculateindegree() int sumindegree = new intnodenum;for (int i = 0; i nodenum; i+) for (int j = 0; j nodenum; j+) if (adjmatji = 1) sumindegreei+; else continue;th

13、is.setindegree(sumindegree);/* * * 計算每個頂點的出度 */public void calcalateoutdegree() int sumoutdegree = new intnodenum;for (int i = 0; i nodenum; i+) for (int j = 0; j nodenum; j+) if (adjmatij = 1) sumoutdegreei+; else continue;this.setoutdegree(sumoutdegree);/* * 返回一個沒有后繼的頂點 * * return */public int nos

14、uccessors() for (int row = 0; row nverts; row+) boolean hassuccessor = false;for (int col = 0; col 0) hassuccessor = true;break;if (!hassuccessor) return row;return -1;/* * 刪除沒有后繼的頂點,并修改鄰接矩陣 * * param v */public void deletevertex(int v) if (v != nverts - 1) / 不是最后一個頂點才做如下操作for (int i = v; i nverts -

15、 1; i+) / 從數(shù)組中刪除已經(jīng)拓撲排好序的節(jié)點nodelisti = nodelisti + 1;for (int i = v; i nverts - 1; i+) / 修改鄰接矩陣行moverowup(i, nverts);for (int i = v; i nverts - 1; i+) / 修改鄰接矩陣列movecolleft(i, nverts - 1);nverts-;/* * 把刪除頂點以下的所有元素上移一行 * * param row * param n */public void moverowup(int row, int n) for (int col = 0; co

16、l n; col+) adjmatrowcol = adjmatrow + 1col;/* * 把刪除頂點右邊的所有元素左移一列 * * param col * param n */public void movecolleft(int col, int n) for (int row = 0; row n; row+) adjmatrowcol = adjmatrowcol + 1;/* * 輸出鄰接矩陣 */public void print() this.calculateindegree();this.calcalateoutdegree();system.out.println(圖的

17、鄰接矩陣為:);system.out.print( );for (int i = 0; i nverts; i+) system.out.print( + nodelisti.label);system.out.println();for (int i = 0; i nverts; i+) system.out.print(nodelisti.label + | );for (int j = 0; j nverts; j+) system.out.print(adjmatij + );system.out.println();system.out.println(n每個頂點的入度為：);for

18、 (int i = 0; i nodenum; i+) system.out.print(tv + (i + 1);system.out.println();for (int i = 0; i nodenum; i+) system.out.print(t + this.getindegree()i);system.out.println(nn每個頂點的出度為：);for (int i = 0; i nodenum; i+) system.out.print(tv + (i + 1);system.out.println();for (int i = 0; i nodenum; i+) sys

19、tem.out.print(t + this.getoutdegree()i);3.testtopology.javapackage com.xatu.topologysort;public class testtopology public static void main(string args) topologysort ts = new topologysort();for(int i=0;its.getnodenum();i+)ts.addnode(v+(i+1);/ts.addnode(1);/ts.addnode(2);/ts.addnode(3);/ts.addnode(4);/ts.addnode(5);/ts.addnode(6);ts.addedge(1, 2);/ts.addedge(2, 1); /設置一個環(huán)的實驗/ts.addedge(6, 6); /設置一個自身環(huán)的實驗ts.addedge(1, 3);ts.addedge(1, 4);ts.addedge(3, 2);ts.addedge(3, 5);ts.a