PINEAL.ME   Archives  About

Topics on Gragh Algorithm

Graph

Graph Representing

https://www.geeksforgeeks.org/graph-and-its-representations/

https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs

Adjacent Matrix

Adjacent List

https://www.geeksforgeeks.org/graph-implementation-using-stl-for-competitive-programming-set-1-dfs-of-unweighted-and-undirected/

https://www.geeksforgeeks.org/graph-implementation-using-stl-for-competitive-programming-set-2-weighted-graph/

Edges

Traversal

BFS

DFS

  1. Pacific Atlantic Water Flow

  2. start from matrix

  3. start from occean

  4. Clone Graph follow up: reverse if DAG

Topological Sorting

DFS method

拓扑排序的常规方法是用DFS。DFS 有一个好处就是可以 backtracking 到所有的 solution。

https://www.geeksforgeeks.org/topological-sorting/

BFS

另一个方法 Kahn’s algorithm 用记录入度/出度的方式进行BFS, 相对容易记忆和实现

https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/

More questions

Course Schedule | Solution

Course Schedule II | Solution

Sequence Reconstruction

Longest Increasing Path in a Matrix

Alien Dictionary

All Topological sorts of a DAG | should use DFS

Connected Component

Connected components for undirected graph

Number of Connected Components

Strongly Connected Components

https://www.geeksforgeeks.org/strongly-connected-components/

https://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/

https://www.geeksforgeeks.org/connectivity-in-a-directed-graph/

Shortest Path

Shortest distance in adjacent table - BFS

Best Meeting Point

Shortest Distance from All Buildings

Dijkstra

https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-set-in-stl/

https://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/

https://www.geeksforgeeks.org/greedy-algorithms-set-7-dijkstras-algorithm-for-adjacency-list-representation/

A star

https://github.com/pineal/-O_O-/blob/master/A_Star_Search/A_Star_Search.cpp

Iterative Deepening Search(IDS) or Iterative Deepening Depth First Search(IDDFS)

https://www.geeksforgeeks.org/iterative-deepening-searchids-iterative-deepening-depth-first-searchiddfs/

Bipartite

Is Graph Bipartite

bfs   dfs   topological sorting   graph