[算法] Topological Sorting

Question
Topological Sorting

Question 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.

Language
Python 3

Data structure description
""" Definition for a Directed graph node class DirectedGraphNode: def __init__(self, x): self.label = x self.neighbors = [] """

Thinking Solution
(1) Get in degree value,
(2) FInd start node (In degree equal 0)
(3) Using queue to perform BFS: Get neighbors to calculate in degree value
(4) Return result

Solution
class Solution: def topSort(self, graph): node_to_degree = self.getInDegree(graph) order = [] start_nodes = [node for node in graph if node_to_degree[node] == 0] queue = collections.deque(start_nodes) while queue: tmp_node = queue.popleft() order.append(tmp_node) for neighbor in tmp_node.neighbors: node_to_degree[neighbor] -= 1 if node_to_degree[neighbor] == 0: queue.append(neighbor) return order def getInDegree(self, graph): output = {x: 0 for x in graph} for node in graph: for neighbor in node.neighbors: if neighbor in output: output[neighbor] += 1 return output

Reference Link
https://www.lintcode.com/problem/topological-sorting/description