Direct BFS Applications Bipartite Check Direct DFS Applications Strongly Connected Components Kosaraju’s Algortihm Directed Acyclic Graph Topological Sort Minimum Spanning Tree Kruskal’s Algorithm Prim’s Algorithm Borůvka’s Algorithm Single Source Shortest Path Algorithm Dijkstra’s algorithm Bellman-Ford All Sources Shortest Path Floyd-Warshall Stable Matching Gale-Shapley Algorithm Max-Flow Ford-Fulkerson Maximum Bipartite Matching
pred[1...n] = [null, null, ..., null] state[1...n] = [unseen, unseen, ..., unseen] dist[1...n] = [infty, infty, ..., infty] def BFS(V[1..n], adjlist[1..n], start: # Initialize stuff for the start q = new queue state[start] = seen dist[start] = 0 q.enqueue(start) # Do the actual BFS while q is not empty: u = q.dequeue() for v in adjlist[u]: if state[v] == unseen: pred[v] = u state[v] = seen dist[v] = dist[u] + 1 q....
pred[1...n] = [null, null, ..., null] state[1...n] = [unseen, unseen, ..., unseen] disc[1...n] = [0, 0, ..., 0] fin[1...n] = [0, 0, ..., 0] time = 0 def FullDFS(adjlist[1...n]): for v in 1..m: if state[v] == unseen: DFS(adjlist, v) def DFS(adjlist[1..n], v): # Update time and set discover time state[v] = seen time = time + 1 disc[v] = time # Process everything else for each w in adjlist[v]: if state[w] == unseen: pred[w] = v DFS(adjlist, w) # Update time and set finishing time state[v] = complete time = time + 1 fin[v] = time