数据结构课程设计 拓扑排序

算法与数据结构

课程设计报告

题目：拓扑排序

院 （系）：  计算机科学与工程学院  

专    业：  计算机科学与技术      

班    级：       080602          

学    生：        马珂           

学    号：       080602128        

指导教师：          赵莉          

                               2010-12-30

一 .问题描述

：简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。离散数学中关于偏序和全序的定义：

　　若集合X上的关系是R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。

设R是集合X上的偏序（Partial Order）,如果对每个x,y属于X必有xRy 或 yRx，则称R是集合X上的全序关系。

　　注意：

　　①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。

　　②若图中存在有向环，则不可能使顶点满足拓扑次序。

③一个DAG的拓扑序列通常表示某种方案切实可行。

　无前趋的顶点优先的拓扑排序算法在具体存储结构下，为便于考察每个顶点的入度，可保存各顶点当前的入度。为避免每次选入度为0的顶点时扫描整个存储空间，可设一个栈或队列暂存所有入度为零的顶点：

　　拓扑排序是有向图的一个重要操作。在给定的有向图G中，若顶点序列vi1,vi2,...,vin满足下列条件：若在有向图G中从顶点vi到顶点vj有一条路径，则在序列中顶点vi必在顶点vj之前，便称这个序列为一个拓扑序列。

求一个有向图拓扑序列的过程称为拓扑排序。

二．算法设计

我主要用的是java语言，所以其中用到了类以及类方法类成员等，还有抛出异常。在非运行时会出现的一场称为io exception。

在程序的一开始先定义一些变量，然后在方法里边有java中常用的System.out.println输入输出语句，只需要在程序的开始用java.util包导入就可以直接使用。

拓扑排序的主要思想是实现的基本方法

　　拓扑排序方法如下:

　　(1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.

　　(2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.

　　(3)重复上述两步,直到剩余的网中不再存在没有前驱的顶点为止.

程序的大概步骤如下

三 代码

import java.io.*;

public class cunchu {

    static int b[],c[],a[][];

    static int n,j,k,l,m,i=0,p=0,u=0,g=0;

    static    char f;

public void shuRu() throws IOException{

                //输入图的结构以邻接矩阵的形式保存

                System.out.println("请输入结点的个数:");

                java.util.Scanner s = new java.util.Scanner(System.in);

                n=s.nextInt();

                int a[][]=new int[n][n];

                int b[]=new int[n];

                int c[]=new int[n];

            do{   

                System.out.print("请输入节点:  ");

                l=s.nextInt();

                System.out.print("请输入与此节点有关的节点:  ");

                m=s.nextInt();

                a[l][m]=1;

                System.out.print("是否要输入节点（y/n)?  ");

                f=(char)System.in.read();

             } while(f=='y');

            System.out.println(" "+"对应的邻接矩阵为：");

for(j=0;j               {

             for(k=0;k                     System.out.print("  "+a[j][k]);

                           System.out.println();

               }

for(j=0;j               {

             for(k=0;k                       if(a[j][k]==1)

                           b[k]+=1;

               }

            System.out.println("各结点的入度为:");

for(j=0;j                   System.out.println("b"+"["+j+"]"+"="+b[j]);

for(k=0;k<12;k++)

            {

             for(j=0;j                {            

                    if(b[j]==0)

                    {    c[u]=j;

                          u++;

                          b[j]=100;

              for(k=0;k                              if(a[j][k]==1)

                                b[k]-=1;

                    }

                }

            }

if(u                  System.out.println("错误，该有向图有回路");

            else

                {

                   System.out.println("拓扑排序的结果为：");

for(j=0;j                   System.out.print(d[c[j]]+"   ");

                 }

     }

public static void main(String[]args)throws IOException{

         cunchu a=new  cunchu ();

         a.shuru();

      }

    }     

程序的运行结果：

请输入结点的个数:

6

请输入节点:  0

请输入与此节点有关的节点:  1

是否要输入节点（y/n)?  y

请输入节点:  0

请输入与此节点有关的节点:  2

是否要输入节点（y/n)?  y

请输入节点:  0

请输入与此节点有关的节点:  3

是否要输入节点（y/n)?  y

请输入节点:  2

请输入与此节点有关的节点:  1

是否要输入节点（y/n)?  y

请输入节点:  2

请输入与此节点有关的节点:  4

是否要输入节点（y/n)?  y

请输入节点:  3

请输入与此节点有关的节点:  4

是否要输入节点（y/n)?  y

请输入节点:  5

请输入与此节点有关的节点:  3

是否要输入节点（y/n)?  y

请输入节点:  5

请输入与此节点有关的节点:  4

是否要输入节点（y/n)?  y

请输入节点:  3

请输入与此节点有关的节点:  4

是否要输入节点（y/n)?  y

请输入节点:  5

请输入与此节点有关的节点:  3

是否要输入节点（y/n)?  y

请输入节点:  5

请输入与此节点有关的节点:  4

是否要输入节点（y/n)?  n

 对应的邻接矩阵为：

  0  1  1  1  0  0

  0  0  0  0  0  0

  0  1  0  0  1  0

  0  0  0  0  1  0

  0  0  0  0  0  0

  0  0  0  1  1  0

各结点的入度为:

b[0]=0

b[1]=2

b[2]=1

b[3]=2

b[4]=3

b[5]=0

拓扑排序的结果为：

v1   v3   v6   v2   v4   v5   

     假设有六个节点则流程图如下

四．心得体会

五．参考资料

严蔚敏  吴伟民 《数据结构（c语言版）》

赵莉  杨国梁《java程序设计教程》