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

《算法与数据结构课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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个则说明有向回路，否则拓扑排序结束。二、拓扑排序采用的数据

3、结构设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：     （1）对于n个顶点的无向图，有A（i，i）=0，1≤i≤n。（2）无向图的邻接矩阵是对称的，即A（i，j）=A（j，i），1≤i≤n，1≤j≤n。（3）有向图的邻接矩阵不一定对称的。因此用邻接矩阵来表示一个具有n个顶点的有向图时需要n2个单位来存储邻接矩阵；对有n个顶点的无向图则需存入上（下）三角形，故只需n（n+1）/2个单位。（4）无向图的邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度TD（vi）。（5）有向图的邻接矩阵的第i行（或第i列

4、）非零元素的个数正好是第i个顶点的出度OD（vi）。3.算法实现一、开发环境操作系统编译环境生成文件WindowsXPMyEclipse7.0Node.javaTopologySort.javaTestTopology.javaWindowsVistaMicrosoftVisioTopologySort.vsd二、拓扑排序算法流程图三、源程序清单1.Node.javapackagecom.xatu.topologySort;/****@author**/publicclassNode{publicStringlabel;publicboolean

5、wasvisited;publicNode(Stringlabel){this.label=label;this.wasvisited=false;}publicStringgetLabel(){returnlabel;}publicvoidsetLabel(Stringlabel){this.label=label;}publicbooleanisWasvisited(){returnwasvisited;}publicvoidsetWasvisited(booleanwasvisited){this.wasvisited=wasvisited

6、;}}2.TopologySort.javapackagecom.xatu.topologySort;importjava.util.Scanner;/***用邻接矩阵实现拓扑排序算法**@author**/publicclassTopologySort{privateintnodeNum=0;privateNode[]NodeList;//图中的所有顶点privateint[][]adjmat;//邻接矩阵privateint[]indegree;//每个顶点入度的数组privateint[]outdegree;//每个顶点出度的数组priva

7、teintnVerts;//实际顶点数privateStringsortedArray[];//拓扑排序用publicintgetNodeNum(){returnnodeNum;}publicvoidsetNodeNum(intnodeNum){this.nodeNum=nodeNum;}publicNode[]getNodeList(){returnNodeList;}publicvoidsetNodeList(Node[]nodeList){NodeList=nodeList;}publicint[][]getAdjmat(){returna

8、djmat;}publicvoidsetAdjmat(int[][]adjmat){this.adjmat=adjmat;}public