经典图论算法
二分图
概念
在图论中，二分图（bipartite graph）是一类特殊的图，又称为二部图、偶图、双分图。二分图的顶点可以分成两个互斥的独立集 U 和 V 的图，使得所有边都是连结一个 U 中的点和一个 V 中的点。
场景
二分图结构在某些场景可以更高效地存储数据
比如说我们需要一种数据结构来储存电影和演员之间的关系：某一部电影肯定是由多位演员出演的，且某一位演员可能会出演多部电影。你使用什么数据结构来存储这种关系呢？
既然是存储映射关系，最简单的不就是使用哈希表嘛，我们可以使用一个 HashMap<String, List<String>> 来存储电影到演员列表的映射，如果给一部电影的名字，就能快速得到出演该电影的演员。
但是如果给出一个演员的名字，我们想快速得到该演员演出的所有电影，怎么办呢？这就需要「反向索引」，对之前的哈希表进行一些操作，新建另一个哈希表，把演员作为键，把电影列表作为值。
显然，如果用哈希表存储，需要两个哈希表分别存储「每个演员到电影列表」的映射和「每部电影到演员列表」的映射。但如果用「图」结构存储，将电影和参演的演员连接，很自然地就成为了一幅二分图：
染色问题
给你一幅「图」，请你用两种颜色将图中的所有顶点着色，且使得任意一条边的两个端点的颜色都不相同，你能做到吗？
这就是图的「双色问题」，其实这个问题就等同于二分图的判定问题，如果你能够成功地将图染色，那么这幅图就是一幅二分图，反之则不是：
判定
框架
/* 图遍历框架 */ void traverse(Graph graph, boolean[] visited, int v) { visited[v] = true; // 遍历节点 v 的所有相邻节点 neighbor for (int neighbor : graph.neighbors(v)) { if (!visited[neighbor]) { // 相邻节点 neighbor 没有被访问过 // 那么应该给节点 neighbor 涂上和节点 v 不同的颜色 traverse(graph, visited, neighbor); } else { // 相邻节点 neighbor 已经被访问过 // 那么应该比较节点 neighbor 和节点 v 的颜色 // 若相同，则此图不是二分图 } } }
785. 判断二分图
存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性：
不存在自环（graph[u] 不包含 u）。
不存在平行边（graph[u] 不包含重复值）。
如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图）
这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。
二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图 。
如果图是二分图，返回 true ；否则，返回 false 。
DFS 算法的逻辑
class Solution { // 记录图是否符合二分图性质 private boolean ok = true; // 记录图中节点的颜色，false 和 true 代表两种不同颜色 private boolean[] color; // 记录图中节点是否被访问过 private boolean[] visited; // 主函数，输入邻接表，判断是否是二分图 public boolean isBipartite(int[][] graph) { int n = graph.length; color = new boolean[n]; visited = new boolean[n]; // 因为图不一定是联通的，可能存在多个子图 // 所以要把每个节点都作为起点进行一次遍历 // 如果发现任何一个子图不是二分图，整幅图都不算二分图 for (int v = 0; v < n; v++) { if (!visited[v]) { traverse(graph, v); } } return ok; } // DFS 遍历框架 private void traverse(int[][] graph, int v) { // 如果已经确定不是二分图了，就不用浪费时间再递归遍历了 if (!ok) return; visited[v] = true; for (int w : graph[v]) { if (!visited[w]) { // 相邻节点 w 没有被访问过 // 那么应该给节点 w 涂上和节点 v 不同的颜色 color[w] = !color[v]; // 继续遍历 w traverse(graph, w); } else { // 相邻节点 w 已经被访问过 // 根据 v 和 w 的颜色判断是否是二分图 if (color[w] == color[v]) { // 若相同，则此图不是二分图 ok = false; return; } } } } }
BFS 算法的逻辑
class Solution { // 记录图是否符合二分图性质 private boolean ok = true; // 记录图中节点的颜色，false 和 true 代表两种不同颜色 private boolean[] color; // 记录图中节点是否被访问过 private boolean[] visited; public boolean isBipartite(int[][] graph) { int n = graph.length; color = new boolean[n]; visited = new boolean[n]; for (int v = 0; v < n; v++) { if (!visited[v]) { // 改为使用 BFS 函数 bfs(graph, v); } } return ok; } // 从 start 节点开始进行 BFS 遍历 private void bfs(int[][] graph, int start) { Queue<Integer> q = new LinkedList<>(); visited[start] = true; q.offer(start); while (!q.isEmpty() && ok) { int v = q.poll(); // 从节点 v 向所有相邻节点扩散 for (int w : graph[v]) { if (!visited[w]) { // 相邻节点 w 没有被访问过 // 那么应该给节点 w 涂上和节点 v 不同的颜色 color[w] = !color[v]; // 标记 w 节点，并放入队列 visited[w] = true; q.offer(w); } else { // 相邻节点 w 已经被访问过 // 根据 v 和 w 的颜色判断是否是二分图 if (color[w] == color[v]) { // 若相同，则此图不是二分图 ok = false; return; } } } } } }
886. 可能的二分法
给定一组 n 人（编号为 1, 2, ..., n）， 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。
给定整数 n 和数组 dislikes ，其中 dislikes[i] = [ai, bi] ，表示不允许将编号为 ai 和 bi的人归入同一组。当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。
思路:
把每个人看做图中的节点，相互讨厌的关系看做图中的边，那么 dislikes 数组就可以构成一幅图；
又因为题目说互相讨厌的人不能放在同一组里，相当于图中的所有相邻节点都要放进两个不同的组；
那就回到了「双色问题」，如果能够用两种颜色着色所有节点，且相邻节点颜色都不同，那么你按照颜色把这些节点分成两组不就行了嘛。
解法: 我们把 dislikes 构造成一幅图，然后执行二分图的判定算法即可
class Solution { // 记录图是否符合二分图性质 private boolean ok = true; // 记录图中节点的颜色，false 和 true 代表两种不同颜色 private boolean[] color; // 记录图中节点是否被访问过 private boolean[] visited; public boolean possibleBipartition(int n, int[][] dislikes) { // 图节点编号从 1 开始 color = new boolean[n + 1]; visited = new boolean[n + 1]; // 转化成邻接表表示图结构 List<Integer>[] graph = buildGraph(n, dislikes); for(int v = 1; v <= n; v++) { if(!visited[v]) { traverse(graph, v); } } return ok; } /** 建图函数 */ private List<Integer>[] buildGraph(int n, int[][] prerequisites) { // 图节点编号为 1...n List<Integer>[] graph = new LinkedList[n + 1]; for (int i = 1; i <= n; i++) { graph[i] = new LinkedList<>(); } for (int[] edge : prerequisites) { int from = edge[1], to = edge[0]; // 「无向图」相当于「双向图」 graph[from].add(to); graph[to].add(from); } return graph; } // DFS 遍历框架 二分图的判定 private void traverse(List<Integer>[] graph, int v) { // 如果已经确定不是二分图了，就不用浪费时间再递归遍历了 if (!ok) return; visited[v] = true; for (int w : graph[v]) { if (!visited[w]) { // 相邻节点 w 没有被访问过 // 那么应该给节点 w 涂上和节点 v 不同的颜色 color[w] = !color[v]; // 继续遍历 w traverse(graph, w); } else { // 相邻节点 w 已经被访问过 // 根据 v 和 w 的颜色判断是否是二分图 if (color[w] == color[v]) { // 若相同，则此图不是二分图 ok = false; return; } } } } }
