When to use dfs? Generally speaking, there are several situations as follows: Combination Sample answer: combination sum2 Key Point: 1) sorting before dfs 2) use Index to help remove duplicates 3) consider out of boundary question whenever using arrays Use DFS without recursion: Use STACK(Every time pop an item, push the it’s children, thus accomplish DFS) Stack FILO … More DFS notes
Topological sorting is about DAG(Directed Acyclic Graph). The main idea of Kahn algorithm is to: Repeatedly find the start node(no income path, in-degree is 0) and print it. To find the start node, there are many ways. Given in-degree is the most convenient one. While sometimes we might need a map(hash map) to map the … More BFS in Topological Sorting(Kahn)
Template: If a layer traversal is needed, add a “for” loop. (Attention that queue.size will change). If in a graph, we need a hash set to store the statue of node ( visited or not), and check set.contains(child) before offerring it into queue.