Topological sorting for a graph is not possible if the graph is not a DAG.
from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.graph = defaultdict(list)
self.vertices = vertices
def addEdge(self, u, v):
self.graph[u].append(v)
def getDegree(graph, vertices):
degrees = [0]*vertices
for v in graph:
for vv in graph[v]:
degrees[vv] += 1
return degrees
BFS TopologicalSort
def topologicalSort(graph) :
indegrees = getDegree(graph.graph, graph.vertices)
visited = set()
path = []
for v in range(graph.vertices):
#print(v)
if indegrees[v] == 0:
bfs_ts(graph.graph, v, visited, path)
return path
import collections
def bfs_ts(graph, v, visited, path):
queue = collections.deque()
queue.append(v)
visited.add(v)
while queue:
v = queue.popleft()
path.append(v)
for nei in graph[v]:
if nei not in visited:
visited.add(nei)
queue.append(nei)
# If vertices left, indegree ==0 will add the path
DFS TopologicalSort
def topologicalSort(graph):
degree = getDegree(graph.graph, graph.vertices)
visited = set()
path = []
for v in range(graph.vertices):
if degree[v] == 0:
dfs_ts(graph.graph, v, visited, path)
return path[::-1]
def dfs_ts(graph, v, visited, path):
visited.add(v)
for nb in graph[v]:
if nb not in visited:
dfs_ts(graph, nb, visited, path)
path.append(v)
Test topologicalSort
myGraph = Graph(5)
myGraph.addEdge(0, 1)
myGraph.addEdge(0, 3)
myGraph.addEdge(1, 2)
myGraph.addEdge(2, 3)
myGraph.addEdge(2, 4)
myGraph.addEdge(3, 4)
print(topologicalSort(myGraph)) # [0, 1, 2, 3, 4]
myGraph = Graph(6)
myGraph.addEdge(5, 2)
myGraph.addEdge(5, 0)
myGraph.addEdge(4, 0)
myGraph.addEdge(4, 1)
myGraph.addEdge(2, 3)
myGraph.addEdge(3, 1)
print(topologicalSort(myGraph)) # [5, 4, 2, 3, 1, 0]"
