算法与数据结构课程设计报告

1、算法与数据结构课程设计报告题目：拓扑排序院 （系）： 计算机科学与工程学院 专 业： 计算机科学与技术 班 级： 学 生： 学 号： 302 指导教师： 2010年 12 月1. 问题描述 图不同于线性结构，也不同于树形结构，图包含若干个顶点，且其中任何两个顶点都可能存在邻接关系，这种关系用边或弧表示，图在存储结构主要有两种：邻接矩阵和邻接表，进行拓扑排序的方法如下：1) 在图中选一个没有直接前驱（入度为0）的顶点, 并把该顶点输出，令 n 为顶点个数；2) 从图中删去该顶点, 同时删去所有它发出的有向边；3) 重复以上(1)、(2)步, 直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；

2、若图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了，这时aov网络中必定存在有向环。2. 算法设计一、拓扑排序设计思想 在拓扑排序的过程之中，输入入度为零（即没有前趋）的顶点，同时将该顶点的直接后继的入度减1。（1）、查邻接矩阵中入度为零的顶点，并进栈。（2）、当栈为空时，进行拓扑排序。（a）、退栈，输出栈顶元素v。（b）、在邻接矩阵中查找vj的直接后继vk，将vk的入度减1，并令入度减至零的顶点进栈。（3）、若栈空时输出的顶点数不是n个则说明有向回路，否则拓扑排序结束。二、拓扑排序采用的数据结构设g=(v，e)是具有n个顶点的图，

3、则g的邻接矩阵是具有如下性质的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列）非零元素的个数正好是第i个顶点的度td（vi）。（5）有向图的邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的出度od（vi）。3. 算法实现一、开发环境操作系统编译环境生成文件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;/* * 用邻接矩阵实现拓扑排序算法 * * author * */public class topologysort private int nodenum = 0;private node nodelist; / 图中的所有顶点private int adjmat; / 邻接矩阵private int indegree;/ 每个顶点入度的数组private int outdegree;/ 每个顶点出度的数组private int nverts; / 实际顶点数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(请输入顶点的个数：);nodenum = scan.nextint();nodelist = new nodenodenum;adjmat = new intnodenumnodenum;sortedarray = new stringnodenum;

10、indegree = new intnodenum;outdegree = new intnodenum;nverts = 0;/ 当前顶点个数/ 初始化邻接矩阵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的邻接点是否已经全部访问 * * 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、后继的节点/ 输出结果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+) / 从数组中删除已经拓扑排好序的节点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); /设置一个环的实验/ts.addedge(6, 6); /设置一个自身环的实验ts.addedge(1, 3);ts.addedge(1, 4);ts.addedge(3, 2);ts.addedge(3, 5);ts.a