Topological Sorting

                                                 Resource Link

Topological Sorting (E-Maxx)

Kahn’s algorithm for Topological Sorting

Topological Sorting

TopSort using DFS:

	#include<bits/stdc++.h>
	using namespace std;
	const int maxn = 10005;
	int n,m;
	vector<int>graph[maxn];
	vector<bool> visited;
	vector<int>ans;
	void dfs(int v)
	{
	visited[v] = true;
	for(int u: graph[v]){
	if(!visited[u])
	dfs(u);
	}
	ans.push_back(v);
	}
	void topSort()
	{
	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()
	{
	cin >> n >> m;
	for(int i = 0; i < m; i++){
	int u,v;
	cin >> u >> v;
	graph[u].push_back(v);
	}
	topSort();
	for(int i = 0; i < ans.size(); i++)
	cout << ans[i]<< " ";
	return 0;
	}
	/*
	6 6
	5 2
	5 0
	4 0
	4 1
	2 3
	3 1
	*/

view raw topsort.cpp hosted with ❤ by GitHub

TopSort using BFS: (Kahn’s algorithm)

	//Kahn’s algorithm, is somewhat similar to BFS.
	#include<bits/stdc++.h>
	using namespace std;
	const int maxn = 1005;
	vector<int>graph[maxn];
	priority_queue<int, vector<int>, greater<int> > PQ;
	int in_degree[maxn];
	vector<int> ans;
	int main()
	{
	int n,m;
	cin >> n >> m;
	for(int i = 0; i < m; i++)
	{
	int u,v;
	cin >> u >> v;
	graph[u].push_back(v);
	in_degree[v]++;
	}
	for(int i = 1; i <= n; i++)
	{
	// cout << in_degree[i] << " ";
	if(in_degree[i] == 0)
	PQ.push(i);
	}
	if(PQ.size() == 0)
	{
	cout << "Cycle Detected\n";
	return 0;
	}
	//cout << PQ.size()<<endl;
	// for(int i = 0; i < n; i++){
	// for(int x = 0; x < graph[i].size(); x++)
	// cout << graph[i][x]<< " ";
	// cout << "-----------\n";;
	// }
	while(!PQ.empty())
	{
	int u = PQ.top();
	// cout << u << endl;
	ans.push_back(u);
	PQ.pop();
	for(int x = 0; x < graph[u].size(); x++)
	{
	int v = graph[u][x];
	// cout << u << " "<<v << endl;
	in_degree[v]--;
	if(in_degree[v] == 0)PQ.push(v);
	}
	}
	//cout << ans.size()<<endl;
	int sz = ans.size();
	if(sz < n)
	{
	cout << "Cycle Detected\n";
	return 0;
	}
	for(int i = 0; i < sz; i++)
	{
	cout << ans[i]<< " ";
	}
	return 0;
	}

view raw Kahn’s algorithm.cpp hosted with ❤ by GitHub

Share: