Topological sorting arranges the nodes of a directed acyclic graph (DAG) in a linear order. In this linear order, if there is a directed edge from node A to node B, then A will always appear before B. This ordering is known as a topological order.

Topological sorting ensures that all the dependencies of a given node are resolved before the node itself. It allows us to establish a precedence relationship between the nodes in a graph. A graph can have multiple valid topological orders, or it may not have any if it contains cycles.

To perform a topological sorting, we can utilize a depth-first search (DFS) algorithm. The basic idea is to visit each node in the graph and explore its neighbours recursively until there are no more unvisited neighbours. After visiting all the neighbours, we add the current node to the front of the topological ordering. This process is repeated for all the nodes in the graph.

Code:

#include

#include

#include

using namespace std;

void DFS(int node, vector<vector>& adjList, vector& visited, stack& sortedStack) {

visited[node] = true;

for (int neighbor : adjList[node]) {

if (!visited[neighbor]) {

DFS(neighbor, adjList, visited, sortedStack);

}

}

sortedStack.push(node);

}

vector topologicalSort(vector<vector>& adjList, int numNodes) {

vector sorted;

vector visited(numNodes, false);

stack sortedStack;

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

if (!visited[i]) {

DFS(i, adjList, visited, sortedStack);

}

}

while (!sortedStack.empty()) {

sorted.push_back(sortedStack.top());

sortedStack.pop();

}

return sorted;

}

int main() {

int numNodes, numEdges;

cout << "Enter the number of nodes: ";

cin >> numNodes;

cout << "Enter the number of edges: ";

cin >> numEdges;

vector<vector> adjList(numNodes);

cout << "Enter the edges (source destination): " << endl;

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

int src, dest;

cin >> src >> dest;

adjList[src].push_back(dest);

}

vector sortedOrder = topologicalSort(adjList, numNodes);

cout << "Topological Order: ";

for (int node : sortedOrder) {

cout << node << " ";

}

cout << endl;

return 0;

}

Applications of Topological Sorting:

1. Task Scheduling: Topological sorting is commonly used in project management and task scheduling. In a project with multiple dependent tasks, topological sorting can determine the order in which tasks should be executed to meet dependencies. This helps in optimizing the project timeline and ensuring that all dependencies are satisfied.

2. Dependency Resolution: In software development, topological sorting is used to resolve dependencies between modules or libraries. By arranging the modules in a topological order, developers can ensure that modules dependent on others are built or loaded first, preventing any runtime errors due to missing dependencies.

3. Build Systems: Build systems, such as Make or CMake, employ topological sorting to determine the order in which source code files or modules should be compiled. By analyzing the dependencies between files, the build system can efficiently compile and link the components in the correct order, improving the build process's speed and reliability.

4. Course Prerequisites: In educational institutions, topological sorting can be used to determine the prerequisites for different courses. By constructing a directed graph representing the course dependencies, students can be guided to take courses in the correct order, ensuring they have the necessary foundational knowledge.

5. Event Scheduling: Topological sorting is useful in scheduling events or activities that have precedence relationships. For example, in a conference schedule, certain talks or workshops may have prerequisites or dependencies on others. Topological sorting can determine the order in which these events should be scheduled to maintain a logical flow throughout the conference.

These are just a few examples of how topological sorting can be applied in various real-world scenarios. The algorithm's ability to establish a linear order based on dependencies is a powerful tool for organizing and optimizing processes in many domains.