Topological Sort

Topological sort is an algorithm that sort the vertices of a #directed acyclic graph in such that it respect the ordering of the vertices in this original graph. We could use the indegree (the incoming edges) to determine the order of the vertices.

Analysis

  • If naively do a sequential search for a vertex with indegree 0 in the array that store the corresponding indegree value of the vertices, the algorithm will result in \(O(\vert V \vert^2)\).
  • When optimised with 202112031157 or 202112101836, it results in \(O(\vert E \vert + \vert V \vert)\)

Implementation

Note: This algorithm uses 202112101836 where all vertices of indegree 0 will be placed into the queue initially or upon decremented. 

void Topsort(Graph G)
{
  Queue Q;
  int Counter = 0;
  Vertex V, W;

  Q = CreateQueue(NumVertex);
  MakeEmpty(Q);
  for each vertex V
    if (Indegree[V] == 0)
      Enqueue(V, Q);

  while (!IsEmpty(Q)) {
    V = Dequeue(Q);
    TopNum[V] = ++Counter;  // Assign next number

    for each W adjacent to V
      if (--Indegree[W] == 0)
        Enqueue(W, Q);
  }

  if (Counter != NumVertex)
    Error("Graph has a cycle");

  DisposeQueue(Q);
}
Links to this page
#algorithm