Graph Search
Introduction
Graph search is an incredibly powerful yet expensive algorithm. We can choose to search by breadth first or by depth first.
Breadth First Search (BFS)
BFS is naturally associated with queue. Visiting a node would be offering it to the queue. And polling it out of the queue to do level search.
Types of Questions
BFS on Binary Tree
Level Order Traversal (separated by level, so an extra for loop on the size)
Store all nodes in the level order. The queue works as an ArrayList
BFS on Graph
Traverse graph (clone graph, search graph nodes), need to check cycle
Topological Sort (Course Schedule, Alien Dictionary, etc)
BFS on 2D Array
Put an index in the queue the keep searching (number of islands, N-queen)
Shortest Path in a Simple Graph
Edges are bidirectional and the edge weight is 1.
Time Complexity
O(V+E)
References
Depth First Search (DFS)
DFS is usually implemented via stack or by recursion (via the call stack). Depth-first is naturally associated with stack, going down would be pushing into the stack and backtracking would be popping out from the stack.
Find one or all valid paths
Recursive vs iterative visiting order
"These two variations of DFS visit the neighbors of each vertex in the opposite order from each other: the first neighbor of v visited by the recursive variation is the first one in the list of adjacent edges, while in the iterative variation the first visited neighbor is the last one in the list of adjacent edges. The recursive implementation will visit the nodes from the example graph in the following order: A, B, D, F, E, C, G. The non-recursive implementation will visit the nodes as: A, E, F, B, D, C, G."
Last updated