Course Schedule problem where each courses should be listed according to pre-requisites. The output list sequence should always start with no pre-requisite courses and any course in the sequence should have already met the prerequisites before it. Using topological sort on DAG (Directed acyclic graph) I am not getting the expected output.
courses_and_prereqs_in_list = {
“algorithms”: [“data structures”],
“calculus”: [“linear algebra”],
“compilers”: [“data structures”, “formal languages”, “computer organization”],
“data structures”: [“discrete math”],
“databases”: [“data structures”],
“discrete math”: [“intro to programming”],
“formal languages”: [“discrete math”],
“networks”: [“operating systems”],
“operating systems”: [“data structures”, “computer organization”],
“programming languages”: [“data structures”, “computer organization”],
}
##My Code
from collections import defaultdict
course = ['computer organization', 'intro to programming', 'calculus', 'discrete math', 'formal languages', 'programming languages', 'networks', 'algorithms', 'databases', 'linear algebra', 'data structures', 'compilers', 'operating systems']
class Graph:
def __init__(self, vertices):
self.graph = defaultdict(list)
self.V = vertices
def addEdge(self, u, v):
self.graph[u].append(v)
def neighbor_gen(self, v):
for k in self.graph:
yield k
def topologicalsortutil(self, v, visited, stack):
working_stack = [(v, self.neighbor_gen(v))]
while working_stack:
v, gen = working_stack.pop()
visited[v] = True
for next_neighbor in gen:
if not visited[next_neighbor]:
working_stack.append((v,gen))
working_stack.append((next_neighbor, self.neighbor_gen(next_neighbor)))
break
else:
stack.append(v)
def topologicalsort(self):
visited = [False]*self.V
stack = []
for i in range(self.V):
if not (visited[i]):
self.topologicalsortutil(i, visited, stack)
stack.reverse()
return stack
g = Graph(13)
g.addEdge(11, 0)
g.addEdge(12, 0)
g.addEdge(5, 0)
g.addEdge(3, 1)
g.addEdge(2, 9)
g.addEdge(11, 10)
g.addEdge(11, 4)
g.addEdge(8, 10)
g.addEdge(7, 10)
g.addEdge(6, 12)
g.addEdge(4, 3)
g.addEdge(10, 3)
Need help in correcting the code to get