- 排序 选择 , SORT
- Graph Search
- MST, Shortest Path
- 图 Min Cut
- Heap , Priority Queue
- Binary Search Tree
- hash
- Symbol Table 实现, HASH
- Dynamic Programming
- Monte Carlo Tree Search
| solved problem | method | graph | comments |
|---|---|---|---|
| connected component | DFS | undirected graph | |
| connectivity | DFS | undirected graph | |
| topology sort | DFS | DAG | sink vertex |
| strongly connected component | DFS | directed graph | reverse G, sink component |
| shortest path | Dijkstra | graph | |
| shortest path | Bellman-Ford | negative weighted edge | |
| MST | Kruskal | undirected graph | |
| MST | Prim | undirected graph | |
| shortest path in social network | Bidirectional Dijkstra | graph |
More applications
| problem | method | graph | comments |
|---|---|---|---|
| Is a graph bipartite | DFS | undirected graph | |
| does the graph exist a cycle | DFS | graph |