graph 算法题目思考

Graph算是非常常见的题目，一般会给你一个2d array或一个数组代表联系，你可以使用这个输入来转换成一个图表示的数据结构，之后在图里做搜索。常见的算法：

  • BFS，DFS
  • union find
  • A*
  • Floyd and dijkstra

Leetcode里的题目的话主要都是dfs, bfs就可以解决，有些需要思考几个之间的关系的题目可以使用union find来做。少部分计算路径的题目需要使用一些基本的最短路径算法。

BFS and DFS

BFS就是使用一个queue,每次在遍历一个点的时候就把这个点放到queue里，是一个FIFO的结构。一层一层的遍历，基本应用是在tree level 遍历。这种方法找最短路径比较好，问题是一次要走很多。相对来说，BFS和DFS都可以解决一道题目，区别只是遍历的顺序不同。 DFS需要使用stack来解决，或者递归。

对于找所有东西是不是一类的题目，经典题目就是看有几个岛的题目，利用dfs可以很方便的写出来。如果是无向图的话，从区域里的任意一点应该是可以到这个区域里任意一点的。所以只要有这个就可以找到所有是一类的点。

Dfs也可以用来实现有向图找环的策略，基本思路就是把图中的点标为白色（unvisited）,灰色(visiting)，黑色(visited)。如果在访问途中遇到灰色的节点，就说明这个点被访问过了，图中有环。

在记录状态时可以使用bitmask来判定是不是所有的point已经visit过了，另外在搜索时可以使用heap来只搜索最小cost的，这样有利于快速找到最优解。

Union find

这类题目一般都是存在多个点属于一个类别的题目，之后可以通过图的关系把这些点合并到一个类别里面。union find 可以用来找无向图中是否有环。基本算法如下：

class DSU {
    int[] parent;
    public DSU(int N) {
        parent = new int[N];
        for (int i = 0; i < N; ++i)
            parent[i] = i;
    }
    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    public void union(int x, int y) {
        parent[find(x)] = find(y);
    }
}

其实也不需要每次写个类，只需要把function 定义好即可。

最短路径算法

单点最短路径算法： bellman-ford 算法，基本思路就是每次更新从起点到v的距离，如果起点到u再到v的路程短，那么就更新。

 for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w

之所以要重复n遍，因为最长的最短路径可能经过所有的节点，所以需要全部走一遍。

多点最短路径算法： Floyd 算法。基本思路是每个节点都做中间的节点，之后再尝试两边，更新距离。

for k from 1 to |V|
   for i from 1 to |V|
      for j from 1 to |V|
         if dist[i][j] > dist[i][k] + dist[k][j] 
            dist[i][j] ← dist[i][k] + dist[k][j]

Dijkstra’s 算法，这也是单点最短路径算法，基本思路是每次从q中取最小的节点，之后更新从该点到其他的点的距离。

  function Dijkstra(G, w, s)
    for each vertex v in V[G]        // 初始化
           d[v] := infinity           // 將各點的已知最短距離先設成無窮大
    d[s] := 0                        // 因为出发点到出发点间不需移动任何距离，所以可以直接将s到s的最小距离设为0
     S := empty set
     Q := set of all vertices
     while Q is not an empty set      // Dijkstra演算法主體
           u := Extract_Min(Q)
           S.append(u)
          for each edge outgoing from u as (u,v)
               if d[v] > d[u] + w(u,v)  // 拓展边（u,v）。w(u,v)为从u到v的路径长度。
                   d[v] := d[u] + w(u,v)  // 更新路径长度到更小的那个和值。