Introduction

Note:

• We will be using 2D arrays(adjacency matrix) for implementing graph.
• We shall implement a directed graph.
• Make a point that the order of traversing actually can be anything like ascending or descending or random, but will stick to traverse each node in ascending order.
• The output will differ because it depends on what vertex you start with and in what order you traverse them.

Working Procedure

Do refer the code available the end of this section to understand the following theory.

1. Inserting new vertices and edges is same as previously done in Graph Traversal Techniques except that here, it is a directed graph.
2. Let V be the number of vertices and E be the number of edges in the graph.
3. Whenever a new edge is added from u->v, increment the indegree of v only because it's a directed graph.
4. Topological Sort:
   1. Initially push the vertices on to a stack whose indegree is 0.
   2. Loop from i=0 to V
      1. Loop until the stack is not empty i.e top != -1.
      2. Pop the top of stack and add it to the topological order array.
      3. Now decrement the indegree of the adjacent vertices of this popped vertex and if indegree of the adjacent vertex becomes zero then push it to the stack.
   3. If the length of the topological order array is not equal to V then the graph has a cycle.
   4. Else we have the required topological sort in the topological order array.

Time Complexity: O(V+E)

Similar posts: Graph Data Structure | Graph Traversal Techniques