求图的拓扑排序

简介

拓扑排序 （Topological Sorting）

在计算机科学领域，有向图的拓扑排序或拓扑排序是其顶点的线性排序，使得对于从顶点u到顶点v的每个有向边uv，u在排序中都在v之前。例如，图形的顶点可以表示要执行的任务，并且边缘可以表示一个任务必须在另一个任务之前执行的约束；在这个应用中，拓扑排序只是一个有效的任务顺序。如果当图形没有定向循环，即如果它是有向无环图（Directed Acyclic Graph，即DAG），则拓扑排序是可能的。任何DAG具有至少一个拓扑排序，并且已知有些算法用于在线性时间内构建任何DAG的拓扑排序。
在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（Topological sorting）。

1. 每个顶点出现且只出现一次；
2. 若A在序列中排在B的前面，则在图中不存在从B到A的边。

也可以定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从顶点A到顶点B的路径，那么在排序中B出现在A的后面。

问题描述

一般可以用有向图表示一个工程。在这种有向图中，用顶点表示活动，用弧 <i, j> 表示活动 i 必须在活动 j 开始之前完成。这种有向图叫做用顶点表示活动的网络（Activity on Vertex），记作 AOV网络。

在AOV网络中不能存在有向回路，即有向环。因为如果出现了有向环，意味着某项活动要以自己的完成作为先决条件。显然这是不可能的。所以对给定的AOV网络，必须先判断它是否存在有向环。

一种方法是对AOV网络构造它的拓扑有序序列。即将所有的顶点能够成一个线性有序的序列，使得AOV网络所有的前驱和后继关系得到满足，这种构造AOV网络全部顶点的拓扑有序序列的运算就叫拓扑排序。

例如，下面有一个有向无环图，“5 4 2 3 1 0”是它的一个拓扑排序。一个有向无环图可以有多个拓扑排序，如下图的另一个拓扑排序为“4 5 2 3 1 0”，拓扑排序中的第一个顶点总是入度为0的顶点（即没有任何一条有向边以它为终点）。

算法思路

1. 在AOV网络中选一个没有直接前驱的顶点v，并输出
2. 从图中删除该顶点，同时删去所有从顶点v发出的弧
3. 重复步骤1,2. 直到没有直接前驱的顶点全部输出

算法步骤

用二维list链表存储图的领接表

1. 建立入度为0的顶点栈
2. 当入度为0的顶点栈为空时，转到步骤6，否则步骤3
3. 从入度为0的顶点栈顶元素v出栈，并输出顶点v
4. 从AOV网络删去顶点v和所有顶点v发出的弧 <v, j>， 并将顶点 j 的入度 -1
5. 如果顶点 j 的入度 = 0，则将该顶点置入入度为0的顶点栈，转到步骤2
6. 如果输出顶点个数 < AOV网络顶点数，则图中存在有向环

复杂度分析

Topological Sorting via Depth First Search(DFS)
在DFS中，我们先打印一个顶点，然后递归的对它的邻接点调用DFS。但是在拓扑排序中，任何一个顶点总要先于它的所有邻接顶点打印，如上面的图，顶点5和4必须先于顶点0打印。所以拓扑排序和DFS是不同的，例如“5 2 3 1 0 4”是上图的一个DFS序列，但是这个序列并不是拓扑排序。

在DFS中，我们从任意一个顶点出发，打印它然后对它的所有邻接顶点递归调用DFS。而在拓扑排序中，我们同样调用DFS过程，但是在递归调用DFS的过程中，我们不直接打印顶点，而是把顶点 push 到栈里，等到递归完成后，所有顶点就全都在栈里了。注意，在这个过程中当且仅当一个顶点的所有邻接顶点入栈后，才到当前顶点入栈，这就保证它们能满足拓扑排序的次序要求。所以最后栈里的内容，从栈顶到栈底，就是一个拓扑排序序列，我们不断出栈并打印它们即可。

因为这个算法只是简单的调用了下DFS，并借助栈做为辅助，所以其复杂度和DFS一样是O(V+E)。

代码实现

C++

#include<iostream>
#include <list>
#include <stack>
using namespace std;

// Class to represent a graph
class Graph
{
    int V;    // No. of vertices'

    // Pointer to an array containing adjacency listsList
    list<int> *adj;

    // A function used by topologicalSort
    void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
public:
    Graph(int V);   // Constructor

     // function to add an edge to graph
    void addEdge(int v, int w);

    // prints a Topological Sort of the complete graph
    void topologicalSort();
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}

// A recursive function used by topologicalSort
void Graph::topologicalSortUtil(int v, bool visited[], 
                                stack<int> &Stack)
{
    // Mark the current node as visited.
    visited[v] = true;

    // Recur for all the vertices adjacent to this vertex
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            topologicalSortUtil(*i, visited, Stack);

    // Push current vertex to stack which stores result
    Stack.push(v);
}

// The function to do Topological Sort. It uses recursive 
// topologicalSortUtil()
void Graph::topologicalSort()
{
    stack<int> Stack;

    // Mark all the vertices as not visited
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;

    // Call the recursive helper function to store Topological
    // Sort starting from all vertices one by one
    for (int i = 0; i < V; i++)
      if (visited[i] == false)
        topologicalSortUtil(i, visited, Stack);

    // Print contents of stack
    while (Stack.empty() == false)
    {
        cout << Stack.top() << " ";
        Stack.pop();
    }
}

int main()
{
    // Create a graph given in the above diagram
    Graph g(6);
    g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);

    cout << "Following is a Topological Sort of the given graph n";
    g.topologicalSort();

    return 0;
}

Java

import java.io.*;
import java.util.*;

// This class represents a directed graph using adjacency
// list representation
class Graph
{
    private int V;   // No. of vertices
    private LinkedList<Integer> adj[]; // Adjacency List

    //Constructor
    Graph(int v)
    {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList();
    }

    // Function to add an edge into the graph
    void addEdge(int v,int w) { adj[v].add(w); }

    // A recursive function used by topologicalSort
    void topologicalSortUtil(int v, boolean visited[],
                             Stack stack)
    {
        // Mark the current node as visited.
        visited[v] = true;
        Integer i;

        // Recur for all the vertices adjacent to this
        // vertex
        Iterator<Integer> it = adj[v].iterator();
        while (it.hasNext())
        {
            i = it.next();
            if (!visited[i])
                topologicalSortUtil(i, visited, stack);
        }

        // Push current vertex to stack which stores result
        stack.push(new Integer(v));
    }

    // The function to do Topological Sort. It uses
    // recursive topologicalSortUtil()
    void topologicalSort()
    {
        Stack stack = new Stack();

        // Mark all the vertices as not visited
        boolean visited[] = new boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;

        // Call the recursive helper function to store
        // Topological Sort starting from all vertices
        // one by one
        for (int i = 0; i < V; i++)
            if (visited[i] == false)
                topologicalSortUtil(i, visited, stack);

        // Print contents of stack
        while (stack.empty()==false)
            System.out.print(stack.pop() + " ");
    }

    public static void main(String args[])
    {
        // Create a graph given in the above diagram
        Graph g = new Graph(6);
        g.addEdge(5, 2);
        g.addEdge(5, 0);
        g.addEdge(4, 0);
        g.addEdge(4, 1);
        g.addEdge(2, 3);
        g.addEdge(3, 1);

        System.out.println("Following is a Topological " +
                           "sort of the given graph");
        g.topologicalSort();
    }
}