Time  algorithm average that decides if there is a cycle in G containing edge e.

Question

a) Let G be an undirected graph with n vertices and m edges, and let e be an edge in G. Give an O(n+m)-time algorithm that decides if there is a cycle in G containing edge e.

b) Let G be a directed acyclic graph (DAG) with n vertices and m edges. Give an O(n+m)-time algorithm that takes as input an ordering of the n vertices of G, and checks whether or not this ordering is a topological sorting for G.

Summary

1. In question-a, an algorithm is created that returns true if a cycle exists in graph G and false otherwise.
2. This algorithm has a time complexity of O(V + E).
3. In question-b, a method for topological sorting is written.
4. This algorithm has a time complexity of O(V + E).

Explanation

a) Algorithm to detect the cycle in graph G with the time complexity of O(n+m).

function is_cyclic()
    let V be the number of vertices
    Allocate memory for an array point visited of size V 
    for every i form 0 to V:
        set visited[i] to false 
    
    for every u from 0 to V
        if visited[u] is false
            if is_cyclic_util(u, visited, -1) is true 
                return true 
    return false 
    
    
function is_cyclic_util(v, visited[], parent)
    set visited[v] to true 
    
    Allocate memory for adjacency list adj[]
    
    for every i from first to last element of adj[]
        if visited[i] is false 
            if is_cyclic_util(i, visited, v) is true 
                return true 
            
            else if i is not parent 
                return true 
    return false

The time complexity of the above algorithm: O(V+E)

b) Algorithm for topological sort with the time complexity of O(V + E):

function topological_sort() 
    Let V be the number of vertices 
    Allocate memory for stack 
    Allocate memory for visited[] of size V
    for every i from 0 to V 
        set visited[i] to false 
    
    for every i from 0 to V 
        if visited[i] is false 
            Call the function topological_sort_util(i, visited, stack)
            
    Print the contents of the stack
    
    
function topological_sort_util(v, visited[], stack)
    set visited[v] to true 
    
    Let adj[] be the adjacency list
    
    for every element i from first to last of the adjacency list 
        if visited[i] is false 
            Call the function topological_sort_util(i, visited, stack)
            
    Push the element v into the stack 
            

The time complexity of the above algorithm is O(V + E).

Also, read check the python code below that doesn’t work properly, adjust it, and explain?