数据结构课程设计 拓扑排序Word文档下载推荐.docx
- 文档编号:3641745
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:9
- 大小:61.31KB
数据结构课程设计 拓扑排序Word文档下载推荐.docx
《数据结构课程设计 拓扑排序Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计 拓扑排序Word文档下载推荐.docx(9页珍藏版)》请在冰点文库上搜索。
080602128
指导教师:
赵莉
2010-12-30
一.问题描述
:
简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。
离散数学中关于偏序和全序的定义:
若集合X上的关系是R是自反的、反对称的和传递的,则称R是集合X上的偏序关系。
设R是集合X上的偏序(PartialOrder),如果对每个x,y属于X必有xRy或yRx,则称R是集合X上的全序关系。
注意:
①若将图中顶点按拓扑次序排成一行,则图中所有的有向边均是从左指向右的。
②若图中存在有向环,则不可能使顶点满足拓扑次序。
③一个DAG的拓扑序列通常表示某种方案切实可行。
无前趋的顶点优先的拓扑排序算法在具体存储结构下,为便于考察每个顶点的入度,可保存各顶点当前的入度。
为避免每次选入度为0的顶点时扫描整个存储空间,可设一个栈或队列暂存所有入度为零的顶点:
拓扑排序是有向图的一个重要操作。
在给定的有向图G中,若顶点序列vi1,vi2,...,vin满足下列条件:
若在有向图G中从顶点vi到顶点vj有一条路径,则在序列中顶点vi必在顶点vj之前,便称这个序列为一个拓扑序列。
求一个有向图拓扑序列的过程称为拓扑排序。
二.算法设计
我主要用的是java语言,所以其中用到了类以及类方法类成员等,还有抛出异常。
在非运行时会出现的一场称为ioexception。
在程序的一开始先定义一些变量,然后在方法里边有java中常用的System.out.println输入输出语句,只需要在程序的开始用java.util包导入就可以直接使用。
拓扑排序的主要思想是实现的基本方法
拓扑排序方法如下:
(1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.
(2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.
(3)重复上述两步,直到剩余的网中不再存在没有前驱的顶点为止.
程序的大概步骤如下
三代码
importjava.io.*;
publicclasscunchu{
staticintb[],c[],a[][];
staticintn,j,k,l,m,i=0,p=0,u=0,g=0;
staticcharf;
publicvoidshuRu()throwsIOException{
//输入图的结构以邻接矩阵的形式保存
System.out.println("
请输入结点的个数:
"
);
java.util.Scanners=newjava.util.Scanner(System.in);
n=s.nextInt();
inta[][]=newint[n][n];
intb[]=newint[n];
intc[]=newint[n];
do{
System.out.print("
请输入节点:
"
l=s.nextInt();
请输入与此节点有关的节点:
m=s.nextInt();
a[l][m]=1;
是否要输入节点(y/n)?
f=(char)System.in.read();
}while(f=='
y'
+"
对应的邻接矩阵为:
for(j=0;
j<
n;
j++)
{
for(k=0;
k<
k++)
System.out.print("
+a[j][k]);
System.out.println();
}
j++)//确定每个结点的入度
if(a[j][k]==1)
b[k]+=1;
各结点的入度为:
System.out.println("
b"
["
+j+"
]"
="
+b[j]);
for(k=0;
12;
for(j=0;
{
if(b[j]==0)
{c[u]=j;
u++;
b[j]=100;
for(k=0;
if(a[j][k]==1)
b[k]-=1;
}
if(u<
n-1)
错误,该有向图有回路"
else
拓扑排序的结果为:
System.out.print(d[c[j]]+"
publicstaticvoidmain(String[]args)throwsIOException{
cunchua=newcunchu();
a.shuru();
}
程序的运行结果:
6
0
1
y
2
3
4
5
n
对应的邻接矩阵为:
011100
000000
010010
000010
000110
b[0]=0
b[1]=2
b[2]=1
b[3]=2
b[4]=3
b[5]=0
v1v3v6v2v4v5
假设有六个节点则流程图如下
四.心得体会
五.参考资料
严蔚敏吴伟民《数据结构(c语言版)》
赵莉杨国梁《java程序设计教程》
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构课程设计 拓扑排序 数据结构 课程设计 拓扑 排序