forked from rajnishmaurya73/algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
/
topological sort
28 lines (25 loc) · 963 Bytes
/
topological sort
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
topological_sort(N, adj[N][N])
T = []
visited = []
in_degree = []
for i = 0 to N
in_degree[i] = visited[i] = 0
for i = 0 to N
for j = 0 to N
if adj[i][j] is TRUE
in_degree[j] = in_degree[j] + 1
for i = 0 to N
if in_degree[i] is 0
enqueue(Queue, i)
visited[i] = TRUE
while Queue is not Empty
vertex = get_front(Queue)
dequeue(Queue)
T.append(vertex)
for j = 0 to N
if adj[vertex][j] is TRUE and visited[j] is FALSE
in_degree[j] = in_degree[j] - 1
if in_degree[j] is 0
enqueue(Queue, j)
visited[j] = TRUE
return T