Graph

Question 1

Check if an undirected graph contains a cycle or not

Given a connected undirected graph, check if it contains any cycle or not. USEING BFS

Answer 1

When we do a Breadth–first search (BFS) from any vertex v in an undirected graph, we may encounter a cross-edge that points to a previously discovered vertex that is neither an ancestor nor a descendant of the current vertex. Each “cross edge” defines a cycle in an undirected graph. If the cross edge is x —> y, then since y is already discovered, we have a path from v to y (or from y to v since the graph is undirected), where v is the starting vertex of BFS. So, we can say that we have a path v ~~ x ~ y ~~ v that forms a cycle. (Here, ~~ represents one more edge in the path, and ~ represents a direct edge).

IN BFS, we receive, graph, src and parent
- make 2 queues —> visited = [False] * n , q-> empty q which q.append((src, -1))

then we do while q: popleft the first pair and for each u in graph.adjList() we shee wether u is checked or not, if we visited u and it is not parent we found the loop point.

code

from collections import deque

# A class to represent a graph object
class Graph:

    # Constructor
    def \_\_init\_\_(self, edges, n):

        # A list of lists to represent an adjacency list
        self.adjList = [[] for _ in range(n)]

    # add edges to the undirected graph
    for (src, dest) in edges:
        self.adjList[src].append(dest)
        self.adjList[dest].append(src)

# Perform BFS on the graph starting from vertex `src` and
# return true if a cycle is found in the graph
def BFS(graph, src, n):

    # to keep track of whether a vertex is discovered or not
    discovered = [False] * n

    # mark the source vertex as discovered
    discovered[src] = True

    # create a queue for doing BFS
    q = deque()

    # enqueue source vertex and its parent info
    q.append((src, -1))

    # loop till queue is empty
    while q:

        # dequeue front node and print it
        (v, parent) = q.popleft()

        # do for every edge (v, u)
        for u in graph.adjList[v]:
            if not discovered[u]:
                # mark it as discovered
                discovered[u] = True

                # construct the queue node containing info
                # about vertex and enqueue it
                q.append((u, v))

            # `u` is discovered, and `u` is not a parent
            elif u != parent:
                # we found a cross-edge, i.e., the cycle is found
                return True

    # no cross-edges were found in the graph
    return False

if __name__ == ‘__main__’:

# List of graph edges
edges = [
    (0, 1), (0, 2), (0, 3), (1, 4), (1, 5), (4, 8),
    (4, 9), (3, 6), (3, 7), (6, 10), (6, 11), (5, 9)
    # edge (5, 9) introduces a cycle in the graph
]

    # total number of nodes in the graph (0 to 11)
    n = 12

    # build a graph from the given edges
    graph = Graph(edges, n)

    # Perform BFS traversal in connected components of a graph
    if BFS(graph, 0, n):
        print('The graph contains a cycle')
    else:
        print('The graph doesn\'t contain any cycle')

Question 2

Check if an undirected graph contains a cycle or not

Given a connected undirected graph, check if it contains any cycle or not. USEING DFS

Answer 2

In DFS we sent the visited list to the function and update it in each iteration. 
DFS use the recursion. 
function received graph, v, discoverd, parent =-1

first we discover the v, then for its u, we do for loop an check each node (w) ,
if the node did not discovered we recur the DFS function for that node DFS(graph, w, discovered, v)
return True,
but if not discovered, and w!=parent: return True

The time complexity of the above solutions is O(V + E), where V and E are the total number of vertices and edges in the graph, respectively.

############## code
# Function to perform DFS traversal on the graph on a graph
def DFS(graph, v, discovered, parent=-1):

    # mark the current node as discovered
    discovered[v] = True

    # do for every edge (v, w)
    for w in graph.adjList[v]:

        # if `w` is not discovered
        if not discovered[w]:
            if DFS(graph, w, discovered, v):
                return True

        # if `w` is discovered, and `w` is not a parent
        elif w != parent:
            # we found a back-edge (cycle)
            return True

    # No back-edges were found in the graph
    return False

if __name__ == ‘__main__’:

# List of graph edges
edges = [
    (0, 1), (0, 6), (0, 7), (1, 2), (1, 5), (2, 3),
    (2, 4), (7, 8), (7, 11), (8, 9), (8, 10), (10, 11)
    # edge (10, 11) introduces a cycle in the graph
]

    # total number of nodes in the graph (0 to 11)
    n = 12

    # build a graph from the given edges
    graph = Graph(edges, n)

    # to keep track of whether a vertex is discovered or not
    discovered = [False] * n

    # Perform DFS traversal from the first vertex
    if DFS(graph, 0, discovered):
        print('The graph contains a cycle')
    else:
        print('The graph doesn\'t contain any cycle')

Question 3

Breadth-First Search (BFS) – Iterative

Answer 3

The non-recursive implementation of BFS is similar to the non-recursive implementation of DFS but differs from it in two ways:

It uses a queue instead of a stack.
It checks whether a vertex has been discovered before pushing the vertex rather than delaying this check until the vertex is dequeued.

The time complexity of BFS traversal is O(V + E), where V and E are the total number of vertices and edges in the graph, respectively. Please note that O(E) may vary between O(1) and O(V2), depending on how dense the graph is.

___________Code__________
from collections import deque

# A class to represent a graph object
class Graph:
    # Constructor
    def \_\_init\_\_(self, edges, n):

        # A list of lists to represent an adjacency list
        self.adjList = [[] for _ in range(n)]

    # add edges to the undirected graph
    for (src, dest) in edges:
        self.adjList[src].append(dest)
        self.adjList[dest].append(src)

# Perform BFS on the graph starting from vertex `v`
def BFS(graph, v, discovered):

    # create a queue for doing BFS
    q = deque()

    # mark the source vertex as discovered
    discovered[v] = True

    # enqueue source vertex
    q.append(v)

    # loop till queue is empty
    while q:

        # dequeue front node and print it
        v = q.popleft()
        print(v, end=' ')

        # do for every edge (v, u)
        for u in graph.adjList[v]:
            if not discovered[u]:
                # mark it as discovered and enqueue it
                discovered[u] = True
                q.append(u)

if __name__ == ‘__main__’:

# List of graph edges as per the above diagram
edges = [
    (1, 2), (1, 3), (1, 4), (2, 5), (2, 6), (5, 9),
    (5, 10), (4, 7), (4, 8), (7, 11), (7, 12)
    # vertex 0, 13, and 14 are single nodes
]

    # total number of nodes in the graph (labelled from 0 to 14)
    n = 15

    # build a graph from the given edges
    graph = Graph(edges, n)

    # to keep track of whether a vertex is discovered or not
    discovered = [False] * n

# Perform BFS traversal from all undiscovered nodes to
# cover all connected components of a graph
for i in range(n):
    if not discovered[i]:
        # start BFS traversal from vertex i
        BFS(graph, i, discovered)

Question 4

BFS applications

Answer 4

Applications of BFS
Copying garbage collection, Cheney’s algorithm.
Finding the shortest path between two nodes u and v, with path length measured by the total number of edges (an advantage over depth–first search).
Testing a graph for bipartiteness.
Minimum Spanning Tree for an unweighted graph.
Web crawler.
Finding nodes in any connected component of a graph.
Ford–Fulkerson method for computing the maximum flow in a flow network.
Serialization/Deserialization of a binary tree vs. serialization in sorted order allows the tree to be reconstructed efficiently.

Question 5

Depth First Search (DFS) – recursive

Answer 5

A Depth–first search (DFS) is a way of traversing graphs closely related to the preorder traversal of a tree. Following is the recursive implementation of preorder traversal:

procedure preorder(treeNode v)
{
    visit(v);
    for each child u of v
        preorder(u);
}

To turn this into a graph traversal algorithm, replace “child” with “neighbor”. But to prevent infinite loops, keep track of the vertices that are already discovered and not revisit them.

procedure dfs(vertex v)
{
    visit(v);
    for each neighbor u of v
        if u is undiscovered
            call dfs(u);
}
\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ code\_\_\_\_\_\_\_
# A class to represent a graph object
class Graph:
    # Constructor
    def \_\_init\_\_(self, edges, n):
        # A list of lists to represent an adjacency list
        self.adjList = [[] for _ in range(n)]

    # add edges to the undirected graph
    for (src, dest) in edges:
        self.adjList[src].append(dest)
        self.adjList[dest].append(src)

# Function to perform DFS traversal on the graph on a graph
def DFS(graph, v, discovered):

discovered[v] = True            # mark the current node as discovered
print(v, end=' ')               # print the current node

# do for every edge (v, u)
for u in graph.adjList[v]:
    if not discovered[u]:       # if `u` is not yet discovered
        DFS(graph, u, discovered)

if __name__ == ‘__main__’:

# List of graph edges as per the above diagram
edges = [
    # Notice that node 0 is unconnected
    (1, 2), (1, 7), (1, 8), (2, 3), (2, 6), (3, 4),
    (3, 5), (8, 9), (8, 12), (9, 10), (9, 11)
]

    # total number of nodes in the graph (labelled from 0 to 12)
    n = 13

    # build a graph from the given edges
    graph = Graph(edges, n)

    # to keep track of whether a vertex is discovered or not
    discovered = [False] * n

# Perform DFS traversal from all undiscovered nodes to
# cover all connected components of a graph
for i in range(n):
    if not discovered[i]:
        DFS(graph, i, discovered)

Question 6

Depth First Search iterative

Answer 6

he non-recursive implementation of DFS is similar to the non-recursive implementation of BFS but differs from it in two ways:

It uses a stack instead of a queue.
The DFS should mark discovered only after popping the vertex, not before pushing it.
It uses a reverse iterator instead of an iterator to produce the same results as recursive DFS.

dfs_iterative:
q -> stack
q.enque(v)
while q:
v = q.deque()
if discovered[v]: continue

discovered[v] = true
adjlist  = graph.adjList[v]
for i in reversed(range(len(adjlist))):
u = adjlist[i]
if not discovered[u] --> discovered[u] =true
stack.append(u)

______________________________
from collections import deque

# A class to represent a graph object
class Graph:
    # Constructor
    def \_\_init\_\_(self, edges, n):

        # A list of lists to represent an adjacency list
        self.adjList = [[] for _ in range(n)]

    # add edges to the undirected graph
    for (src, dest) in edges:
        self.adjList[src].append(dest)
        self.adjList[dest].append(src)

# Perform iterative DFS on graph starting from vertex `v`
def iterativeDFS(graph, v, discovered):

    # create a stack used to do iterative DFS
    stack = deque()

    # push the source node into the stack
    stack.append(v)

    # loop till stack is empty
    while stack:

        # Pop a vertex from the stack
        v = stack.pop()

        # if the vertex is already discovered yet, ignore it
        if discovered[v]:
            continue

        # we will reach here if the popped vertex `v` is not discovered yet;
        # print `v` and process its undiscovered adjacent nodes into the stack
        discovered[v] = True
        print(v, end=' ')

        # do for every edge (v, u)
        adjList = graph.adjList[v]
        for i in reversed(range(len(adjList))):
            u = adjList[i]
            if not discovered[u]:
                stack.append(u)

if __name__ == ‘__main__’:

# List of graph edges as per the above diagram
edges = [
    # Notice that node 0 is unconnected
    (1, 2), (1, 7), (1, 8), (2, 3), (2, 6), (3, 4),
    (3, 5), (8, 9), (8, 12), (9, 10), (9, 11)
    # (6, 9) introduces a cycle
]

    # total number of nodes in the graph (labelled from 0 to 12)
    n = 13

    # build a graph from the given edges
    graph = Graph(edges, n)

    # to keep track of whether a vertex is discovered or not
    discovered = [False] * n

# Do iterative DFS traversal from all undiscovered nodes to
# cover all connected components of a graph
for i in range(n):
    if not discovered[i]:
        iterativeDFS(graph, i, discovered)

Question 7

BFS recursive

Answer 7

Unlike DFS iterative wich receve graph nodeV and discovered list, it needs graph, queue, discovered
Note, the queue will be provided to the function by adding the first element in the testing phase

def BFS_recursive(graph, q, discovered)
checke we have q if not return
v =q.popleft()
#### do what you want here like printing
print(v)
for u in graph.adjList[v]:
    discover [u] =True of not
    q.append(u)
BFS_recursive(graph, q, discovered)

_______________Code__________
rom collections import deque

# A class to represent a graph object
class Graph:
    # Constructor
    def \_\_init\_\_(self, edges, n):

        # A list of lists to represent an adjacency list
        self.adjList = [[] for _ in range(n)]

    # add edges to the undirected graph
    for (src, dest) in edges:
        self.adjList[src].append(dest)
        self.adjList[dest].append(src)

# Perform BFS recursively on the graph
def recursiveBFS(graph, q, discovered):

if not q:
    return

    # dequeue front node and print it
    v = q.popleft()
    print(v, end=' ')

    # do for every edge (v, u)
    for u in graph.adjList[v]:
        if not discovered[u]:
            # mark it as discovered and enqueue it
            discovered[u] = True
            q.append(u)

recursiveBFS(graph, q, discovered)

if __name__ == ‘__main__’:

# List of graph edges as per the above diagram
edges = [
    (1, 2), (1, 3), (1, 4), (2, 5), (2, 6), (5, 9),
    (5, 10), (4, 7), (4, 8), (7, 11), (7, 12)
    # vertex 0, 13, and 14 are single nodes
]

    # total number of nodes in the graph (labelled from 0 to 14)
    n = 15

    # build a graph from the given edges
    graph = Graph(edges, n)

    # to keep track of whether a vertex is discovered or not
    discovered = [False] * n

    # create a queue for doing BFS
    q = deque()

    # Perform BFS traversal from all undiscovered nodes to
    # cover all connected components of a graph
    for i in range(n):
        if not discovered[i]:
            # mark the source vertex as discovered
            discovered[i] = True

            # enqueue source vertex
            q.append(i)

            # start BFS traversal from vertex i
            recursiveBFS(graph, q, discovered)

Question 8

what is Bipartite Graph?

what are the two direction in checking graph for being Bipartie?

Answer 8

A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V.
for every U and V, with every edge having one endpoint in set U and the other in set V.

It is possible to test whether a graph is bipartite or not using a Breadth–first search (BFS) algorithm. There are two ways to check for a bipartite graph:

1. A graph is a bipartite graph if and only if it is 2–colorable.

While doing BFS traversal, each node in the BFS tree is given its parent’s opposite color. If there exists an edge connecting the current vertex to a previously colored vertex with the same color, then we can safely conclude that the graph is not bipartite.

2. A graph is a bipartite graph if and only if it does not contain an odd cycle.

If a graph contains an odd cycle, we cannot divide the graph such that every adjacent vertex has a different color. To check if a given graph contains an odd-cycle or not, do a breadth–first search starting from an arbitrary vertex v. If in the BFS, we find an edge, both of whose endpoints are at the same level, then the graph is not Bipartite, and an odd-cycle is found. Here, the vertex level is its minimum distance from the starting vertex v. So, the odd-level vertices will form one set, and the even-level vertices will form another.

Question 9

Given an undirected graph, check if it is bipartite or not

Answer 9

we use BFS and checks if the graph contains an odd cycle or not.
for this checking along with a discovered list we have level list too.
in BFS algorithm, once we popleft the node from queue, for each u in its adjlist[v], we chack to case:
case 1: if u is not discovered:
discovered[u]=True
level[u] = level[v]+1

case 2: if u is discovered:
check if the level[u] == level[v]:
if yes, return False

The time complexity of the above solution is O(V + E), where V and E are the total number of vertices and edges in the graph, respectively. Please note that O(E) may vary between O(1) and O(V2), depending on how dense the graph is.

___________________ Code_____________
from collections import deque

# A class to represent a graph object
class Graph:

    # Constructor
    def \_\_init\_\_(self, edges=None, n=0):

        # Total number of nodes in the graph
        self.n = n

        # A list of lists to represent an adjacency list
        self.adjList = [[] for _ in range(n)]

        # add edges to the undirected graph
        for (src, dest) in edges:

            # add an edge from source to destination
            self.adjList[src].append(dest)

            # add an edge from destination to source
            self.adjList[dest].append(src)

# Perform BFS on a graph starting from vertex `v`
def isBipartite(graph):

    # start from any node as the graph is connected and undirected
    v = 0

    # to keep track of whether a vertex is discovered or not
    discovered = [False] * graph.n

    # stores the level of each vertex in BFS
    level = [None] * graph.n

    # mark the source vertex as discovered and set its level to 0
    discovered[v] = True
    level[v] = 0

    # create a queue to do BFS and enqueue source vertex
    q = deque()
    q.append(v)

    # loop till queue is empty
    while q:

        # dequeue front node and print it
        v = q.popleft()

        # do for every edge (v, u)
        for u in graph.adjList[v]:
            # if vertex `u` is explored for the first time
            if not discovered[u]:
                # mark it as discovered
                discovered[u] = True

                # set level one more than the level of the parent node
                level[u] = level[v] + 1

                # enqueue vertex
                q.append(u)

            # if the vertex has already been discovered and the
            # level of vertex `u` and `v` are the same, then the
            # graph contains an odd-cycle and is not bipartite
            elif level[v] == level[u]:
                return False

return True

if __name__ == ‘__main__’:

    # List of graph edges
    # Note that if we add edge (1, 3), the graph becomes non-bipartite
    edges = [(0, 1), (1, 2), (1, 7), (2, 3), (3, 5), (4, 6), (4, 8), (7, 8)]

    # total number of nodes in the graph (0 to 8)
    n = 9

    # build a graph from the given edges
    graph = Graph(edges, n)

    if isBipartite(graph):
        print('Graph is bipartite')
    else:
        print('Graph is not bipartite')

Question 10

Brook’s Theorem for graph coloring

Answer 10

Brooks’ theorem states that a connected graph can be colored with only x colors, where x is the maximum degree of any vertex in the graph except for complete graphs and graphs containing an odd length cycle, which requires x+1 colors.

Question 11

graph coloring set of questions

Answer 11

1) m coloring decision problem –> given a graph and a set of color –> Goal: find out if the graph can be colored using the provided set of colors
- —> out put: True or False

2) m coloring permutation probelm –> given a graph and a set of color —> Goal: find out # of ways to color the graph using the provided set of colors

3) m coloring optimization problem –> given a graph
Goal –> find out the # of colors requires to color the graph
it is an NP problem, we need to use greedy search algo. which guaranteed to have d+1 color where d is d.max.degree

Question 12

Given an undirected graph, check if it is k–colorable or not and print all possible configurations of assignment of colors to its vertices.

Answer 12

We can use backtracking to solve this problem. The idea is to try all possible combinations of colors for the first vertex in the graph and recursively explore the remaining vertices to check if they will lead to the solution or not. If the current configuration doesn’t result in a solution, backtrack. Note that we assign any color to a vertex only if its adjacent vertices share the different colors.

The time complexity of the above solution is exponential and requires additional space for the recursion (call stack).
________________Code__________________

# A class to represent a graph object
class Graph:
    # Constructor
    def \_\_init\_\_(self, edges, n):

        # A list of lists to represent an adjacency list
        self.adjList = [[] for _ in range(n)]

    # add edges to the undirected graph
    for (src, dest) in edges:
        self.adjList[src].append(dest)
        self.adjList[dest].append(src)

Function to check if it is safe to assign color c to vertex v
def isSafe(graph, color, v, c):
# check the color of every adjacent vertex of v
for u in graph.adjList[v]:
if color[u] == c:
return False
return True

def kColorable(g, color, k, v, n):

    # if all colors are assigned, print the solution
    if v == n:
        print([COLORS[color[v]] for v in range(n)])
        return

    # try all possible combinations of available colors
    for c in range(1, k + 1):
        # if it is safe to assign color `c` to vertex `v`
        if isSafe(g, color, v, c):
            # assign color `c` to vertex `v`
            color[v] = c

            # recur for the next vertex
            kColorable(g, color, k, v + 1, n)

            # backtrack
            color[v] = 0

if __name__ == ‘__main__’:

    # List of graph edges as per the above diagram
    edges = [(0, 1), (0, 4), (0, 5), (4, 5), (1, 4), (1, 3), (2, 3), (2, 4)]

# A list to store colors (can handle 10–colorable graph)
COLORS = ['', 'BLUE', 'GREEN', 'RED', 'YELLOW', 'ORANGE', 'PINK',
        'BLACK', 'BROWN', 'WHITE', 'PURPLE']

    # Set number of vertices in the graph
    n = 6

    # build a graph from the given edges
    g = Graph(edges, n)

k = 3

color = [None] * n

    # print all k–colorable configurations of the graph
    kColorable(g, color, k, 0, n)

Question 13

Given a Directed Acyclic Graph (DAG), print it in topological order using the topological sort algorithm. If the graph has more than one topological ordering, output any of them. Assume valid Directed Acyclic Graph (DAG).

Answer 13

Topological sort has two algorithm:
1) Kahan's Algo
2) modified DFS algo
Here we use modified Algo
Complexity: O(V+E)
result =[]
visited = [False]*n

topological_dfs(graph, v, result)
    make v as visited
    for each av of v
        if not visited
            topological_dfs(graph, v, result)

result.append(v)

--- Calling and runing function    
visited = [False]*n
for i in range(n):
    if not visited[i]:
        topological_dfs(graph, v, result)

print(result[::-1]) or print reversed result while using for loop

_________________ code______________

class Graph:

def \_\_init\_\_(self, edge, n ):

    self.n = n
    self.adjlist = [[] for i in range(n)]
    for src, dest in edge:
        self.adjlist[src].append(dest)

def Topological_sort_DFS(graph, v, visited, result):
# print(v)
visited[v] = True
for u in graph.adjlist[v]:
if not visited[u]:
Topological_sort_DFS(graph, u, visited, result)

result.append(v)
print(result)

if __name__ ==”__main__”:

    edge = [(0, 6), (1, 2), (1, 4), (1, 6), (3, 0), (3, 4), (5, 1), (7, 0), (7, 1)]
    n = 8
    result = []
    visited = [False]*n
    graph = Graph(edge,n)
    for i in range(n):
        if visited[i] == False:
            Topological_sort_DFS(graph, i, visited, result)

for elem in reversed(result):
    print(elem)
print(result)

Question 14

Given a directed acyclic graph (DAG), print it in Topological order using Kahn’s topological sort algorithm. If the DAG has more than one topological ordering, print any of them. If the graph is not DAG, report that as well.

Answer 14

for this algorithm we need indgree array. we define it once we define class for graph.

topological sort Kahan’s algorith queu = [] result =[] indegree =[0,0,0,0,0]
we find indegree of vertices throught the graph difinition
pick vertices with degree 0 to queue
while q!=empty: v = queue.pop() result.append(v) for each av in v:
indegree[av] -= 1
if indegree[av]==0:
queue.append(av)
if result.size()!= len(graph): graph ha cycle

from collections import deque
class Graph:
    indegree = None
    def \_\_init\_\_(self, edge, n):

    self. adjList = [[] for _ in range(n)]
    self. indegree = [0] * n

    for (src, dest) in edges:

        self. adjList[src].append(dest)
        self. indegree[dest] = self.indegree[dest]+1

def kahans_topological_sort(graph, n):

result = []

indegree = graph.indegree
print(indegree)
q = deque([i for i in range(n) if indegree[i]==0 ])

    while q:
        n = q.pop()
        result.append(n)
#         print(result)
        for m in graph.adjList[n]:

        indegree[m] = indegree[m]-1

        if indegree[m] == 0:
            print(m)
            print(q)
            q.append(m)

for i in range(n):
    if indegree[i]:
        return None

return result

if __name__ == “__main__”:

edge = [(0, 6), (1, 2), (1, 4), (1, 6), (3, 0), (3, 4), (5, 1), (7, 0), (7, 1)]
n = 8
graph = Graph(edge, n )

L = (kahans_topological_sort(graph, n))
if L:
    print(L)    # print topological order
else:
    print('Graph has at least one cycle. Topological sorting is not possible.')

Question 15

The transitive closure for a digraph G is a digraph G’ with an edge (i, j) corresponding to each directed path from i to j in G. The resultant digraph G’ representation in the form of the adjacency matrix is called the connectivity matrix

Answer 15

c = Metrix with n*n dimension

dfs(graph, v, c)

for u in adjlist[v]:
    if c[u][v]==0
        c[u][v]==1
        dfs(graph, v, c)

\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ code\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
# A class to represent a graph object
class Graph:
    def \_\_init\_\_(self, edges, n):

        # A list of lists to represent an adjacency list
        self.adjList = [[] for _ in range(n)]

    # add edges to the directed graph
    for (src, dest) in edges:
        self.adjList[src].append(dest)

# `C` is a connectivity matrix and stores transitive closure of a graph
# `root` is the topmost node in DFS tree (it is the starting vertex of DFS)
# `descendant` is current vertex to be explored in DFS.
# Invariant: A path already exists in the graph from `root` to `descendant`
def DFS(graph, C, root, descendant):

for child in graph.adjList[descendant]:
    # if `child` is an adjacent vertex of descendant, we have
    # found a path from root->child
    if C[root][child] == 0:
        C[root][child] = 1
        DFS(graph, C, root, child)

if __name__ == ‘__main__’:

    # List of graph edges as per the above diagram
    edges = [(0, 2), (1, 0), (3, 1)]

    # total number of nodes in the graph (labelled from 0 to 3)
    n = 4

    # build a graph from the given edges
    graph = Graph(edges, n)

    # `C` is a connectivity matrix and stores the transitive closure
    # of the graph. The value of `C[i][j]` is 1 only if a directed
    # path exists from vertex `i` to vertex `j`.
    C = [[0 for x in range(n)] for y in range(n)]

# consider each vertex and start DFS from it
for v in range(n):
    C[v][v] = 1
    DFS(graph, C, v, v)

        # print path info for vertex `v`
        print(C[v])

Question 16

Given a digraph (directed graph), find the total number of routes to reach the destination from a given source with exactly m edges.

Answer 16

We Use modified BFS traversal:
Usually, BFS doesn’t explore already discovered vertices again, but here we do the opposite. To cover all possible paths from source to destination, remove this check from BFS. But if the graph contains a cycle, removing this check will cause the program to go into an infinite loop. We can easily handle that if we don’t consider nodes having a BFS depth of more than m. Basically, we maintain two things in the BFS queue node:

The current vertex number.
The current depth of BFS (i.e., how far away from the current node is from the source?).
So, whenever the destination vertex is reached and BFS depth is equal to m, we update the result. The BFS will terminate when we have explored every path in the given graph or BFS depth exceeds m.

O(V+E)

out = count of totall number of routs –>int]
def FindTotallPath_BFS(graph, src, dest, m)
result= []
q
q.append(src, 0) # 0 is depth of BFS == how far the current node is away from the src

while q:
vertex,depth = q.popleft()

check if vertex == dest and depth = m:
    count +=1

if depth > m: 
    break
for every av in adjlist[v]:
    q.append(av, depth+1)

return count

_________________ code _____________

from collections import deque

# A class to represent a graph object
class Graph:
    # Constructor
    def \_\_init\_\_(self, edges, n):

        # A list of lists to represent an adjacency list
        self.adjList = [[] for _ in range(n)]

    # add edges to the directed graph
    for (src, dest) in edges:
        self.adjList[src].append(dest)

# Perform BFS on graph `graph` starting from vertex `v`
def findTotalPaths(graph, src, dest, m):

    # create a queue for doing BFS
    q = deque()

    # enqueue current vertex and the current depth of BFS
    # (how far away the current node is from the source)
    q.append((src, 0))

    # stores number of paths from source to destination having exactly `m` edges
    count = 0

    # loop till queue is empty
    while q:

        # dequeue front node
        vertex, depth = q.popleft()

        # if the destination is reached and BFS depth is equal to `m`, update count
        if vertex == dest and depth == m:
            count = count + 1

        # don't consider nodes having a BFS depth more than `m`.
        # This check will result in optimized code and handle cycles
        # in the graph (otherwise, the loop will never break)
        if depth > m:
            break

    # do for every adjacent vertex `u` of `v`
    for u in graph.adjList[vertex]:
        # enqueue every vertex (discovered or undiscovered)
        q.append((u, depth + 1))

    # return number of paths from source to destination
    return count

if __name__ == ‘__main__’:

# List of graph edges as per the above diagram
edges = [
    (0, 6), (0, 1), (1, 6), (1, 5), (1, 2), (2, 3), (3, 4),
    (5, 2), (5, 3), (5, 4), (6, 5), (7, 6), (7, 1)
]

    # total number of nodes in the graph
    n = 8

    # construct graph
    graph = Graph(edges, n)

src, dest = 0, 3
m = 4

    # Do modified BFS traversal from the source vertex src
    print(findTotalPaths(graph, src, dest, m))

Question 17

what is the back edge node?

what is it showing?

Answer 17

Back-edge is an edge from a vertex to one of its ancestors in the DFS tree.

When we do a Depth–first search (DFS) from any vertex v in an undirected graph, we may encounter a back-edge that points to one of the ancestors of the current vertex v in the DFS tree.

Each “back edge” defines a cycle in an undirected graph

Question 18

Given an undirected graph, check if it is a tree or not. In other words, check if a given undirected graph is an Acyclic Connected Graph or not.

Answer 18

we have to check two conditions: 1) cycle and 2) disconectivity.

for 1) we write a utilDFS. in a function we call utilDFS then check discovered array to chcek the connectivity

Discovered= [False, False, ..]

isTree:
istree = True

istree = DFSutil(graph, 0, discovered, parent=-1)

for i in range(n): # check connectivity using discovered

    if discovered[i]==False:

    return False

return is tree

DFSisTree:

The graph is a tree if it does not contain any cyrcle. 

A graph has backege in DFS traversal, if parent == u. 

     def DFS(graph, v, discovered, parent)
        discovered[v] = True
        for each u in adjlist[v]:
            if not discovered[u]:
                if not DFS(graph, u, discovered, v)
                    return False
            elif u!= parent:
                return False 

   return True

O(V+E)
____________________ Code_________________

# A class to represent a graph object
class Graph:
    # Constructor
    def \_\_init\_\_(self, edges, n):

        # A list of lists to represent an adjacency list
        self.adjList = [[] for _ in range(n)]

    # add edges to the undirected graph
    for (src, dest) in edges:
        self.adjList[src].append(dest)
        self.adjList[dest].append(src)

# Perform DFS on the graph and returns true if any back-edge
# is found in the graph
def DFS(graph, v, discovered, parent):

    # mark the current node as discovered
    discovered[v] = True

    # do for every edge (v, w)
    for w in graph.adjList[v]:

    # if `w` is not discovered
    if not discovered[w]:
        if not DFS(graph, w, discovered, v):
            return False

        # if `w` is discovered, and `w` is not a parent
        elif w != parent:
            # we found a back-edge (cycle)
            return False

    # no back-edges were found in the graph
    return True

# Check if the given undirected graph is a tree
def isTree(graph, n):

    # to keep track of whether a vertex is discovered or not
    discovered = [False] * n

    # flag to store if the graph is tree or not
    isTree = True

    # Perform DFS traversal from the first vertex
    isTree = DFS(graph, 0, discovered, -1)

    for i in range(n):
        # any undiscovered vertex means the graph is disconnected
        if not discovered[i]:
            return False

return isTree

if __name__ == ‘__main__’:

    # List of graph edges as per the above diagram.
    # Note edge (5, 0) introduces a cycle in the graph
    edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0)]

    # total number of nodes in the graph (0 to 5)
    n = 6

    # construct graph
    graph = Graph(edges, n)

    if isTree(graph, n):
        print('The graph is a tree')
    else:
        print('The graph is not a tree')

Question 19

1) What is 2-edge connected graph

2) what is Bridg or cut arc?

Answer 19

1) A graph is 2-edeg connected graph, if it remains connected whenever any edges are removed.
2) A bridge or cut arc is an edge whose removing of it increases the number of connected components, i.e an edge whose removal disconnected the graph.

Question 20

Given an undirected connected graph, check if the graph is 2–edge connected and return the bridges (if any).

Answer 20

we use modified timeDFS:

find the bridge

we modify the function that we had for DFSTime. in each iteration we find t = min(t, dfstime)

parent =-1
time =0
bridge =set()
arrival = [None]*n
visited = [False]*n

findDFSBridge(graph, v, visted,arrival, parent, time, bridge)
    time =time+1
    arrival[time] =time
    visited[v]
    t = arrivel[v]

for w in graph.adjlist[v]

    if not visited[w]

        t = min(t, findDFSBridge(graph, w, visted,arrival, v, time, bridge))

        elif w!=parent:
            ## cycle darim, backedge
            t = min(t, arrival[w])

if t==arrivel[w] and parrent ==-1:
     # if the value of `t` remains unchanged, i.e., it is equal
    # to the arrival time of vertex `v`, and if `v` is not the root node,
    # then (parent[v] —> v) forms a bridge
    brige.add((parent, v))

return t

_______________ Code________________

# A class to represent a graph object
class Graph:

    # Constructor
    def \_\_init\_\_(self, edges, n):
        # A list of lists to represent an adjacency list
        self.adjList = [[] for _ in range(n)]

    # add edges to the undirected graph
    for (src, dest) in edges:
        self.adjList[src].append(dest)
        self.adjList[dest].append(src)

# Perform DFS on the graph starting from vertex `v` and find
# all bridges in the process
def DFS(graph, v, visited, arrival, parent, time, bridges):
    # set the arrival time of vertex `v`
    time = time + 1
    arrival[v] = time

    # mark vertex as visited
    visited[v] = True

    # initialize `t` with the arrival time of vertex `v`
    t = arrival[v]

    # (v, w) forms an edge
    for w in graph.adjList[v]:

        # if `w` is not visited
        if not visited[w]:
            t = min(t, DFS(graph, w, visited, arrival, v, time, bridges))

        # if `w` is visited, and `w` is not a parent of `v`
        elif w != parent:
            # If vertex `w` is already visited, there
            # is a back edge starting from `v`. Note that as `visited[u]`
            # is already true, arrival[u] is already defined
            t = min(t, arrival[w])

# if the value of `t` remains unchanged, i.e., it is equal
# to the arrival time of vertex `v`, and if `v` is not the root node,
# then (parent[v] —> v) forms a bridge
if t == arrival[v] and parent != -1:
    bridges.add((parent, v))

    # return the minimum arrival time
    return t

def findBridges(graph, n):

    # to keep track of whether a vertex is visited or not
    visited = [False] * n

    # stores arrival time of a node in DFS
    arrival = [None] * n

start = 0
parent = -1
time = 0

bridges = set()

    # As the given graph is connected, DFS will cover every node
    DFS(graph, start, visited, arrival, parent, time, bridges)

return bridges

if __name__ == ‘__main__’:

    # (u, v) triplet represent undirected edge from vertex `u` to vertex `v`
    edges = [(0, 2), (1, 2), (2, 3), (2, 4), (3, 4), (3, 5)]

    # total number of nodes in the graph (0 to 6)
    n = 6

    # construct graph
    graph = Graph(edges, n)

    bridges = findBridges(graph, n)
    if bridges:
        print('Bridges are', bridges)
    else:
        print('Graph is 2–Edge Connected')

Question 21

what is 2–vertex connected ?

what is articulation point?

Answer 21

A connected graph G is said to be 2–vertex connected (or 2–connected) if it has more than 2 vertices and remains connected on the removal of any vertices. Any such vertex whose removal will disconnect the graph is called the Articulation point.

Question 22

Given a directed graph, check if it is a DAG (Directed Acyclic Graph) or not. A DAG is a digraph (directed graph) that contains no cycles.

Answer 22

For the directed graph, we need to consider departure time to find the cycle or back-edge.
you want to explore whether there is any u and v which u is a back-edge vertex
so using DFSTime, find the departure of each node, the only difference is that before updating incrementing time to time+1, we update departure[v] = time. then on the main function, we do
DFSTime(graph, v, visited, departure, time)
for v in range(n):
for u in the graph.adjlist[v]:

if departur[u ] < departure[v]:
    return False

O(V+E)
__________________ Code_____________

# A class to represent a graph object
class Graph:
    # Constructor
    def \_\_init\_\_(self, edges, n):

        # A list of lists to represent an adjacency list
        self.adjList = [[] for _ in range(n)]

    # add edges to the directed graph
    for (src, dest) in edges:
        self.adjList[src].append(dest)

# Perform DFS on the graph and set the departure time of all vertices of the graph
def DFS(graph, v, discovered, departure, time):

    # mark the current node as discovered
    discovered[v] = True

    # do for every edge (v, u)
    for u in graph.adjList[v]:
        # if `u` is not yet discovered
        if not discovered[u]:
            time = DFS(graph, u, discovered, departure, time)

    # ready to backtrack
    # set departure time of vertex `v`
    departure[v] = time
    time = time + 1

return time

# Returns true if the given directed graph is DAG
def isDAG(graph, n):

    # keep track of whether a vertex is discovered or not
    discovered = [False] * n

    # keep track of the departure time of a vertex in DFS
    departure = [None] * n

time = 0

    # Perform DFS traversal from all undiscovered vertices
    # to visit all connected components of a graph
    for i in range(n):
        if not discovered[i]:
            time = DFS(graph, i, discovered, departure, time)

    # check if the given directed graph is DAG or not
    for u in range(n):

        # check if (u, v) forms a back-edge.
        for v in graph.adjList[u]:

            # If the departure time of vertex `v` is greater than equal
            # to the departure time of `u`, they form a back edge.

            # Note that `departure[u]` will be equal to `departure[v]`
            # only if `u = v`, i.e., vertex contain an edge to itself
            if departure[u] <= departure[v]:
                return False

    # no back edges
    return True

if __name__ == ‘__main__’:

    # List of graph edges as per the above diagram
    edges = [(0, 1), (0, 3), (1, 2), (1, 3), (3, 2), (3, 4), (3, 0), (5, 6), (6, 3)]

    # total number of nodes in the graph (labelled from 0 to 6)
    n = 7

    # build a graph from the given edges
    graph = Graph(edges, n)

    # check if the given directed graph is DAG or not
    if isDAG(graph, n):
        print('The graph is a DAG')
    else:
        print('The graph is not a DAG')

Question 23

Given a chessboard, find the shortest distance (minimum number of steps) taken by a knight to reach a given destination from a given source.

Answer 23

it asks for shortest Path => BFS

but as we have coordinate in chest board, we need to assign coordinat on the nodes.
so we define a Node class with x, y, dist. also we rewrite \_\_hash\_\_ and \_\_eq\_\_ functions for the node

We also need row and column array for appropriate knite movement. Aks interveiwr if you do not know these

input: two pairs of coordinates

we need to have a function to validate the x and y –> is_valid(x,y,N)

then in the BFS_function(src, dest, N)

- we need a visited = set() 
- a queu
append src to queu

while q is not empty:
    node = queue.pop()

    find (x, y and dist) of node and save them in vars

    check if x == dest.x and y== dest.y
        return dist

    if node is not visited:

        visited.add(node)

        for i  in range(len(row)):

            first make x1 and y1:
            x1 = x + rw[i]
            y1 = y +col[i]

            if is_valid(x1,y1, dist+1)

                q.append(Node(x1,y1,dist+1) return inf if the path is not possible

O(M * N)

__________________ Code_______________

import sys
from collections import deque

# A queue node used in BFS
class Node:
    # (x, y) represents chessboard coordinates
    # `dist` represents its minimum distance from the source
    def \_\_init\_\_(self, x, y, dist=0):
        self.x = x
        self.y = y
        self.dist = dist

    # As we are using `Node` as a key in a dictionary,
    # we need to override the `\_\_hash\_\_()` and `\_\_eq\_\_()` function
    def \_\_hash\_\_(self):
        return hash((self.x, self.y, self.dist))

    def \_\_eq\_\_(self, other):
        return (self.x, self.y, self.dist) == (other.x, other.y, other.dist)

Below lists detail all eight possible movements for a knight
row = [2, 2, -2, -2, 1, 1, -1, -1]
col = [-1, 1, 1, -1, 2, -2, 2, -2]

# Check if (x, y) is valid chessboard coordinates.
# Note that a knight cannot go out of the chessboard
def isValid(x, y, N):
    return not (x < 0 or y < 0 or x >= N or y >= N)

# Find the minimum number of steps taken by the knight
# from the source to reach the destination using BFS
def findShortestDistance(src, dest, N):

    # set to check if the matrix cell is visited before or not
    visited = set()

    # create a queue and enqueue the first node
    q = deque()
    q.append(src)

    # loop till queue is empty
    while q:

        # dequeue front node and process it
        node = q.popleft()

    x = node.x
    y = node.y
    dist = node.dist

        # if the destination is reached, return distance
        if x == dest.x and y == dest.y:
            return dist

    # skip if the location is visited before
    if node not in visited:
        # mark the current node as visited
        visited.add(node)

            # check for all eight possible movements for a knight
            # and enqueue each valid movement
            for i in range(len(row)):
                # get the knight's valid position from the current position on
                # the chessboard and enqueue it with +1 distance
                x1 = x + row[i]
                y1 = y + col[i]

                if isValid(x1, y1, N):
                    q.append(Node(x1, y1, dist + 1))

    # return infinity if the path is not possible
    return sys.maxsize

if __name__ == ‘__main__’:

N = 8                # N x N matrix
src = Node(0, 7)    # source coordinates
dest = Node(7, 0)   # destination coordinates

print("The minimum number of steps required is",
      findShortestDistance(src, dest, N))

Question 24

Given a source vertex s from a set of vertices V in a weighted digraph where all its edge weights w(u, v) are non-negative, find the shortest path weights d(s, v) from source s for all vertices v present in the graph.

Answer 24

Need to modify BFS. instead of queue we use prior queue, min heap.

class Node to save weight and vertex, update “__le__” function

graph needs to be weighted

sefl.adjlist[source].append((dest, weight))

def getrout(prev, i, rout)

def findsortestPath(graph, sourcs, n):

1) q = []
2) dist = [inf]*n
3) visited = [False] * n
4) prev = [-1] * n

heappush(q, Node(src)) ##- src ra mizare tooye minheap

update dist for src =0 
visted src

while q is not empty:
    node = q.popleft()

    u = node.vertex

    for (v,weight) in graph.adjlist[u]:
        if not visited[v] and (dist[u]+weight ) < dist[v]:
            update dist --> dist[v] = dist[u]+weight
            update parent
            heappush(pq, Node(v, dist[v] ))

    visited[u] = True

rout = []

for i in range(n):

    if i!=sorce and dist[i] != sys.maxsize:
        get_rout

        print( source ,"-->", i, rout, dist[i])

Dijkstra’s algorithm runs in O(E.log(V)) time like Prim’s algorithm. Here, E is the total number of edges, and V is the graph’s number of vertices.

______________ Code_____________

import sys
from heapq import heappop, heappush

# A class to store a heap node
class Node:
    def \_\_init\_\_(self, vertex, weight=0):
        self.vertex = vertex
        self.weight = weight

    # Override the \_\_lt\_\_() function to make `Node` class work with a min-heap
    def \_\_lt\_\_(self, other):
        return self.weight < other.weight

# A class to represent a graph object
class Graph:
    def \_\_init\_\_(self, edges, n):
        # allocate memory for the adjacency list
        self.adjList = [[] for _ in range(n)]

    # add edges to the directed graph
    for (source, dest, weight) in edges:
        self.adjList[source].append((dest, weight))

def get_route(prev, i, route):
if i >= 0:
get_route(prev, prev[i], route)
route.append(i)

# Run Dijkstra’s algorithm on a given graph
def findShortestPaths(graph, source, n):

# create a min-heap and push source node having distance 0
pq = []
heappush(pq, Node(source))

    # set initial distance from the source to `v` as infinity
    dist = [sys.maxsize] * n

    # distance from the source to itself is zero
    dist[source] = 0

    # list to track vertices for which minimum cost is already found
    done = [False] * n
    done[source] = True

    # stores predecessor of a vertex (to a print path)
    prev = [-1] * n

    # run till min-heap is empty
    while pq:

    node = heappop(pq)      # Remove and return the best vertex
    u = node.vertex         # get the vertex number

    # do for each neighbor `v` of `u`
    for (v, weight) in graph.adjList[u]:
        if not done[v] and (dist[u] + weight) < dist[v]:        # Relaxation step
            dist[v] = dist[u] + weight
            prev[v] = u
            heappush(pq, Node(v, dist[v]))

        # mark vertex `u` as done so it will not get picked up again
        done[u] = True

route = []
for i in range(n):
    if i != source and dist[i] != sys.maxsize:
        get_route(prev, i, route)
        print(f'Path ({source} —> {i}): Minimum cost = {dist[i]}, Route = {route}')
        route.clear()

if __name__ == ‘__main__’:

# initialize edges as per the above diagram
# (u, v, w) represent edge from vertex `u` to vertex `v` having weight `w`
edges = [(0, 1, 10), (0, 4, 3), (1, 2, 2), (1, 4, 4), (2, 3, 9), (3, 2, 7),
        (4, 1, 1), (4, 2, 8), (4, 3, 2)]

    # total number of nodes in the graph (labelled from 0 to 4)
    n = 5

    # construct graph
    graph = Graph(edges, n)

    # run the Dijkstra’s algorithm from every node
    for source in range(n):
        findShortestPaths(graph, source, n)

Question 25

Given a directed graph, check if it is strongly connected or not. A directed graph is said to be strongly connected if every vertex is reachable from every other vertex.

Answer 25

A simple solution is to perform Depth–first search (DFS) or Breadth–first search (BFS) starting from every vertex in the graph. If each DFS/BFS call visits every other vertex in the graph, then the graph is strongly connected.

time complexity, The time complexity of the above solution is O(n × (n + m)), where n is the total number of vertices and m is the total number of edges in the graph.

write Simple dfs
in another function :
isStronglyConnected(graph, n):
       for i in range(n):
              visited =[False] * n
              DFS(graph, visited, i)