DirectedGraph::topologicalSort

Function

vector<Vertex<T> > topologicalSort();

Returns the topological order of a directed acyclic graph.

Parameters

None

Return value

If the graph is not acyclic, return a empty vector.
If the grapht is acyclic return a vector contain all nodes in a topological order.

Example

#include "HKUAL_graph.h"
#include <iostream>
#include <vector>
using namespace std;
using namespace HKUAL;

int main(){
    DirectedGraph<string> g;
    g.addVertex("A");
    g.addVertex("B");
    g.addVertex("C");
    g.addVertex("D");
    g.addVertex("E");
    g.addEdge("A","B");
    g.addEdge("A","C");
    g.addEdge("B","C");
    g.addEdge("B","D");
    g.addEdge("C","D");
    g.addEdge("D","E");
    g.addEdge("A","E");

    vector<Vertex<string> > v = g.topologicalSort();
    for (int i = 0; i < v.size(); i++)
        cout << v[i].label << endl;
    return 0;
}

Output

A
B
C
D
E

Time Complexity

, for is number of edges and is total number of vertives.