fucking-algorithm
fucking-algorithm copied to clipboard
Published
20 hours ago •
labuladong
labuladong
二分图判定 :: labuladong的算法小抄
js 785. 判断二分图 DFS 解法
var isBipartite = function(graph) {
const n = graph.length;
// 记录图是否符合二分图性质
let valid = true;
// 记录图中节点是否被访问（着色）过
const visited = {};
// 记录图中节点的颜色，false 和 true 代表两种不同颜色
const colors = new Array(n).fill(false);
// 因为图不一定是联通的，可能存在多个子图
// 所以要把每个节点都作为起点进行一次遍历
// 如果发现任何一个子图不是二分图，整幅图都不算二分图
for (let v = 0; v < n; v++) {
if (visited[v]) continue;
traverse(v);
}
return valid;
// DFS 遍历框架
function traverse(v) {
// 如果已经确定不是二分图了，就不用浪费时间再递归遍历了
if (!valid) return;
visited[v] = true;
for (const n of graph[v]) {
// 相邻节点被访问过
// 比较两个节点的颜色是否相同
// 比如相同，则不是二分图
if (visited[n]) {
if (colors[n] === colors[v]) {
valid = false;
return;
}
continue;
}
// 相邻节点没有被访问过
// 那么涂色
colors[n] = !colors[v];
// 继续遍历
traverse(n);
}
}
};
js 785. 判断二分图 BFS 解法
var isBipartite = function(graph) {
const n = graph.length;
// 记录图是否符合二分图性质
let valid = true;
// 记录图中节点是否被访问（着色）过
const visited = {};
// 记录图中节点的颜色，false 和 true 代表两种不同颜色
const colors = new Array(n).fill(false);
// 因为图不一定是联通的，可能存在多个子图
// 所以要把每个节点都作为起点进行一次遍历
// 如果发现任何一个子图不是二分图，整幅图都不算二分图
for (let v = 0; v < n; v++) {
if (visited[v]) continue;
traverse(v);
}
return valid;
// BFS 遍历框架
function traverse(start) {
const q = [start];
visited[start] = true;
while (q.length && valid) {
const v = q.shift();
// 从节点 v 向所有相邻节点扩散
for (const n of graph[v]) {
// 相邻节点被访问过
// 比较两个节点的颜色是否相同
// 比如相同，则不是二分图
if (visited[n]) {
if (colors[n] === colors[v]) {
valid = false;
return;
}
continue;
}
// 相邻节点没有被访问过
// 那么涂色
colors[n] = !colors[v];
visited[n] = true;
q.push(n);
}
}
}
};
js 886. 可能的二分法
let valid = true;
const colors = new Array(n + 1).fill(false);
const visited = [];
// 转化成邻接表表示图结构
const graph = buildGraph();
// 图节点编号从 1 开始
for (let v = 1; v <= n; v++) {
if (visited[v]) continue;
traverse(v);
}
return valid;
// 建图
function buildGraph() {
// 图节点编号为 1...n
const graph = new Array(n + 1).fill(0).map(
() => []
);
for (const [v, n] of dislikes) {
// 「无向图」相当于「双向图」
graph[v].push(n);
graph[n].push(v);
}
return graph;
}
function traverse(v) {
if (!valid) return;
visited[v] = true;
for (const n of graph[v]) {
if (visited[n]) {
// 相邻着色相同，说明不喜欢的两个人分到同一组了
if (colors[n] === colors[v]) {
valid = false;
return;
}
continue;
}
colors[n] = !colors[v];
traverse(n);
}
}
210「 课程表 II」的BFS解法则使用入度作为算法入口
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indgree[i] == 0) {
// 节点 i 没有入度，即没有依赖的节点
// 可以作为拓扑排序的起点，加入队列
q.offer(i);
}
}
当解答 785「 判断二分图」的时候，发现入度全部不为0，根本无法进入BFS循环。 看了题解才知道，对于不一定连通的图，BFS的循环方式如下：
for (int v = 0; v < n; v++) {
if (!visited[v]) {
bfs(graph, v);
}
}
那么我可不可以这么理解： 入度出度的适用范围是：1. 有向图 并且 2.图是连通的 循环调用BFS的适用范围是：1.无向图 或者 2.图未必连通
@omgwtfholyshit 你可以理解为，indegree 数组只适用于拓扑排序的场景，其他场景的 BFS/DFS 遍历都是配合 visited 数组进行的。
明白了,如果不能通过下标找到下一个节点就得建图,或者说让每个数组下标代表一个人,下标所在元素(一个链表)代表这个人能走向的目的地.所以有时候根据二维数组的定义就是天然的邻接表,有些题得自己建
C++
#include <vector>
using namespace std;
class Solution{
public:
vector<bool> color; // 给结点染色
vector<bool> visited; // 保存访问过的结点
bool isBi = true; // 是否符合二分图
bool isBipartite(vector<vector<int>> &graph){
visited.resize(graph.size());
color.resize(graph.size());
for (int i = 0; i < graph.size(); i++)// 图可能并不连通
if (!visited[i] && isBi) traverse(graph, i);
return isBi;
}
void traverse(vector<vector<int>> &graph, int v){
visited[v] = true;
for (int n : graph[v]) {// 遍历顶点v的所有邻居顶点
if (visited[n] == false) {
color[n] = !color[v];// 没访问过的顶点，染成反色
traverse(graph, n);
}
else{
if (color[n] == color[v]) isBi = false;// 两个相邻顶点同色，不符合二分图
}
}
}
};
有帮助的话请点个赞再走~
c++ bfs
class Solution {
public:
bool ok {true};
vector<bool> visited;
vector<bool> color;
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
visited.resize(n);
color.resize(n);
for(int i = 0; i < n; i++) {
if(!visited[i]&&ok){
bfs(graph,i);
}
}
return ok;
}
void bfs(vector<vector<int>>& graph,int &s){
queue<int> q;
q.emplace(s);
while(!q.empty() && ok){
int v = q.front();
q.pop();
visited[v] = true;
for(const auto &w : graph[v]){
if(!visited[w]){
color[w] = !color[v];
q.emplace(w);
}else if(color[w] == color[v]){
ok = false;
return;
}
}
}
}
};
785 Python3 DFS
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
#DFS
self.isBp = True
self.visited = set()
self.colormap = {}
for i in range(len(graph)):
#已遍历过的连接子图跳过
if i not in self.visited:
self.colormap[i] = 0
self.traverse(i,graph)
return self.isBp
def traverse(self,node,graph):
if not self.isBp:
return
self.visited.add(node)
for nextnode in graph[node]:
if nextnode not in self.visited:
self.colormap[nextnode] = (self.colormap[node] + 1) % 2
self.traverse(nextnode,graph)
else:
if self.colormap[nextnode] == self.colormap[node]:
self.isBp = False
return
return
BFS
class Solution:
#BFS
def isBipartite(self, graph: List[List[int]]) -> bool:
isBp = True
colormap = {}
visited = set()
for i in range(len(graph)):
#已遍历过的连接子图跳过
if i not in visited:
queue = deque()
queue.append(i)
visited.add(i)
colormap[i] = 0
while queue and isBp:
curNode = queue.popleft()
for nextNode in graph[curNode]:
if nextNode not in visited:
colormap[nextNode] = (colormap[curNode] + 1) % 2
queue.append(nextNode)
visited.add(nextNode)
else:
if colormap[nextNode] == colormap[curNode]:
isBp = False
break
return isBp
