Graphs

Question 1

What is Bipartite graph ?

Answer 1

Whose vertices can be split into two independent groups U,V such that every edge connects between U and V

Question 2

What is complete graph?

Answer 2

Where there is a unique edge between every pair of nodes.

Question 3

Three ways of representing the graph?

Answer 3

1. Adjacency Matrix
2. Adjacency List
3. Edge List

Question 4

Which graph representation type is space efficient for

representing dense graphs?

Answer 4

Adjacency Matrix

Question 5

Bridges in the graph?

Answer 5

A bridge/cut edge is any edge in a graph whose removal increases the number of connected components.

Question 6

Articulation points in graph?

Answer 6

Articulation points/cut vertex is any node in the graph whose removal increases the number of connected components.

Question 7

Time complexity of DFS on graph?

Answer 7

O(V+E) where V is number of vertices and E is the number of edges

Question 8

Pseudo code for DFS on graphs?

Answer 8

# Global or class scope variables
n=number of nodes in the graph
g=adjacency list representation of graph
visited=[false,.....false]# size n

function dfs(at):
if visited[at]: return;
visited[at]=true;
neighbors=graph[at]
for next in neighbors:
    dfs(next)

# start DFS at node zero 
start_node=0;
dfs(start_node)

Question 9

What is the time complexity of BFS on graph?

Answer 9

O(V+E)
V is number of vertices
E is the number of edges

Question 10

Algorithm to find shortest path on unweighted directed/undirected graphs?

Answer 10

BFS(Breadth first search)

Question 11

Pseudo code for BFS on graphs?

Answer 11

function BFS(s)
q=queue data structure with enqueue and dequeue
q.enqueue(s)

visited=[false,.....,false] # size n
visited[s]=true;
while !q.IsEmpty():
node=q.dequeue();
neighbors=g.get(node)

for(next: neighbors):
if !visited[next]:
q.Enqueue(next)
visited[next]=true;

Question 12

What are Directed Acyclic Graphs?

Answer 12

DAGs are directed graphs with no cycles.

Question 13

Which graph representation is space efficient for representing sparse graphs ?

Answer 13

Adjacency List

Question 14

Pseudo-code for DFS on graph

Answer 14

# Global or class scope variables
n = number of nodes in the graph
g = adjacency list representing graph
visited = [false, …, false] # size n
function dfs(at):
if visited[at]: return
visited[at] = true
neighbours = graph[at]
for next in neighbours:
dfs(next)
# Start DFS at node zero
start_node = 0
dfs(start_node)

Question 15

What is spanning tree?

Answer 15

https://www.ics.uci.edu/~eppstein/161/960206.html
A spanning tree of a graph is just a subgraph that contains all the vertices and is a tree. A graph may have many spanning trees; for instance the complete graph on four vertices

Question 16

What is a minimum spanning tree?

Answer 16

https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/

A minimum spanning tree (MST) or minimum weight spanning tree for a weighted, connected and undirected graph is a spanning tree with weight less than or equal to the weight of every other spanning tree.

Question 17

What is topological sort algorithm?

Answer 17

https://www.interviewcake.com/concept/java/topological-sort
The topological sort algorithm takes a directed acyclic graph and returns an array of the nodes where each node appears before all the nodes it points to.

Question 18

How to define tree ?

Answer 18

Graph with no cycle

Question 19

Which algorithm we can use to detect cycle in graph?

Answer 19

1. DFS
2. Toplogical Sort
3. Union Find
   Tarjan’s strongly connected componets

Question 20

How to detect cycle using depth first search in cyclic/acyclic graph?

Answer 20

1. Create color array with three states .
   I. white(not visited), II. Grey(currently visiting) and III. Black(not visited).
2. Mark all the nodes initially as white.
3. Do DFS
   Mark current node as grey
   Iterate the neighbors
   if we encounter neighbor with grey color,
   we detect cycle
   else recursively call DFS on neighbors
   After processing all the neighbors , we mark node as
   black(visited)

Question 21

What is the iterative version of DFS on the graph?

Answer 21

https: //medium.com/leetcode-patterns/leetcode-pattern-1-bfs-dfs-25-of-the-problems-part-1-519450a84353
1. Initialize node with the stack
2. Pop the current node from stack
3. Mark the current node as visited
4. retrieve all current unvisited neighbors and push them to stack
5. Push all of them to the stack.