Algorithm

LintCode/Topological Sorting

Problem Summary

Given an directed graph, find any topological order for it.

Solution

Topological sorting is a very classic algorithm. It can be implemented in many ways. I used Kahn’s algorithm.

For details, check this:
Topological sorting - Wikipedia

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*
 struct directedgraphnode {
     int label;
     vector<directedgraphnode *> neighbors;
     directedgraphnode(int x) : label(x) {};
 };
*/
class Solution {
public:
    /*
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */
    vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*>& graph) {
        int n = graph.size();
        int nums[n+1],indegree[n+1];
       	
       	memset(indegree,0,sizeof(indegree));
        for (int i = 0; i < n; ++i)
        {
        	nums[i] = graph[i]->neighbors.size();
        	for (int j = 0; j < nums[i]; ++j)
        		++indegree[graph[i]->neighbors[j]->label];
        }
        bool vis[n+1];
        memset(vis,0,sizeof(vis));
        vector<DirectedGraphNode*> res;
        int k = n;
        while (k)
        {
			for (int i = 0; i < n; ++i)
	       	{
	       		int x = graph[i]->label;
	       		if (!vis[x] && indegree[x]==0)
	       		{
	       			--k;
	       			vis[x] = true;
	       			res.push_back(graph[i]);
	       			for (int j = 0; j < nums[i]; ++j)
	       			{
	       				int y = graph[i]->neighbors[j]->label;
	       				if (!vis[y])
	       					--indegree[y];
	       			}
	       		}
			}
        }
        
       	return res;
    }
};