In: Computer Science
Redesign topsort so it selects the LAST NODE in each iteration, rather than the first.
def topsort(G):
count = dict((u, 0) for u in G) # The in-degree for each node
for u in G:
for v in G[u]:
count[v] += 1 # Count every in-edge
Q = [u for u in G if count[u] == 0] # Valid initial nodes
S = [] # The result
while Q: # While we have start nodes...
u = Q.pop() # Pick one
S.append(u) # Use it as first of the rest
for v in G[u]:
count[v] -= 1 # "Uncount" its out-edges
if count[v] == 0: # New valid start nodes?
Q.append(v) # Deal with them next
return S
topsort will function as reverse. In this topological sorting is used to increase the accuracy.
for getting your final output you have to re-arrage some function and apply some extra logic these will work in most of test cases , but you got any problem please rebuild some functions and try to execute.The program will work correct.
also Depth First Search can be used.
for example:
dag <- DAG(a ~ b, c ~ a + b, d ~ c + b)
dag
topOrder(dag)
topSort(dag)
#solution
class Test:
def __init__(self, vertices):
self.Test = defaultdict(list)
self.V = vertices
def adeg(self, u, v):
self.Test[u].append(v)
def toposort(self):
in_degree = [0]*(self.V)
for i in self.Test:
for j in self.Test[i]:
in_degree[j] += 1
queue = []
for i in range(self.V):
if in_degree[i] == 0:
queue.append(i)
cnt = 0
t_order = []
while queue:
u = queue.pop(0)
t_order.append(u)
for i in self.Test[u]:
in_degree[i] -= 1
# If in-degree becomes zero, add it to queue
if in_degree[i] == 0:
queue.append(i)
cnt += 1
if cnt != self.V:
print("exists a cycle in Test")
else :
print(t_order)
g = Test(6)
g.adeg(5, 2);
g.adeg(5, 0);
g.adeg(4, 0);
g.adeg(4, 1);
g.adeg(2, 3);
g.adeg(3, 1);
print("Sort of the given Test")
g.toposort()
the above code will run in only case when you import defaultdict in your local system also don't forget to write the import statements which are essential.