graphs_class

Question 1

What are standard steps to address any graph problem in general?

Answer 1

Build a Graph
Write BFS/DFS
Outer loop to run as many BFS/DFS to explore graph

Question 2

Given list of edge representations (src, dest), how do we build the Adjacency List representation for given undirected Graph

Answer 2

For each (src, dest) element within the edge list, we need to perform following two operations
adj_list[src].append(dest)
adj_list[dest].append(src)

Question 3

Given list of edge representations (src, dest), how do we build the Adjacency List representation for given directed Graph

Answer 3

For each (src, dest) element within the edge list, we need to perform following operation
adj_list[src].append(dest)

Question 4

Three requirements/steps to build a graph

Answer 4

Need to know vertices of the graph
Build adjacency list for given list of edges using
for each (src, dest) in edges:
adj_list[src].append(dest)
adj_list[dest].append(src)
and
Initialize visited array with blank/null values

Question 5

Why is it preferred to represent vertices in convenient Id format 0 to n-1

Answer 5

That would help us using array & use index as the vertex Id, which will eventually enable us to retrieve it’s neighbors in constant time O(1)

Question 6

Basic BFS template for Graphs

Answer 6

def bfs(source):
    queue = deque()
    queue.append(source)
    visited[source] = 1

while not queue:
      node = queue.popleft()
      for neighbor in adj_list[node]:
            if visited[neighbor] == 0:
                visited[neighbor] = 1
                queue.append(neighbor)

Question 7

Basic DFS template for Graphs

Answer 7

def dfs(source):
    visited[source] = 1
    for neighbor in adj_list[source]:
         if visited[neighbor] == 0:
            dfs(neighbor)

Question 8

DFS tree from graph produces of which type of edges

Answer 8

DFS tree from graph produces tree edges and back edges.

Question 9

BFS tree from graph produces of which type of edges

Answer 9

BFS tree from graph produces tree edges and cross edges

Question 10

Types of Edges in graphs

Answer 10

Tree Edge
Forward Edge
Backward Edge
Cross Edge

Question 11

Outer loop code/logic for graph BFS/DFS traversal

Answer 11

components = 0
for v in 0 to n-1:
    if visited[v] == -1:
        components ++
        dfs/bfs(v)
return components

Question 12

Outer loop code/logic for graph BFS/DFS traversal

Answer 12

components = 0
for v in 0 to n-1:
    if visited[v] == -1:
        components ++
        dfs/bfs(v)
return components

Question 13

Sum of degrees of all nodes in an undirected graph

Answer 13

twice the number of edges

Question 14

BFS time complexity on Graphs

Answer 14

O(m+n) where

O(n) - Push and pop of each vertex from Queue
O(m) - Looking at adjacency list of each vertex

Question 15

Sum of degrees of all nodes in an undirected graph

Answer 15

twice the number of edges

Question 16

BFS space complexity on Graphs

Answer 16

Auxiliary space: O(n) - number of vertices in queue if source vertex connected to all remaining vertices in worst case
Actual Space: O(n + m)
O(n) - to save vertices information
O(m) - to save edges information

Question 17

DFS time complexity on Graphs

Answer 17

O(m+n) where

O(n) - Push and pop out of active stack frame for each vertex
O(m) - Looking at adjacency list of each vertex

Question 18

BFS space complexity on Graphs

Answer 18

Auxiliary space: O(n) - number of vertices in queue if source vertex connected to all remaining vertices in worst case
Actual Space: O(n + m)
O(n) - to save vertices information
O(m) - to save edges information

Question 19

DFS time complexity on Graphs

Answer 19

O(m+n) where

O(n) - Push and pop out of active stack frame for each vertex
O(m) - Looking at adjacency list of each vertex

Question 20

DFS space complexity on Graphs

Answer 20

Auxiliary space: O(n) - number of active stack frame entries is height of the tree, which can be O(n) in worst case
Actual Space: O(n + m)
O(n) - to save vertices information
O(m) - to save edges information

Question 21

When Graph is valid Tree?

Answer 21

If all vertices are connected with no cycles in it

Question 22

BFS function to detect if there is a cycle or not

Answer 22

def bfs_has_cycle(source):
    queue = deque()
    queue.append(source)
    visited[source] = 1
    parent[source] = None

    while queue:
       node = queue.popleft()
       for neighbor in adj_list[node]:
           if visited[neighbor]  == 0:
                visited[neighbor] = 1
                parent[neighbor] = node
                queue.append(neighbor)
           else: # if visited node
                if neighbor !=parent[node]: # here check if neighbor is not our own parent
                     return True # This is cross edge

return False

Question 23

If there is a cross edge in a tree, can we conclude graph has cycle?

Answer 23

Yes

Question 24

DFS function to detect if there is a cycle or not

Answer 24

def dfs_has_cycle(node):
visited[node] = 1
for neighbor in adj_list[node]:
if visited[neighbor] == 0:
parent[neighbor] = node
if dfs_has_cycle(neighbor):
return True
else: # if visited node
if neighbor != parent[node]: # here check if neighbor is not our own parent
return True # This is back edge
return False

Question 25

If there is a cross edge in a tree, can we conclude graph has cycle?

Answer 25

Yes

Question 26

What type of edge will be created when DFS detects cycle

Answer 26

Back Edge

Question 27

In short how do we find if there is a cross edge or back edge

Answer 27

If the neighbor vertex is visited and it is not equal to the current vertex parent, we can conclude that graph has cycle.

If we use DFS to traverse the graph there will be Back Edges, where as if we use BFS there will be Cross Edges.

Question 28

What is Bipartite Graph?

Answer 28

A Graph is Bipartite if we can split it’s set of nodes into two independent subsets A and B. such that every edge of the graph has one node in A and other node in B.

Question 29

If there are two nodes, without any edges - Is that graph bipartite?

Answer 29

Yes. As far as we can put both nodes into two different subsets and no edge connecting to 2 vertices in same sub set, it is bipartite.

Question 30

What is Bipartite Graph?

Answer 30

A Graph is Bipartite if we can split it’s set of nodes into two independent subsets A and B. such that every edge of the graph has one node in A and other node in B.

Question 31

If there are two nodes, without any edges - Is that graph bipartite?

Answer 31

Yes. As far as we can put both nodes into two different subsets and no edge connecting to 2 vertices in same sub set, it is bipartite.

Question 32

Can we say graph is bipartite if there are cycles?

Answer 32

No. there is no relation between both of those characteristics of graph

Question 33

If there is a cycle of odd length, is graph bipartite?

Answer 33

No

Question 34

Can I tree bipartite? (Which means graph does not have a cycle?

Answer 34

Yes. Every alternate level in tree can be in each subset

Question 35

Can a BFS/DFS tree give information about whether a tree is bipartite or not?

Answer 35

Yes.

Question 36

The graph is a bipartite graph if:(Using disjoint sets technique)

Answer 36

1) The vertex set of can be partitioned into two disjoint and independent sets.
2) All the edges from the edge set have one endpoint vertex from the set and another endpoint vertex from the set.

Question 37

The graph is a bipartite graph if: (Using coloring technique)

Answer 37

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.

Question 38

If there are multiple cycles in BFS, with one or more even edge length - Is graph bipartite?

Answer 38

Yes

Question 39

If there are multiple cycles in BFS, with one or more odd edge length - Is graph bipartite?

Answer 39

No

Question 40

BFS function to detect if connection component is bipartite

Answer 40

write code

Question 41

DFS function to detect if connection component is bipartite

Answer 41

def dfs_is_bipartite(node):
      visited[node] = 1
      for neighbor in adj_list[node]:
           if visited[neighbor] == 0:
               visited[neighbor] = 1
               color[neighbor] = color (toggling)
               if not dfs_is_bipartite(neighbor):
                    return False
           else:
               if color of neighbor == color of node:
                     return False
       return True   

   (To be tested and filled complete code here)

Question 42

When you have set of inputs and set of pair wise relationships, what category of problem could it be?

Answer 42

Graphs