Topological Sorting | DSA in C++ - Software Development PDF Download

Introduction

In computer science, topological sorting is an algorithmic technique used to order the vertices of a directed graph in such a way that for every directed edge from vertex A to vertex B, A comes before B in the ordering. This technique is widely used in various applications such as task scheduling, dependency resolution, and determining the execution order of a set of tasks with dependencies.

How does it work?

Topological sorting can be performed using Depth-First Search (DFS) or Breadth-First Search (BFS) algorithms. Here, we will focus on the DFS approach.

The steps involved in performing topological sorting using DFS are as follows:

• Choose a starting vertex arbitrarily.
• Perform a depth-first search from the chosen vertex.
• When a vertex has no outgoing edges or all its neighbors have been visited, add it to the front of a list.
• Repeat steps 2 and 3 for all unvisited vertices.

At the end of this process, the resulting list will contain the vertices in a valid topological order.

Example: Topological Sorting using DFS

Let's understand the process of topological sorting with an example. Consider the following directed graph:

      4    5

     /    / \

    v    v   v

    2 -> 0 -> 1

     \    ^

      v  /

       3

We will perform topological sorting on this graph using DFS.

Code:

#include <iostream>

#include <vector>

#include <stack>

using namespace std;

void topologicalSortDFS(vector<vector<int>>& graph, int vertex, vector<bool>& visited, stack<int>& result) {

    visited[vertex] = true;

    for (int neighbor : graph[vertex]) {

        if (!visited[neighbor]) {

            topologicalSortDFS(graph, neighbor, visited, result);

        }

    }

    result.push(vertex);

}

vector<int> topologicalSort(vector<vector<int>>& graph, int numVertices) {

    vector<bool> visited(numVertices, false);

    stack<int> result;

    for (int i = 0; i < numVertices; i++) {

        if (!visited[i]) {

            topologicalSortDFS(graph, i, visited, result);

        }

    }

    vector<int> sortedVertices;

    while (!result.empty()) {

        sortedVertices.push_back(result.top());

        result.pop();

    }

    return sortedVertices;

}

int main() {

    int numVertices = 6;

    vector<vector<int>> graph(numVertices);

    // Add directed edges

    graph[2].push_back(0);

    graph[2].push_back(3);

    graph[3].push_back(1);

    graph[4].push_back(0);

    graph[4].push_back(1);

    graph[5].push_back(2);

    graph[5].push_back(0);

    vector<int> sortedVertices = topologicalSort(graph, numVertices);

    // Print the sorted vertices

    cout << "Topological order: ";

    for (int vertex : sortedVertices) {

        cout << vertex << " ";

    }

    return 0;

}

• The 'topologicalSortDFS' function performs a depth-first search on the graph starting from the given vertex. It marks the current vertex as visited and recursively calls itself for all unvisited neighbors.
• The 'topologicalSort' function initializes the visited array and a stack to store the sorted vertices. It iterates over all vertices and calls 'topologicalSortDFS' for each unvisited vertex.
• After the DFS traversal, the sorted vertices are obtained by popping elements from the stack and adding them to a vector in reverse order.
• The 'main' function creates a directed graph and calls the 'topologicalSort' function. It then prints the sorted vertices.

Output:

Topological order: 5 4 2 3 0 1

The topological order of the given graph is '5 4 2 3 0 1', which satisfies the ordering condition.

Sample Problems

• Given a list of tasks with dependencies, find a valid order of task execution using topological sorting.
• Determine if a directed graph contains a cycle. If it does, the graph cannot be topologically sorted.
• Find the minimum number of semesters required to complete all courses given their prerequisites. Use topological sorting to determine the order of course completion.

Conclusion

Topological sorting is a powerful algorithmic technique used to order the vertices of a directed graph. By performing a depth-first search, we can obtain a valid topological order. This technique finds applications in various domains, including task scheduling and dependency resolution. Understanding and implementing topological sorting will enable you to solve a wide range of problems efficiently.