Topological- Sort Algorithm
The Topological Sort Algorithm is a linear ordering algorithm specifically designed for directed acyclic graphs (DAGs). The purpose of this algorithm is to provide a linear ordering of the vertices in such a way that for every directed edge (u, v) from vertex u to vertex v, vertex u comes before vertex v in the ordering. This algorithm is particularly useful in scenarios where certain tasks must be performed in a specific order, such as scheduling tasks with dependencies or determining the sequence of courses to take in a curriculum with prerequisites.
Topological sorting can be implemented using depth-first search (DFS) or Kahn's algorithm. In the DFS-based approach, the algorithm traverses the graph in a depth-first manner, marking visited nodes and adding them to the result in reverse post-order. On the other hand, Kahn's algorithm iteratively finds nodes with no incoming edges, adds them to the result, and removes their outgoing edges. Both algorithms ensure that vertices with dependencies are visited before dependent vertices, resulting in a valid topological ordering. It is important to note that topological sorting is only possible for acyclic graphs, as the presence of a cycle would create a circular dependency, making it impossible to establish a linear order.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m; // For number of Vertices (V) and number of edges (E)
vector<vector<int>> G;
vector<bool> visited;
vector<int> ans;
void dfs(int v)
{
visited[v] = true;
for (int u : G[v])
{
if (!visited[u])
dfs(u);
}
ans.push_back(v);
}
void topological_sort()
{
visited.assign(n, false);
ans.clear();
for (int i = 0; i < n; ++i)
{
if (!visited[i])
dfs(i);
}
reverse(ans.begin(), ans.end());
}
int main()
{
cout << "Enter the number of vertices and the number of directed edges\n";
cin >> n >> m;
int x, y;
G.resize(n, vector<int>());
for (int i = 0; i < n; ++i)
{
cin >> x >> y;
x--, y--; // to convert 1-indexed to 0-indexed
G[x].push_back(y);
}
topological_sort();
cout << "Topological Order : \n";
for (int v : ans)
{
cout << v + 1 << ' '; // converting zero based indexing back to one based.
}
cout << '\n';
return 0;
}
