当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

拓扑排序入门练习

发表于: 2012-11-01   作者:128kj   来源:转载   浏览:
摘要:    拓扑排序简单来说就是把一个图的所有节点排序,使得每一条有向边(u,v)对应的u都排在v的前面。 拓扑排序最大的用途就是判断一个有向图是否有环。 无前趋的顶点优先的拓扑排序方法     该方法的每一步总是输出当前无前趋(即人度为零)的顶点,其抽象算法可描述为:     NonPreFirstTopSo
   拓扑排序简单来说就是把一个图的所有节点排序,使得每一条有向边(u,v)对应的u都排在v的前面。 拓扑排序最大的用途就是判断一个有向图是否有环。

无前趋的顶点优先的拓扑排序方法

    该方法的每一步总是输出当前无前趋(即人度为零)的顶点,其抽象算法可描述为:
    NonPreFirstTopSort(G){//优先输出无前趋的顶点
      while(图G中有人度为0的顶点)do{
       从G中选择一个人度为0的顶点v且输出之;
       从G中删去v及其所有出边;
       }
      if(输出的顶点数目<|V(G)|)
        //若此条件不成立,则表示所有顶点均已输出,排序成功。
        Error("G中存在有向环,排序失败!");
     }

性质
1、 拓扑排序在有向无环图中才能排出有效的序列,否则能判断该有向图有环。
2、如果输入的有向图中的点,不存在入度为0的点,则该有向图存在回路
3、如果存在的入度为0的点大于一个,则该有向图肯定不存在一个可以确定的拓扑序列但并不妨碍拓扑排序

例: 有N个比赛队(1<=N<=500),编号依次为1,2,3,。。。。,N进行比赛,比赛结束后,裁判委员会要将所有参赛队伍从前往后依次排名,但现在裁判委员会不能直接获得每个队的比赛成绩,只知道每场比赛的结果,即P1赢P2,用P1,P2表示,排名时P1在P2之前。现在请你编程序确定排名。


Input
输入有若干组,每组中的第一行为二个数N(1<=N<=500),M;其中N表示队伍的个数,M表示接着有M行的输入数据。
接下来的M行数据中,每行也有两个整数P1,P2表示即P1队赢了P2队。


Output
给出一个符合要求的排名。输出时队伍号之间有空格,最后一名后面没有空格。

其他说明:符合条件的排名可能不是唯一的,此时要求输出时编号小的队伍在前;
输入数据保证是正确的,即输入数据确保一定能有一个符合要求的排名。


Sample Input
4 3
1 2
2 3
4 3

Sample Output
1 2 4 3

典型的拓扑排序算法
import java.util.*;

方法一:(邻接矩阵实现图存储)
public class Main {

	private  int n, m;
	private int[] indegree;// 顶点的入度
	private int[] result;// 保存最后排好序的结果
	private int[][] G;// 邻接矩阵存储
	private  Queue<Integer> que;//存入入度为0的顶点

        public Main(int n,int m,int[] indegree,int[][] G){
             this.n=n;
             this.m=m;
             this.indegree=indegree;
             this.G=G;
        }
             
       

	public static void main(String[] args) {
	  Scanner sc = new Scanner(System.in);
           int[][] G;
           int[] indegree;
           int n,m;
	    while (sc.hasNext()) {
	      n = sc.nextInt();
	      m = sc.nextInt();
	      G = new int[n + 1][n + 1];
	      indegree = new int[n + 1];

                 while (m-- > 0) {
		   int u = sc.nextInt();
		   int v = sc.nextInt();
              if (G[u][v] == 0) {// 这个条件一定要,避免重边的情况比如a b可能出现两次的情况
		     indegree[v]++;
		     G[u][v] = 1;
		    }
		 }
                 Main ma=new Main(n,m,indegree,G);
			ma.topsort();
			
		}
	}

	private  void topsort() {
          result = new int[n + 1];
          que = new PriorityQueue<Integer>();//同名次时,序号小的排前,所以用优先队列
	  int index = 0;
	  for (int i = 1; i <= n; i++) {//找出图中所有入度为O的顶点
	    if (indegree[i] == 0)
		que.add(i);//编号小的在前
	  }
	  while (!que.isEmpty()) {
	     int u = que.poll();
	     result[++index] = u;
             for (int i = 1; i <= n; i++) {
                if (G[u][i] == 1) {
		  indegree[i]--;//模拟删除顶点,i的入度减1
		  if (indegree[i] == 0)
		    que.add(i);
		}
	     }
	  }
          // 输出
	   System.out.print(result[1]);
	   for (int i = 2; i <= n; i++) {
		System.out.print(" "+result[i]);
	   }
	   System.out.println();
	}

  }

import java.util.*;

方法二:拓扑排序(使用邻接表实现)
public class Main{
	private int n, m;
	private int[] indegree;// 顶点的入度
	private int[] result;// 保存最后排好序的结果
	private List<ArrayList<Integer>> G;// 邻接表。
	private Queue<Integer> que;

        public Main(int n,int m,int[] indegree,List<ArrayList<Integer>> G){
             this.n=n;
             this.m=m;
             this.indegree=indegree;
             this.G=G;
        }

	public static void main(String[] args) {
          int n,m;
          int[] indegree;
          List<ArrayList<Integer>> G;
          Scanner sc = new Scanner(System.in);
	  while (sc.hasNext()) {
	    n = sc.nextInt();
	    m = sc.nextInt();
	    G = new ArrayList<ArrayList<Integer>>();
	    for(int i = 1;i<=n+1;i++)
               G.add(new ArrayList<Integer>());//初始化邻接表
	    indegree = new int[n + 1];
            while (m-- > 0) {
              int u = sc.nextInt();
              int v = sc.nextInt();
        if (!G.get(u).contains(v)) {// 这个条件一定要,避免重边的情况比如a b可能出现两次的情况
                 indegree[v]++;
                 G.get(u).add(v);
               }
	    }
             Main ma=new Main(n,m,indegree,G);
             ma.topsort();
           }
        }
			
	

	private  void topsort() {
          result = new int[n + 1];
          que = new PriorityQueue<Integer>();
	  int index = 0;
	  for (int i = 1; i <= n; i++) {
	     if (indegree[i] == 0)
		que.add(i);
	   }
           while (!que.isEmpty()) {
	     int v = que.poll();
	     result[++index] = v;
	     for (int i : G.get(v)) {
                 indegree[i]--;
                 if (indegree[i] == 0)
                   que.add(i);
             }
           }
          // 输出
         System.out.print(result[1]);
         for (int i = 2; i <= n; i++) {
            System.out.print(" " + result[i]);
         }
         System.out.println();
       }
 }



拓扑排序入门练习

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
拓扑排序 1.概述: 拓扑排序就是将一个“有向无环图G“(左图所示,右图为有环的有向图)中的所有顶
(好文章就是要分享!原文:http://www.cnblogs.com/shanyou/archive/2006/11/16/562861.html) 拓
问题及描述: /* * Copyright (c) 2015, 烟台大学计算机与控制工程学院 * All rights reserved. *
代码部分: main.cpp: #include <stdio.h> #include <malloc.h> #include "graph.h" vo
拓扑排序是对有向无环图的一种排序。表示了顶点按边的方向出现的先后顺序。如果有环,则无法表示两
在图中用顶点表示活动,用弧表示活动间的优先关系,这样的有向图成为AOV网。 下面是AOV网的拓扑排序
在介绍拓扑排序前我们需要了解什么是偏序和全序。 1、偏序——若集合X上的关系R是自反的、反对称的
一、概述   对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排
如上图,为一有向图,想在要对其进行拓扑排序,算法可以参考: http://zh.wikipedia.org/wiki/%E6%8
拓扑排序: 拓扑排序是根据离散数学中有关偏序与全序定义的。 若一个集合 X 上的关系 R 是自反的 反
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号