乐趣区

关于智能合约:东哥带你刷图论第四期二分图的判定

读完本文,你不仅学会了算法套路,还能够顺便去 LeetCode 上拿下如下题目:

  1. 判断二分图(中等)
  2. 可能的二分法(中等)

———–

我之前写了好几篇图论相干的文章:

图遍历算法

名流问题

并查集算法计算连通重量

环检测和拓扑排序

Dijkstra 最短门路算法

明天持续来讲一个经典图论算法:二分图断定。

二分图简介

在讲二分图的断定算法之前,咱们先来看下百度百科对「二分图」的定义:

二分图的顶点集可宰割为两个互不相交的子集,图中每条边附丽的两个顶点都分属于这两个子集,且两个子集内的顶点不相邻。

其实图论外面很多术语的定义都比拟拗口,不容易了解。咱们甭看这个死板的定义了,来玩个游戏吧:

给你一幅「图」,请你用两种色彩将图中的所有顶点着色,且使得任意一条边的两个端点的色彩都不雷同,你能做到吗

这就是图的「双色问题」,其实这个问题就等同于二分图的断定问题,如果你可能胜利地将图染色,那么这幅图就是一幅二分图,反之则不是:

在具体解说二分图断定算法之前,咱们先来说说计算机大佬们闲着无聊解决双色问题的目标是什么。

首先,二分图作为一种非凡的图模型,会被很多高级图算法(比方最大流算法)用到,不过这些高级算法咱们不是特地有必要去把握,有趣味的读者能够自行搜寻。

从简略实用的角度来看,二分图构造在某些场景能够更高效地存储数据。

比方前文 介绍《算法 4》文章中的例子,如何存储电影演员和电影之间的关系?

如果用哈希表存储,须要两个哈希表别离存储「每个演员到电影列表」的映射和「每部电影到演员列表」的映射。

但如果用「图」构造存储,将电影和参演的演员连贯,很天然地就成为了一幅二分图:

每个电影节点的相邻节点就是参演该电影的所有演员,每个演员的相邻节点就是该演员参演过的所有电影,十分不便直观。

类比这个例子,其实生存中不少实体的关系都能天然地造成二分图构造,所以在某些场景下图构造也能够作为存储键值对的数据结构(符号表)。

好了,接下来进入正题,说说如何断定一幅图是否是二分图。

二分图断定思路

断定二分图的算法很简略,就是用代码解决「双色问题」。

说白了就是遍历一遍图,一边遍历一遍染色,看看能不能用两种色彩给所有节点染色,且相邻节点的色彩都不雷同

既然说到遍历图,也不波及最短门路之类的,当然是 DFS 算法和 BFS 皆可了,DFS 算法绝对更罕用些,所以咱们先来看看如何用 DFS 算法断定双色图。

首先,基于 学习数据结构和算法的框架思维 写出图的遍历框架:

/* 二叉树遍历框架 */
void traverse(TreeNode root) {if (root == null) return;
    traverse(root.left);
    traverse(root.right);
}

/* 多叉树遍历框架 */
void traverse(Node root) {if (root == null) return;
    for (Node child : root.children)
        traverse(child);
}

/* 图遍历框架 */
boolean[] visited;
void traverse(Graph graph, int v) {
    // 避免走回头路进入死循环
    if (visited[v]) return;
    // 前序遍历地位,标记节点 v 已拜访
    visited[v] = true;
    for (TreeNode neighbor : graph.neighbors(v))
        traverse(graph, neighbor);
}

因为图中可能存在环,所以用 visited 数组避免走回头路。

这里能够看到我习惯把 return 语句都放在函数结尾,因为个别 return 语句都是 base case,集中放在一起能够让算法构造更清晰

其实,如果你违心,也能够把 if 判断放到其它中央,比方图遍历框架能够略微改改:

/* 图遍历框架 */
boolean[] visited;
void traverse(Graph graph, int v) {
    // 前序遍历地位,标记节点 v 已拜访
    visited[v] = true;
    for (int neighbor : graph.neighbors(v)) {if (!visited[neighbor]) {
            // 只遍历没标记过的相邻节点
            traverse(graph, neighbor);
        }
    }
}

这种写法把对 visited 的判断放到递归调用之前,和之前的写法惟一的不同就是,你须要保障调用 traverse(v) 的时候,visited[v] == false

为什么要特地说这种写法呢?因为咱们判断二分图的算法会用到这种写法。

回顾一下二分图怎么判断,其实就是让 traverse 函数一边遍历节点,一边给节点染色,尝试让每对相邻节点的色彩都不一样

所以,断定二分图的代码逻辑能够这样写:

/* 图遍历框架 */
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 题「判断二分图」就是原题,题目给你输出一个 邻接表 示意一幅无向图,请你判断这幅图是否是二分图。

函数签名如下:

boolean isBipartite(int[][] graph);

比方题目给的例子,输出的邻接表 graph = [[1,2,3],[0,2],[0,1,3],[0,2]],也就是这样一幅图:

显然无奈对节点着色使得每两个相邻节点的色彩都不雷同,所以算法返回 false。

但如果输出 graph = [[1,3],[0,2],[1,3],[0,2]],也就是这样一幅图:

如果把节点 {0, 2} 涂一个色彩,节点 {1, 3} 涂另一个色彩,就能够解决「双色问题」,所以这是一幅二分图,算法返回 true。

联合之前的代码框架,咱们能够额定应用一个 color 数组来记录每个节点的色彩,从而写出解法代码:

// 记录图是否合乎二分图性质
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;
            }
        }
    }
}

这就是解决「双色问题」的代码,如果能胜利对整幅图染色,则阐明这是一幅二分图,否则就不是二分图。

接下来看一下 BFS 算法的逻辑:

// 记录图是否合乎二分图性质
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;
                }
            }
        }
    }
}

外围逻辑和方才实现的 traverse 函数(DFS 算法)齐全一样,也是依据相邻节点 vw 的色彩来进行判断的。对于 BFS 算法框架的探讨,详见前文 BFS 算法框架 和 Dijkstra 算法模板,这里就不开展了。

最初再来看看力扣第 886 题「可能的二分法」:

函数签名如下:

boolean possibleBipartition(int n, int[][] dislikes);

其实这题考查的就是二分图的断定

如果你把每个人看做图中的节点,互相厌恶的关系看做图中的边,那么 dislikes 数组就能够形成一幅图;

又因为题目说相互厌恶的人不能放在同一组里,相当于图中的所有相邻节点都要放进两个不同的组;

那就回到了「双色问题」,如果可能用两种色彩着色所有节点,且相邻节点色彩都不同,那么你依照色彩把这些节点分成两组不就行了嘛。

所以解法就进去了,咱们把 dislikes 结构成一幅图,而后执行二分图的断定算法即可:

private boolean ok = 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[][] dislikes) {
    // 图节点编号为 1...n
    List<Integer>[] graph = new LinkedList[n + 1];
    for (int i = 1; i <= n; i++) {graph[i] = new LinkedList<>();}
    for (int[] edge : dislikes) {int v = edge[1];
        int w = edge[0];
        //「无向图」相当于「双向图」// v -> w
        graph[v].add(w);
        // w -> v
        graph[w].add(v);
    }
    return graph;
}

// 和之前的 traverse 函数完全相同
private void traverse(List<Integer>[] graph, int v) {if (!ok) return;
    visited[v] = true;
    for (int w : graph[v]) {if (!visited[w]) {color[w] = !color[v];
            traverse(graph, w);
        } else {if (color[w] == color[v]) {ok = false;}
        }
    }
}

至此,这道题也应用 DFS 算法解决了,如果你想用 BFS 算法,和之前写的解法是齐全一样的,能够本人尝试实现。

二分图的断定算法就讲到这里,更多二分图的高级算法,敬请期待。

_____________

查看更多优质算法文章 点击我的头像,手把手带你刷力扣,致力于把算法讲清楚!我的 算法教程 曾经取得 90k star,欢送点赞!

退出移动版