Graphs

Question 1

basic graph terms
- G
- order(G)
- size(G)
- degree of a vertex
- edge e
- undirected graph
- directed graph
- simple graph
- non-simple graph
- cyclic graph
- acyclic graph

Answer 1

• G = (V,E)
• order(G) = |V|
• size(G) = |E|
• edge e = (u, v), where u, v are vertices

Question 2

3 graph representations

Answer 2

• adjacency list
• adjacency matrix
• edge list

Question 3

how does graph dfs work

Answer 3

• idea: traverse from a vertex as deep as it can before it searches other vertex, done by recursion
• implementation
  1. have a global state variable that stores all visited vertex set
  2. starting with the first vertex, loop through all of its edges, for every one of which call the subroutine if it’s not yet in the visited vertex set
• time complexity: O(|V| + |E|) since we have to go through every edge and every vertex

Question 4

how does graph bfs work

Answer 4

• idea: traverse all the vertices one edge away from the current vertex before it goes to any further levels
• implementation
  1. prepare a visited set, a queue
  2. push the first vertex into the queue and into VS as well
  3. start outer loop until the queue is empty
  3.1 pop queue
  3.2 iterate all adjacent vertices of this popped vertex
  3.2.1 mark all unvisited vertex visited and enqueue
• time complexity: O(|V| + |E|)

Question 5

how does Dijkstra work

Answer 5

• idea: use BFS to find the shortest path from one level to the next one while ensuring every vertex is visited, which altogether makes up the shortest path to traverse all the vertices in a graph
• implementation
  1. prepare a distance hashmap that maps a vertex to the cumulative distance up to this vertex
  2. prepare a priority queue that stores an adjacent vertex along with the cumulative length up to the adjacent vertex
  3. prepare a visited set
  4. enqueue (starting vertex, 0) into PQ
  5. start the outer loop until all vertices visited
  5.1 pop out PQ which will give the next vertex to be
  visited along with its edge length from current vertex
  5.2 update distance hashmap to this popped vertex
  5.3 for every adjacent vertex of this popped vertex
  5.3.1 if not visited, enqueue itself with its cumulative
  length to the PQ and mark it as visited
• time complexity: since PQ could potentially contain all the edges which is |E|, and for every iteration we need to enqueue and dequeue, each of which takes O(logn) in the worst cae, so it’d be O(|E|log|E|)

Question 5

what’s MST

Answer 5

a subset of the edges of a connected, edge-weighted graph that connects all the vertices together without any cycles and with the minimum possible total edge weight

Question 6

how does Prim’s algo work for finding MST

Answer 6

• idea: similar to Dijkstra’s algo, we make use of priority queue to find the local shortest edge between two levels, and we add that shortest edge to MST set
• implementation: similar to Dijsktra’s algo
• efficiency: O(|E|log|E|)

Question 7

how does Kruskal’s algo work for finding MST

Answer 7

• idea: add every edge of the graph into a priority queue, and while the queue is not empty and the MST size is not reached, dequeue an edge from the priority queue. If the dequeued edge does not form a cycle, then add the edge to the MST
• implementation
• efficiency: O(|E|log|E|)