《算法与数据结构课程设计报告.doc》由会员分享，可在线阅读，更多相关《算法与数据结构课程设计报告.doc（15页珍藏版）》请在三一办公上搜索。
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);
20、/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.addEdge(4, 5);ts.addEdge(6, 4);ts.addEdge(6, 5);ts.addEdge(7, 1);ts.print();ts.topology();四、程序运行结果4. 心得体会本次课程设计主要是通过Java实现拓扑
21、排序算法，一开始以为实现这个算法的基本功能就算大功告成了，结果让老师一检查问题就出来了两个主要问题。第一，我原来的程序直接定义一个长度为2020的邻接矩阵，以后添加的顶点不能超过20个，这对程序可扩展行存在很大的问题，老师建议我们要根据我们自己输入的顶点个数动态分配邻接矩阵的存储空间，这样就考虑到了算法空间复杂度，先声明邻接矩阵和数组的引用(其实这就是C语言的指针)，通过根据用户输入的顶点个数再分配存储空间，这样可以减省很多内存空间，如此就把这个问题解决了。第二，我的程序还没有实现每个顶点的入度和出度，我一直认为这是个很复杂的问题，但是在看老师给别人检查程序的时候，领会到了解决这个问题办法，计算顶点的入度就是计算每列元素1的个数，出度就是每行元素1的个数，最后添加了calculateIndegree()和calcalateOutdegree()两个方法把这个问题解决了。通过本次课程设计让我认识到了理论知识学的好，并不代表我们的实践能力就好，编程过程中发现有时遇到一点小问题，你没有一个整体的思路，很难轻易把这个问题解决。5. 参考文献1数据结构（C语言版） 严蔚敏 清华大学出版社.2Java程序设计教程 赵莉，杨国梁等 西安电子科技大学出版社.
