有向无环图下的拓扑排序

几个基本概念

1.有向图：顾名思义，从一个点到另一个点，并非向无向图那样默认双向可达（只要两点之间存在边就相互可达），有向图是严格按照方向单向可达。

2.有向图的环:对于一个有向图，如果从A出发，存在一条通路可使其又回到A，那么我们说该有向图存在环。

3.有向无环图：一个不存在环的有向图。

4.自反和反自反：设R是集合A上的二元关系,对于A中的每一个元素x，都有（x，x）满足关系R，则称关系R具有自反性。因此对于反自反，就是A中的每一个元素x,都有(x，x)不满足关系R，则称关系R具有反自反性。

5.对称和反对称：设R是集合A上的二元关系,对于A中任意两个元素x，y，如果（x,y）满足关系R，则（y,x）也满足关系R，则称此关系具有对称性。反之，集合A里面不存在一对元素他们相互满足关系R，则称R具有反对称性。

5.传递和反传递：设R是集合A上的二元关系，对于A中的任意三个元素x，y，z,有 xRy, yRz,则有xRz。反之，对于对于A中的任意三个元素x，y，z,有 xRy, yRz，那么a和c没有关系R，则称为反传递性。

6.偏序：集合A上的关系R是自反的，反对称的和传递的，则称R是集合A上的偏序关系。

7.全序：是R是集合A上的偏序，如果对每个x，y∈A必有xRy或yRx，则称R是集合A上的全序关系。（就是任意两个元素都满足关系R）

8.拓扑排序：由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

如何进行拓扑排序？

（1）在有向图中选择一个入度为零（就是没有路径到达改点，如下图的v1,v6…）的顶点且输出之。
（2）从图中删除该顶点和所有以它为起始点的边。
（3）重复上诉两步，直到图中不存在无前驱的顶点为止。

代码实现

import java.util.Scanner;
import java.util.Stack;
/*
由于要统计每个结点的入读,所以我们我"邻接表"来存储图
测试输入:
6
8
0 1 1
0 2 1
0 3 1
2 1 1
2 4 1
3 4 1
5 3 1
5 4 1
输出：
5 0 2 1 3 4 
*/
public class Main{
   public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int nodeTotalNums = sc.nextInt();  //图的结点的个数
        int edgeTotalNums = sc.nextInt();  //图的边的条数
         
        //创建领接数组,这里我们规定顶点的最小编号为0
        ArcNode[] nodeInformation = new ArcNode[nodeTotalNums];
        for(int i=0;i<nodeTotalNums;i++){ //领接数组初始化
             nodeInformation[i] = new ArcNode(i,null);
        }
        
        //录入数据,这里我们规定顶点的最小编号为0
        for(int i=0;i<edgeTotalNums;i++){
            int startNode = sc.nextInt();
            int endNode = sc.nextInt();
            int weight = sc.nextInt();
            Edge e;
            if(nodeInformation[startNode].firstEdge == null){
                 e = new Edge(endNode,weight,null);
            } else {
                 e = new Edge(endNode,weight,nodeInformation[startNode].firstEdge);
            }
            nodeInformation[startNode] = new ArcNode(startNode,e);
        }

        sc.close();
        TopologicalSorting(nodeTotalNums,nodeInformation);
  }
  
   //拓扑排序，为了达到最佳时间复杂度 O(n+e)，将引入栈的使用
   public static void TopologicalSorting(int nodeTotalNums,ArcNode[] nodeInformation){
         //设置一个入度数组inDegree,记录各个顶点的入度
         int[] inDegree = new int[nodeTotalNums];
         for(int i=0;i<nodeTotalNums;i++){
                if(nodeInformation[i].firstEdge != null){
                      Edge tempE = nodeInformation[i].firstEdge;
                      while(tempE != null){
                          inDegree[tempE.endNode]++;
                          tempE = tempE.nextEdge;
                      }
                 }
          }
           
          Stack<Integer> s = new Stack<>();
          for(int i=0;i<nodeTotalNums;i++){
              if(inDegree[i] == 0){
                  s.push(i);    //将入度为0的点入栈
              }
          }
                    
          while(!s.isEmpty()){
               int tempN = s.pop();
               System.out.print(tempN+" ");
  
              if(nodeInformation[tempN].firstEdge != null){
                  for(Edge p=nodeInformation[tempN].firstEdge; p!=null; p=p.nextEdge){
                        inDegree[p.endNode]--;
                        if(inDegree[p.endNode] == 0){
                             s.push(p.endNode);
                        }
                  }
              }
          }
      
    }
   
}

//顶点类
class ArcNode{
    int date;
    Edge firstEdge;   //该顶点指向的第一条边(采用前插结点发)
    //无参构造方法
    public ArcNode(){}  
    //全参构造方法
    public ArcNode(int date,Edge firstEdge){
        this.date = date;
        this.firstEdge = firstEdge;
    }
}

//边类
class Edge{
   int endNode;      //边的终点
   int weight;       //边的权值
   Edge nextEdge;    //下一条边
   //无参构造方法
   public Edge(){}
   //全参构造方法
   public Edge(int endNode,int weight,Edge nextEdge){
        this.endNode = endNode;
        this.weight = weight;
        this.nextEdge = nextEdge;
   }
}

该图的邻接表

算法分析

对有n个顶点的和e条边的有向图而言,建立各项点的入度的时间复杂度为O(e),建立零入度顶点栈的时间复杂度为O(n).在拓扑排序过程中,若有向图无环,则每个顶点进一次栈，出一次栈，入度减一的操作在while语句中共执行e次，所以总的时间复杂度为O(n+e).