Topological sorting for a directed acyclic graph

Question

Is it possible to have different topological sorts for a directed acyclic graph G? For example in a graph:

A --> B --> D
      B --> E
A --> C --> E

I thought topological sorts depend on the finishing times of each vertex after running a depth-first-search algorithm. Isn't each finishing time unique and thus only one topological sort for G is possible?

Answer 1

yes. you can traverse the graph in multiple ways.

In your example, you can have A, B ,.... or A, C, ......

The wikipedia page on topological sorting has a better example: http://en.wikipedia.org/wiki/Topological_sorting

From the wiki page cited above:

If a topological sort has the property that all pairs of consecutive vertices in the sorted order are connected by edges, then these edges form a directed Hamiltonian path in the DAG. If a Hamiltonian path exists, the topological sort order is unique; no other order respects the edges of the path. Conversely, if a topological sort does not form a Hamiltonian path, the DAG will have two or more valid topological orderings, for in this case it is always possible to form a second valid ordering by swapping two consecutive vertices that are not connected by an edge to each other. Therefore, it is possible to test in linear time whether a unique ordering exists, and whether a Hamiltonian path exists, despite the NP-hardness of the Hamiltonian path problem for more general directed graphs (Vernet & Markenzon 1997).

Answer 2

public class TopologicalSort
{
    private int V;   // No. of vertices
    private List<int> [] adj; // Adjacency List

    public ToplogicalSort(int v)
    {
        V = v;
        adj = new List<int>[v];
        for (int i=0; i < v; ++i)
            adj[i] = new List<int>();
    }

    public void AddEdge(int v,int w) { adj[v].Add(w); }

    public void TopologicalSortUtil(int v, bool[] visited, Stack<int> stack)
    {
        Stack<int> stackTracing = new Stack<int>();
        bool res = true;
        List<int> list = new List<int>(adj[v]);
        stackTracing.Push(v);
        while (stackTracing.Count != 0 | res)
        {
            int n = stackTracing.Peek();
            list = new List<int>(adj[n]);
            bool check = false;
            foreach (var elem in list)
            {
                if (!visited[elem])
                {
                    visited[elem] = true;
                    n = elem;
                    stackTracing.Push(elem);
                    check = true;
                    break;
                }
            }

            if(!check)
            {
                if(!stack.Contains(n))
                {
                    stack.Push(n);
                }
                if (stackTracing.Count != 0)
                    stackTracing.Pop();
                res = false;
            }           
        }
    }

    public void TopologicalSort()
    {
        Stack<int> stack = new Stack<int>();
        bool[] visited = new bool[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;

        for (int i = 0; i < V; i++)
        {
            if (visited[i] == false)
            {
                topologicalSortUtil(i, visited, stack);
            }
        }
        // Print contents of stack
        while (stack.Count != 0)
        {
            stack.Pop();
            Console.WriteLine(stack.Pop() + " ");
        }
    }
    public static void RunSort()
    {
        TopologicalSort g = new TopologicalSort(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);
        g.TopologicalSort();
    }
}