当前位置： 面试刷题>> 图是否可以被二分 (经典算法题500道)
### 题目描述补充
给定一个无向图`G = (V, E)`，其中`V`是顶点集，`E`是边集。我们需要判断这个图是否可以被二分（也称为二部图或偶图）。在图论中，一个图如果顶点可以被划分为两个互不相交的集合A和B，使得图中的每一条边连接的两个顶点分别属于A和B（即图中没有边连接两个属于同一集合的顶点），则称该图为二分图。
### 示例
假设有以下图：
```
A ---- B
/ \ / \
C---D---E
\ / \ /
F ---- G
```
此图可以被二分，例如，顶点集A = {A, C, E, G} 和 B = {B, D, F}。
### 解题思路
一种常见的方法是使用图的着色算法（也称为二分图判定算法），通常通过深度优先搜索（DFS）或广度优先搜索（BFS）来实现。我们可以尝试给每个顶点着色（通常是两种颜色，如0和1），并确保每条边的两个顶点颜色不同。
### PHP 示例代码
```php
[1, 2],
1 => [0, 3, 4],
2 => [0, 3, 5],
3 => [1, 2, 4],
4 => [1, 3, 5],
5 => [2, 4]
];
// 调用函数并输出结果
if (isBipartite($graph)) {
echo "该图是一个二分图。\n";
} else {
echo "该图不是一个二分图。\n";
}
?>
```
### Python 示例代码
```python
def is_bipartite(graph):
def dfs(node, color, colors):
colors[node] = color
for neighbor in graph[node]:
if colors[neighbor] == color:
return False
if colors[neighbor] == -1 and not dfs(neighbor, 1 - color, colors):
return False
return True
n = len(graph)
colors = [-1] * n
for i in range(n):
if colors[i] == -1 and not dfs(i, 0, colors):
return False
return True
# 示例图的邻接表表示
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 3, 5],
3: [1, 2, 4],
4: [1, 3, 5],
5: [2, 4]
}
# 调用函数并输出结果
if is_bipartite(graph):
print("该图是一个二分图。")
else:
print("该图不是一个二分图。")
```
### JavaScript 示例代码
```javascript
function isBipartite(graph) {
const n = graph.length;
const colors = new Array(n).fill(-1); // -1 表示未着色
function dfs(node, color) {
colors[node] = color;
for (let neighbor of graph[node]) {
if (colors[neighbor] === color) return false;
if (colors[neighbor] === -1 && !dfs(neighbor, 1 - color)) return false;
}
return true;
}
for (let i = 0; i < n; i++) {
if (colors[i] === -1 && !dfs(i, 0)) {
return false;
}
}
return true;
}
// 示例图的邻接表表示
const graph = [
[1, 2], [0, 3, 4], [0, 3, 5], [1, 2, 4], [1, 3, 5], [2, 4]
];
// 调用函数并输出结果
if (isBipartite(graph)) {
console.log("该图是一个二分图。");
} else {
console.log("该图不是一个二分图。");
}
```
码小课网站中有更多相关内容分享给大家学习，包括图论的其他算法和数据结构的高级应用。