Graphs Flashcards
What is Bipartite graph ?
Whose vertices can be split into two independent groups U,V such that every edge connects between U and V
What is complete graph?
Where there is a unique edge between every pair of nodes.
Three ways of representing the graph?
- Adjacency Matrix
- Adjacency List
- Edge List
Which graph representation type is space efficient for
representing dense graphs?
Adjacency Matrix
Bridges in the graph?
A bridge/cut edge is any edge in a graph whose removal increases the number of connected components.
Articulation points in graph?
Articulation points/cut vertex is any node in the graph whose removal increases the number of connected components.
Time complexity of DFS on graph?
O(V+E) where V is number of vertices and E is the number of edges
Pseudo code for DFS on graphs?
# 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)
What is the time complexity of BFS on graph?
O(V+E)
V is number of vertices
E is the number of edges
Algorithm to find shortest path on unweighted directed/undirected graphs?
BFS(Breadth first search)
Pseudo code for BFS on graphs?
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;
What are Directed Acyclic Graphs?
DAGs are directed graphs with no cycles.
Which graph representation is space efficient for representing sparse graphs ?
Adjacency List
Pseudo-code for DFS on graph
# 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)
What is spanning tree?
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
What is a minimum spanning tree?
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.
What is topological sort algorithm?
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.
How to define tree ?
Graph with no cycle
Which algorithm we can use to detect cycle in graph?
- DFS
- Toplogical Sort
- Union Find
Tarjan’s strongly connected componets
How to detect cycle using depth first search in cyclic/acyclic graph?
- Create color array with three states .
I. white(not visited), II. Grey(currently visiting) and III. Black(not visited). - Mark all the nodes initially as white.
- 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)
What is the iterative version of DFS on the graph?
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.
