Question

You need to complete n courses in order to complete your degree. Some of these courses have prerequisites, for example: “course 1 has to be completed before course 3”. Your goal is to find an order to take all n courses and complete your degree.

Observe the following input file. The first line in the file has 2 numbers n and p where n is number of courses and p is the number of prerequisites.

Input:
5 3
1 2
3 1
4 5

The first line indicates that there are 5 courses numbered 1 to 5 and 3 prerequisites “1 should be taken before 2”, “3 should be taken before 1” and “4 should be taken before 5”
The output should an ordered list of the sequence of courses or “Not possible”. You can print any valid sequence. For the above example the output can be 3, 4 1, 2,5 or 4, 3, 1, 5, 2 etc…

Using topological sort (DFS or source removal) create a python algorithm.

Answer 1

• Below is the detailed implementation of the above problem in PYTHON with code and output shown.
• For better understanding please read the comments mentioned in the code.
• The basic idea of the algorithm is to see the courses as a set of nodes in a graph in which each edge i.e, an edge is a prerequisite course(say u) -> this course(say v) is seen as a directed edge and using topological sort to generate an order in which every node such that it is a prerequisite course(say node u) comes first in order than the this course(say node v). So for generating topological order we also have to check if cycle exists in graph or not as if cycle exists then there cannot be any topological order of the graph nodes.
• CODE:

#function which creates a topological order of the given nodes of a graph, if possible
def topo(node,graph,l):
#visit current node
vis[node]=1
#if node as some neighbor
if node in graph.keys():
#iterate through all neighbors
for neighbor in graph[node]:
#if unvisited
if vis[neighbor]==0:
#call topo() recursively for this node
topo(neighbor,graph,l)
#after exploring all the subtree of node add it to list
l.append(node)
  
#driver code

#input n and p
n,p=list(map(int,input().split()))
#dictionary t store graph
graph={}
#take input all edges
for i in range(p):
#u->v is a directed edge
u,v=list(map(int,input().split()))
#if u exists in dict then add v to keys of it
if u in graph.keys():
graph[u].append(v);
#otherwise create a new list with v as it's only element
else:
graph[u]=[v]
  
#list to store the topological order of nodes
order=[]
#create a visited list to check if a node is visited or not, initially all unvisited
vis=[False]*(n+1)
#for every unvisited node call topo()
for i in range(1,n+1):
if vis[i]==0:
topo(i,graph,order)
#reverse order list to get the actual topological sort
order=order[::-1]

#now to check of the cycle exists in the graph or not, if cycle exist then topological sort not possible
#create a dict to store the order of nodes in topological order we got i.e, order
store={}
#store each node with their indices in order list
for ind,ele in enumerate(order):
store[ele]=ind
  
#initially set cycle to false
cycle=False
#for each node from 1 to n
for i in range(1,n+1):
#if node has neighbors
if i in graph.keys():
#for each neighbor
for nodes in graph[i]:
#if index of neighbor(or child) is less than that of parent then cycle exists
if store[nodes]<store[i]:
#matk cycle as true and break
cycle=True
break
#if cycle true the break from loop
if cycle==True:
break
#if cycle exists in graph then topological order not possible
if cycle==True:
print("Not possible")
#otherwise print the order
else:
print(*order)

• INPUT/OUTPUT:

1. 5 3
   1 2
   3 1
   4 5
   4 5 3 1 2

2. 4 6
   1 2
   1 3
   2 3
   3 1
   3 4
   4 4
   Not possible

• Below are the screenshot attached for the code and input/output for better clarity and understanding.

CODE

INPUT/OUTPUT

So if you still have any doubt regarding this solution please feel free to ask it in the comment section below and if it is helpful then please upvote this solution, THANK YOU.