图

编辑中

搜索算法

• DFS
  主要用于计算连通块的个数、大小，现在给出DFS迭代的模板:

def dfs(grid, i, j):
    if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) 
    : return
    grid[i][j] = '0'
    dfs(grid, i + 1, j)
    dfs(grid, i, j + 1)
    dfs(grid, i - 1, j)
    dfs(grid, i, j - 1)

• BFS
  主要用于计算距离问题，现在给出DFS迭代的模板:

def bfs(grid, i, j):
    queue = [[i, j]]
    while queue:
        [i, j] = queue.pop(0)
        if 0 <= i < len(grid) and 0 <= j < len(grid[0]):
            grid[i][j] = '0'
            queue += [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]

注意：BFS的模板中，通常用于计算距离问题，当处理1:N的距离问题时，初始化队列时往往加入一个元素，而处理N:N的距离问题时，初始化队列时往往所有需要N元素,考虑问题类似小岛批量沉默。

• 0-1BFS

while (!deque.isEmpty()) {
    int[] cur = deque.pollFirst();
    int x = cur[0], y = cur[1];
    for (int[] dir : dirs) {
        int nx = x + dir[0], ny = y + dir[1];
        if(nx>=0 && ny>=0 && nx<m && ny<n){
            if(cost[nx][ny]>grid[x][y]+cost[x][y]){
                cost[nx][ny] = cost[x][y]+grid[x][y];
                if(grid[nx][ny]==1)
                    deque.addLast(new int[]{nx, ny});
                else
                    deque.addFirst(new int[]{nx, ny});
            }
        }
    }
}
// 另一种方法，利用priorityQueue
PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> dp[a[0]][a[1]] - dp[b[0]][b[1]]);

求可变迷宫最短路径问题，图中只有两种状态。采用双向队列，思路是队列中前半部分代价永远比后半部分小，将通透路径点加入前半部分，其余加入后半部分。

并查集

@::: code-tabs
#shell
@tab java

public class UnionFind {
    private int[] parent;

    public UnionFind(int size) {
        parent = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }

    public int find(int p) {
        if (p == parent[p]) {
            return p;
        } else {
            parent[p] = find(parent[p]);
            return parent[p];
        }
    }

    public void union(int p1, int p2) {
        parent[find(p1)] = find(p2);
    }
}

@tab python

class UninoFind:
    def __init__(self,size):
        self.parent = list(range(size))
    
    def find(self,p):
        if p == self.parent[p]:
            return p
        else:
            self.parent[p] = self.find(self.parent[p])
            return self.parent[p]
    
    def union(self,p1,p2):
        self.parent[self.find(p1)] = self.find(p2)

:::

其中：
find函数：相当于连线，如果p节点有父节点，则指向父节点来进一步搜索根节点。
union函数：将节点p1指向节点p2。

• 时间复杂度：O(n+ClogC)，其中 n 是 equations 中的方程数量，C 是变量的总数

• 空间复杂度：O(C)。

该模板中只用到了并查集中最简单的优化方法，即路径压缩，在find函数中定义，将p节点的父节点通过find函数连接到父亲的父亲，降低二叉树的高度。如果find函数调用次数够多，最终可能会出现每个节点都指向最终父节点的高度为2的树。

其他复杂问题

如何检测是否有环？

bfs搜索，如果当前节点的下一搜索节点距离源节点的距离大于等于当前节点，则表示有环。