算法思维-图论算法

一图的逻辑结构


/* 图节点的逻辑结构 */
class Vertex {
    int id;
    Vertex[] neighbors;
}


/* 基本的 N 叉树节点 */
class TreeNode {
    int val;
    TreeNode[] children;
}

可以看出来图的结构和多叉树基本相同，所以图论算法其本质就是对多叉树的处理

实际中我们表示一个图常用邻接表或者邻接矩阵。如我们要表示以下图结构

最后，我们再明确一个图论中特有的度（degree）的概念，在无向图中，「度」就是每个节点相连的边的条数。

由于有向图的边有方向，所以有向图中每个节点「度」被细分为入度（indegree）和出度（outdegree），其中节点 3 的入度为 3（有三条边指向它），出度为 1（它有 1 条边指向别的节点）。

二图的遍历

图和多叉树最大的区别是，图是可能包含环的，你从图的某一个节点开始遍历，有可能走了一圈又回到这个节点，而树不会出现这种情况，从某个节点出发必然走到叶子节点，绝不可能回到它自身。

所以，如果图包含环，遍历框架就要一个 visited 数组进行辅助。

类比贪吃蛇游戏，visited 记录蛇经过过的格子，而 onPath 仅仅记录蛇身


// 记录被遍历过的节点
boolean[] visited;
// 记录从起点到当前节点的路径
boolean[] onPath;

/* 图遍历框架 */
void traverse(Graph graph, int s) {
    if (visited[s]) return;
    // 经过节点 s，标记为已遍历
    visited[s] = true;
    // 做选择：标记节点 s 在路径上
    onPath[s] = true;
    for (int neighbor : graph.neighbors(s)) {
        traverse(graph, neighbor);
    }
    // 撤销选择：节点 s 离开路径
    onPath[s] = false;
}

onPath

另外，这个 onPath 数组的操作很像前文回溯算法核心套路中做「做选择」和「撤销选择」，区别在于位置：回溯算法的「做选择」和「撤销选择」在 for 循环里面，而对 onPath 数组的操作在 for 循环外面。

为什么呢？

前文纲领篇中讲到，回溯算法和 DFS 算法的区别所在：回溯算法关注的不是节点，而是树枝。

对于回溯算法，我们需要在「树枝」上做选择和撤销选择：


// DFS 算法，关注点在节点
void traverse(TreeNode root) {
    if (root == null) return;
    printf("进入节点 %s", root);
    for (TreeNode child : root.children) {
        traverse(child);
    }
    printf("离开节点 %s", root);
}

// 回溯算法，关注点在树枝
void backtrack(TreeNode root) {
    if (root == null) return;
    for (TreeNode child : root.children) {
        // 做选择
        printf("从 %s 到 %s", root, child);
        backtrack(child);
        // 撤销选择
        printf("从 %s 到 %s", child, root);
    }
}

但其实两者的区别只是在于，前者会打印所有的节点进入离开信息，而后者会漏掉根节点。

visited

于图可能含有环，visited 数组就是防止递归重复遍历同一个节点进入死循环的。

当然，如果题目告诉你图中不含环，可以把 visited 数组都省掉，基本就是多叉树的遍历。

三并查集

并查集（Union-Find）算法是一个专门针对「动态连通性」的算法。

3.1 动态连通性

简单说，动态连通性其实可以抽象成给一幅图连线。比如下面这幅图，总共有 10 个节点，他们互不相连，分别用 0~9 标记：

这里所说的「连通」是一种等价关系，也就是说具有如下三个性质：

1、自反性：节点 p 和 p 是连通的。

2、对称性：如果节点 p 和 q 连通，那么 q 和 p 也连通。

3、传递性：如果节点 p 和 q 连通，q 和 r 连通，那么 p 和 r 也连通。

比如说之前那幅图，0～9 任意两个不同的点都不连通，调用 connected 都会返回 false，连通分量为 10 个。

如果现在调用 union(0, 1)，那么 0 和 1 被连通，连通分量降为 9 个。

再调用 union(1, 2)，这时 0,1,2 都被连通，调用 connected(0, 2) 也会返回 true，连通分量变为 8 个。

这里的并查集主要实现以下的API


class UF {
    /* 将 p 和 q 连接 */
    public void union(int p, int q);
    /* 判断 p 和 q 是否连通 */
    public boolean connected(int p, int q);
    /* 返回图中有多少个连通分量 */
    public int count();
}

所以并查集基本框架如下：


    class UF {
        // 连通分量个数
        private int count;
        // 存储一棵树
        private int[] parent;

        // n 为图中节点的个数
        public UF(int n) {
            this.count = n;
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        // 将节点 p 和节点 q 连通
        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ)
                return;

            parent[rootQ] = rootP;
            // 两个连通分量合并成一个连通分量
            count--;
        }

        // 判断节点 p 和节点 q 是否连通
        public boolean connected(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            return rootP == rootQ;
        }

        // 返回节点 x 的连通分量根节点
        private int find(int x) {
            if (parent[x] != x) {
                // 进行路径压缩
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        // 返回图中的连通分量个数
        public int count() {
            return count;
        }
    }

四 Kruskal最小生成树

🌒

mst: 图中若干边的组合

最小生成树是在一个图里，满足以下特质。

连接所有节点

不存在环

权重和最小

这里使用贪心的思想：将所有边按从小到大排序，从权重小的开始遍历，如果这条边和mst中的其他边不会形成环，那这条边就是最小生成树的一部分，将它加入到mst集合。否则，这条边不是最小生成树的一部分，不加入mst。


    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        // 生成所有边及权重
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int xi = points[i][0], yi = points[i][1];
                int xj = points[j][0], yj = points[j][1];
                // 用坐标点在 points 中的索引表示坐标点
                edges.add(new int[] {
                        i, j, Math.abs(xi - xj) + Math.abs(yi - yj)
                });
            }
        }
        // 将边按照权重从小到大排序
        Collections.sort(edges, (a, b) -> {
            return a[2] - b[2];
        });

        // 执行 Kruskal 算法
        int mst = 0;
        UF uf = new UF(n);
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int weight = edge[2];
            // 若这条边会产生环，则不能加入 mst
            if (uf.connected(u, v)) {
                continue;
            }
            // 若这条边不会产生环，则属于最小生成树
            mst += weight;
            uf.union(u, v);
        }
        return mst;
    }

    class UF {
        // 连通分量个数
        private int count;
        // 存储一棵树
        private int[] parent;

        // n 为图中节点的个数
        public UF(int n) {
            this.count = n;
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        // 将节点 p 和节点 q 连通
        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ)
                return;

            parent[rootQ] = rootP;
            // 两个连通分量合并成一个连通分量
            count--;
        }

        // 判断节点 p 和节点 q 是否连通
        public boolean connected(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            return rootP == rootQ;
        }

        // 返回节点 x 的连通分量根节点
        private int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);

            }
            return parent[x];
        }

        // 返回图中的连通分量个数
        public int count() {
            return count;
        }
    }

算法思维-图论算法

一 图的逻辑结构

二 图的遍历