DFS BFS 图算法与数据结构并查集拓扑排序

LeetCode

发布日期: 2019-09-16

文章字数: 2.4k

阅读时长: 10 分

阅读次数:

二分图

785. 判断二分图

难度：中等

给定一个无向图graph，当这个图为二分图时返回true。

如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。

graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。

示例 1:
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释: 
无向图如下:
0----1
|    |
|    |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。
示例 2:
输入: [[1,2,3], [0,2], [0,1,3], [0,2]]
输出: false
解释: 
无向图如下:
0----1
| \  |
|  \ |
3----2
我们不能将节点分割成两个独立的子集。

注意:

graph 的长度范围为 [1, 100]。
graph[i] 中的元素的范围为 [0, graph.length - 1]。
graph[i] 不会包含 i 或者有重复的值。
图是无向的: 如果j 在 graph[i]里边, 那么 i 也会在 graph[j]里边。

使用一个colors 数组保存每个节点的颜色，0表示没有访问过，1和-1用来标志。

使用一个DFS 的辅助方法，把每个节点的邻居节点的颜色取反，如果再次访问到的时候，当前颜色（想要加给它的颜色）和 colors 数组中保存的颜色应该一致，如果有一个节点不一致，则说明不是二分图。

public boolean isBipartite (int[][] graph) {
    int[] colors = new int[graph.length];
    for (int i = 0; i < graph.length; i++) {  // 处理图不是连通的情况
        if (colors[i] == 0) {
            if (!dfs(i, -1, colors, graph))
                return false;
        }
    }
    return true;
}

private boolean dfs (int curNode, int curColor, int[] colors, int[][] graph) {
    if (colors[curNode] != 0 && colors[curNode] != curColor) return false;
    if (colors[curNode] != 0 ) return true;
    colors[curNode] = curColor;
    for (int adj : graph[curNode]) {
        if (!dfs(adj, -curColor, colors, graph)) {
            return false;
        }
    }
    return true;
}

拓扑排序

207. 课程表

难度：中等

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？

示例 1:

输入: 2, [[1,0]] 
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

示例 2:

输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

说明:

输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。

提示:

这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
拓扑排序也可以通过 BFS 完成。

先将给定数组通过buildAdjList构造成一个邻接表，此处使用HashMap，再设置两个HashSet，visitedTmp表示当前遍历中已经访问过的节点，visitedPerm表示整张图中已经访问过的节点。如果在一次 dfs 的遍历中，访问到了visitedTmp中的元素，说明这条路上成环了。

private Map<Integer, List<Integer>> adj = new HashMap<>();
private Set<Integer> visitedPerm = new HashSet<>();
private Set<Integer> visitedTmp = new HashSet<>();

public boolean canFinish (int numCourses, int[][] prerequisites) {
    if (numCourses <= 0 || prerequisites == null)
        return true;
    buildAdjList(prerequisites);

    for (Integer key : adj.keySet()) {
        if (!dfs(key)) {
            return false;
        }
    }

    return true;
}

private void buildAdjList (int[][] prerequisites) {

    for (int[] prerequisite : prerequisites) {
        int course = prerequisite[0];
        int preCourse = prerequisite[1];
        if (!adj.containsKey(preCourse)) {
            adj.put(preCourse, new ArrayList<>());
        }
        adj.get(preCourse).add(course);
    }
}

private boolean dfs (int node) {
    if (visitedTmp.contains(node))
        return false;
    if (visitedPerm.contains(node))
        return true;

    visitedTmp.add(node);
    visitedPerm.add(node);

    if (adj.containsKey(node)) {
        for (Integer v : adj.get(node)) {
            if (!dfs(v)) {
                return false;
            }
        }
    }

    visitedTmp.remove(node);
    return true;
}

210. 课程表 II

难度：中等

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

示例 1:

输入: 2, [[1,0]] 
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2:

输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
     因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

说明:

输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。

提示:

这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
拓扑排序也可以通过 BFS 完成。

DSF 的完成顺序就是后序，然后反向输出，逆后序就是拓扑排序

用数组+动态数组的形式保存每个节点的后置课程，用来构造邻接表。

在 DFS 的过程中，如果发现成环了，就返回空数组。

private List<Integer>[] adj;
private Set<Integer> visitedPerm = new HashSet<>();
private Set<Integer> visitedTmp = new HashSet<>();
private Stack<Integer> postOrder = new Stack<>();

public int[] findOrder (int numCourses, int[][] prerequisites) {
    if (numCourses <= 0) {
        return new int[0];
    }
    if (prerequisites.length == 0) {
        int[] ans = new int[numCourses];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = i;
        }
        return ans;
    }
    adj = new List[numCourses];

    for (int i = 0; i < numCourses; i++) {
        adj[i] = new ArrayList<>();
    }
    for (int[] p : prerequisites) {
        adj[p[1]].add(p[0]);
    }

    for (int i = 0; i < numCourses; i++) {
        if (!dfs(i)) {
            return new int[0];
        }
    }

    int[] ans = new int[numCourses];
    for (int i = 0; i < numCourses; i++) {
        ans[i] = postOrder.pop();
    }
    return ans;
}

private boolean dfs (int node) {
    if (visitedTmp.contains(node))
        return false;
    if (visitedPerm.contains(node))
        return true;

    visitedTmp.add(node);
    visitedPerm.add(node);


    for (Integer v : adj[node]) {
        if (!dfs(v)) {
            return false;
        }
    }

    postOrder.push(node);
    visitedTmp.remove(node);
    return true;
}

并查集（Union-Find）

684. 冗余连接

难度：中等

在本问题中, 树指的是一个连通且无环的无向图。

输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。

返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。

示例 1：

输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的无向图为:
  1
 / \
2 - 3

示例 2：

输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
解释: 给定的无向图为:
5 - 1 - 2
    |   |
    4 - 3

注意:

输入的二维数组大小在 3 到 1000。
二维数组中的整数在1到N之间，其中N是输入数组的大小。

更新(2017-09-26):
我们已经重新检查了问题描述及测试用例，明确图是无向图。对于有向图详见冗余连接II。对于造成任何不便，我们深感歉意。

使用并查集辅助解决这个问题，遍历给定的数组（实际上就是遍历每一条边），将每条边的两个节点设置为一个连通量。如果出现两个节点已经是连通量了，这两个节点组成的边就是我们要找的冗余连接。

如果追求速度的话，可以将并查集优化为加权 quick-union 算法（参考《算法》（第 4 版）第145页 1.5.2.6 的算法 1.5 （续））

public int[] findRedundantConnection(int[][] edges) {
    int N = edges.length;
    UF uf = new UF(N);
    for (int[] edge : edges) {
        int p = edge[0];
        int q = edge[1];
        if (uf.isConnected(p, q)) {
            return edge;
        }
        uf.union(p, q);
    }
    return new int[]{-1, -1};
}

class UF {
    private int[] id;
    private int[] size;

    UF (int N) {
        id = new int[N + 1];
        for (int i = 0; i < id.length; i++) {
            id[i] = i;
        }
        size = new int[N + 1];
        Arrays.fill(size, 1);
    }

    void union (int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        if (size[pRoot] < size[pRoot]) {
            id[pRoot] = qRoot;
            size[qRoot] += size[pRoot];
        } else {
            id[qRoot] = pRoot;
            size[pRoot] += size[qRoot];
        }
    }

    int find (int p) {
        while (p != id[p]) {
            p = id[p];
        }
        return p;
    }

    boolean isConnected (int p, int q) {
        return find(p) == find(q);
    }
}