Topological Sorting is a fundamental algorithm in computer science, primarily used on Directed Acyclic Graphs (DAGs). It provides a linear ordering of vertices such that for every directed edge u → v, vertex u comes before vertex v in the ordering. This sorting is crucial in various applications like task scheduling, course prerequisite ordering, and resolving symbol dependencies in linkers.

Program Structure

The C++ program to perform Topological Sorting is organized into the following key components:

• Graph Representation: Using an adjacency list to represent the DAG.
• Topological Sorting Implementation: Utilizing Depth-First Search (DFS) for the sorting process.
• Main Function: Handling input, invoking the sorting algorithm, and displaying the result.

Code Implementation

The following C++ program implements Topological Sorting on a Directed Acyclic Graph using the DFS-based approach:

// Topological Sorting of a Directed Acyclic Graph (DAG) in C++
// This program performs topological sorting using Depth-First Search (DFS).

#include <iostream>
#include <vector>
#include <stack&gt>
#include <list&gt>
#include <algorithm&gt>

using namespace std;

// Class to represent a graph using adjacency list representation
class Graph {
    int V; // Number of vertices
    list *adj; // Pointer to an array containing adjacency lists

    // A recursive function used by topologicalSort
    void topologicalSortUtil(int v, vector &visited, stack &Stack);
public:
    Graph(int V); // Constructor
    void addEdge(int v, int w); // Function to add an edge to graph
    void topologicalSort(); // Function to perform Topological Sort
};

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

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

// A recursive function to perform DFS and store the vertex in stack
void Graph::topologicalSortUtil(int v, vector &visited, stack &Stack) {
    // Mark the current node as visited
    visited[v] = true;

    // Recur for all the vertices adjacent to this vertex
    for(auto it = adj[v].begin(); it != adj[v].end(); ++it) {
        if(!visited[*it]) {
            topologicalSortUtil(*it, visited, Stack);
        }
    }

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

// Function to perform Topological Sort
void Graph::topologicalSort() {
    stack Stack;

    // Mark all the vertices as not visited
    vector visited(V, 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]) {
            topologicalSortUtil(i, visited, Stack);
        }
    }

    // Print contents of stack
    cout << "Topological Sort of the given graph is:\n";
    while(!Stack.empty()) {
        cout << Stack.top() << " ";
        Stack.pop();
    }
    cout << endl;
}

int main() {
    int V, E;
    cout << "Enter the number of vertices: ";
    cin >> V;
    cout << "Enter the number of edges: ";
    cin >> E;

    Graph g(V);

    cout << "Enter the edges in the format (source destination):\n";
    for(int i = 0; i < E; i++) {
        int src, dest;
        cin >> src >> dest;
        g.addEdge(src, dest);
    }

    g.topologicalSort();

    return 0;
}
        

Program Explanation

The program implements Topological Sorting using a Depth-First Search (DFS) approach. Below is a detailed explanation of its components:

1. Graph Representation

The graph is represented using an adjacency list, which is an array of lists. Each index of the array represents a vertex, and each element in the list at that index represents an adjacent vertex.

list<int> *adj;

2. Adding Edges

The addEdge function adds a directed edge from vertex v to vertex w.

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

3. Topological Sorting Utility Function

The topologicalSortUtil function performs a recursive DFS starting from a given vertex. It marks the vertex as visited, explores all its adjacent vertices, and finally pushes the vertex onto a stack. This ensures that vertices are pushed onto the stack only after all their dependencies are processed.

void Graph::topologicalSortUtil(int v, vector<bool> &visited, stack<int> &Stack) {
    visited[v] = true;
    for(auto it = adj[v].begin(); it != adj[v].end(); ++it) {
        if(!visited[*it]) {
            topologicalSortUtil(*it, visited, Stack);
        }
    }
    Stack.push(v);
}
        

4. Topological Sort Function

The topologicalSort function initializes a stack and a visited vector. It iterates through all vertices, and for each unvisited vertex, it calls the utility function to perform DFS. After processing all vertices, it pops elements from the stack to get the topological ordering.

void Graph::topologicalSort() {
    stack<int> Stack;
    vector<bool> visited(V, false);

    for(int i = 0; i < V; i++) {
        if(!visited[i]) {
            topologicalSortUtil(i, visited, Stack);
        }
    }

    cout << "Topological Sort of the given graph is:\n";
    while(!Stack.empty()) {
        cout << Stack.top() << " ";
        Stack.pop();
    }
    cout << endl;
}
        

5. Main Function

The main function handles user input, creates the graph, adds the edges based on user input, and invokes the topological sort function.

int main() {
    int V, E;
    cout << "Enter the number of vertices: ";
    cin >> V;
    cout << "Enter the number of edges: ";
    cin >> E;

    Graph g(V);

    cout << "Enter the edges in the format (source destination):\n";
    for(int i = 0; i < E; i++) {
        int src, dest;
        cin >> src >> dest;
        g.addEdge(src, dest);
    }

    g.topologicalSort();

    return 0;
}
        

Program Documentation

Detailed documentation for each component of the program:

Class: Graph

• Purpose: Represents a directed graph using an adjacency list and provides functionality to perform topological sorting.
• Members:
  • int V; – Number of vertices in the graph.
  • list<int> *adj; – Pointer to an array of adjacency lists.
• Functions:
  • Graph(int V); – Constructor to initialize the graph with V vertices.
  • void addEdge(int v, int w); – Adds a directed edge from vertex v to vertex w.
  • void topologicalSort(); – Performs topological sorting of the graph.

Function: topologicalSortUtil

• Purpose: A recursive helper function for performing DFS and storing the vertices in a stack to achieve topological ordering.
• Parameters:
  • int v – The current vertex being processed.
  • vector<bool> &visited – Vector to keep track of visited vertices.
  • stack<int> &Stack – Stack to store the topological order.
• Returns: None. The function updates the Stack with the vertex v.

Function: topologicalSort

• Purpose: Initiates the topological sort process and prints the sorted order.
• Parameters: None.
• Returns: None. Prints the topological order to the console.

Function: main

• Purpose: Entry point of the program. Handles user input, constructs the graph, and invokes the topological sort.
• Parameters: None.
• Returns: 0 upon successful execution.

How the Program Works

1. Input Handling: The program begins by prompting the user to enter the number of vertices (V) and the number of edges (E). It then reads each edge’s source and destination vertices.
2. Graph Construction: Using the addEdge function, the program constructs the adjacency list representation of the graph.
3. Topological Sorting: The topologicalSort function is called to perform the sorting. It initializes a stack and a visited vector, then iterates through all vertices, performing DFS on unvisited vertices.
4. Result Display: After completing the sorting, the program pops elements from the stack to display the topological order.

Example Execution

Consider the following example graph:

Enter the number of vertices: 6
Enter the number of edges: 6
Enter the edges in the format (source destination):
5 2
5 0
4 0
4 1
2 3
3 1
        

Running the program with the above input will produce the following output:

Topological Sort of the given graph is:
5 4 2 3 1 0 
        

This output represents one possible topological ordering of the vertices in the graph. Note that multiple valid topological orders may exist for a given DAG.

Conclusion

Topological Sorting is an essential algorithm for ordering tasks with dependencies. This C++ implementation using the DFS-based approach provides an efficient way to achieve a linear ordering of vertices in a Directed Acyclic Graph. Understanding and implementing topological sorting is crucial for solving various real-world problems, including task scheduling, resolving symbol dependencies, and more.