Given directed, unweighted, and simple (not multi-graph) Graph G as G = (V;E) wi

Question

Given directed, unweighted, and simple (not multi-graph) Graph G as G = (V;E) with jV j < 50,
do the followings:
1. Assume vertices are labeled with numbers from 1 to jV j < 50

Write a function to check if G is a DAG. Call it check dag.

if G is a DAG. If G is DAG then you will print the topological
order (vertex labels in the topological order), as in the figure 2c and exit. If any two vertices are
at the same rank, prefer the one with the smallest label number.

Can you help me to implement it. It requires basically Depth First Search algorithm yet, all I implement so far misunderstands the multiple parent situation with cycle.

Explanation / Answer

class DAG:
def __init__(self,vertices_):
self.graph = defaultdict(list)
self.V = vertices_

def addEdge(self,u,v):
self.graph[u].append(v)
  
def topologicalSortUtil(self,v,visited,stack):
visited[v] = True
for i in self.graph[v]:
if visited[i] == False:
self.topologicalSortUtil(i,visited,stack)
stack.insert(0,v)
def topologicalSort(self):
visited = [False]*self.V
stack =[]
for i in range(self.V):
if visited[i] == False:
self.topologicalSortUtil(i,visited,stack)
print stack

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.