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
|
"""
Definition for a Directed graph node
class DirectedGraphNode:
def __init__(self, x):
self.label = x
self.neighbors = []
"""
import collections
class :
"""
@param: graph: A list of Directed graph node
@return: Any topological order for the given graph.
"""
def topSort(self, graph):
indegree = self.indegree_node(graph)
queue = collections.deque()
result = []
for i in indegree:
if indegree[i] == 0:
queue.append(i)
while len(queue):
head = queue.popleft()
result.append(head)
for i in head.neighbors:
indegree[i] -= 1
if indegree[i] == 0:
queue.append(i)
return result
def indegree_node(self, graph):
indegree_nodes = {}
for i in graph:
if i not in indegree_nodes:
indegree_nodes[i] = 0
for j in i.neighbors:
if j not in indegree_nodes:
indegree_nodes[j] = 0
indegree_nodes[j] += 1
return indegree_nodes
|
近期评论