Graph

Question 1

Graph Types

Answer 1

Undirected
Directed
- Directed Acyclic Graph ( DAG)

Question 2

Graph Data structure

Answer 2

Adjacency Matrix
- M/N array - ‘1’ represents edge between 2 vertices i and j.
Adjacency List
- Array of List holding edges for each vertex.

Question 3

Graph Algorithms

Answer 3

BFS
DFS
Union-Find
Single Source Shortest Path
   - Dijkstras 
   - Bellman Ford
All pair shortest path
   -  Floyd Warshall
 Minimum Spanning Tree
  - Prim's
  - Kruskals
Topological Sorting
BackTracking

Question 4

BFS

Answer 4

• Use Queues to traverse the graph.

Question 5

DFS

Answer 5

• Recursion stack

Question 6

Disjoint Sets

Answer 6

• To find cycle in an undirected graph.
  Use Find and Union to find and detect the cycle.
• Prim’s and Kruskal algorithms use disjoint sets to detect the cycle.

Find: finds a vertex in a set.
Union: merges set s1 and set s2, if U and V are belongs to S1/S2.

if both vertices are in same set, then there is a cycle.

Array Representation of disjoint sets:

Initialize array with -1 for all vertices. As we find edge between vertices, change its value to parent and parent edge being negative number(represents number of nodes). If vertices parent are different, merge using union. Make one set parent of other set and change the number of elements.

Weighted Union (Union by Rank):
In union, select the parent based on the number of elements and there will be a hierarchy of underlying children and its parents.
set1: { 1, 2} s2: {3, 4}
-1 3-> 1 -> -1.
Collapsing Find:
Here we can make all children point directly to main parent. This makes constant time to find the direct parent of any child.

Question 7

Minimum Cost Spanning Trees

Answer 7

Spanning tree - is a subset of a graph where all vertices are connected and does not form a cycle.
Given V vertices and E edges,
Spanning tree will have V vertices and V-1 edges.

Minimum cost spanning tree - in weighted graph subset of a graph with minimum cost ( no cycles).
Algorithms:
Kruskal
Prims

Question 8

Prim’s and Kruskal ( Greedy approach)

Answer 8

Prim’s Algorithm:
Select minimum cost edge and from the selected edge continue selecting the minimum cost edge. Next minimum edge should be always selected from already selected vertex.

Time complexity: O(n 2)
N- no. of vertices
N - no.o f edges.

Kruskals’s Algorithm:
Select the minimum edge even though if it is not connected. Select the edge if it is not forming a cycle.
- Min Heap can be used to select the edge.
Kruskal’s algo works for non-connected graphs also. But it may not provide the spanning tree.

Complexity: O(n * logn)
Log n to select the edge using min heap; n - no of vertices.

Question 9

Cycle Detection - (Undirected Graph)

Answer 9

Union-Find Algorithm
BFS
DFS

Question 10

Cycle Detection - (Directed Graph)

Answer 10

Using indegrees/outdegrees of Vertex
BFS
DFS

Question 11

Find Connected components ( Directed Graph)

Answer 11

Kosaraju’s Algorithm

Tarjan’s Algorithm

Question 12

Topological Sorting

Answer 12

Given a directed (Acyclic) graph - edge between vertices U-> V represents edge U must be processed/visited before proceeding to Vertex V.
Topological sorting is useful in task scheduling with prerequisites.

Algorithms:
Kahn’s Algorithm
DFS

Question 13

Kahn’s Algorithm

Answer 13

In-degree - Vertex with incoming edges
Out-Degree - Vertex with outgoing edges.

1. Start with vertex having no incoming edges. (also called source)
2. Add current source vertex to result list.
3. visit all of its outgoing vertices and add it to queue.
4. Decrement in-degree of child