Lintcode 127 Topological Sorting
https://www.lintcode.com/problem/127/description
Given an directed graph, a topological order of the graph nodes is defined as follow:
For each directed edge A -> B in graph, A must before B in the order list.
The first node in the order can be any node in the graph with no nodes direct to it.
Find any topological order for the given graph.We can follow the steps introduced in https://leetcode-solution.com/breadth-first-search to solve this problem.
One thing to note is that, for topological sorting, we do NOT have a variable called visited to record visited nodes while BFS. Why?
First of all, let’s ask why we needed it for other BFS’ in the first place? Think about the timing when we put the node into visited, for general BFS’, when we see the node for the very first time, we added it to the queue so it can be process later, BUT it could also be seen at a later time from other parent node. That’s why we want to mark it as visited so it won’t be visited multiple times.
But for topological sort, things are a little bit different. Only when the in degree becomes 0 we put the node in the queue for later processing. This timing means, the node is seen for the very last time because there’s no other edges pointing to it anymore. That’s why we don’t have to worry about visiting it again.
Let’s take a look at the solution:
"""
class DirectedGraphNode:
def __init__(self, x):
self.label = x
self.neighbors = []
"""
class Solution:
"""
@param graph: A list of Directed graph node
@return: Any topological order for the given graph.
"""
def topSort(self, graph):
# write your code here
queue = collections.deque()
result = []
# get a dict keyed by node and valued by the node's indegree
in_degree = {}
for node in graph:
if node not in in_degree:
in_degree[node] = 0
for neighbor in node.neighbors:
if neighbor in in_degree:
in_degree[neighbor] += 1
else:
in_degree[neighbor] = 1
# find the nodes that have indegree as 0 and put them in the queue
for key, count in in_degree.items():
if count == 0:
queue.append(key)
while queue:
node = queue.popleft()
result.append(node)
for neighbor in node.neighbors:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return result