极客教程C++检查给定图是否使用DFS为双向图
给定一个连通图，请检查该图是否是二分图。如果可以使用两种颜色进行图着色，使得同一组中的顶点具有相同的颜色，则可能存在二分图。请注意，可以使用两种颜色来对一个带偶环的循环图进行着色。例如，请参见以下图。
无法使用两种颜色对带奇数环的循环图进行着色。
在之前的帖子中，已经讨论了使用BFS的方法。在本文中，已经实现了使用DFS的方法。
如下是检查图的双边性的算法。
- 使用一个 color[] 数组，该数组为每个节点存储0或1，表示相反的颜色。
- 从任何节点调用函数DFS。
- 如果节点u之前没有被访问过，则将!color[v]分配给color[u]并再次调用DFS来访问连接到u的节点。
- 如果在任何时候color[u]等于color[v]，则该节点不是二分图。
- 修改DFS函数，使其在结束时返回一个布尔值。
下面是上述方法的实现：
// C++ program to check if a connected
// graph is bipartite or not using DFS
#include <bits/stdc++.h>
using namespace std;
// function to store the connected nodes
void addEdge(vector<int> adj[], int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
// function to check whether a graph is bipartite or not
bool isBipartite(vector<int> adj[], int v,
vector<bool>& visited, vector<int>& color)
{
for (int u : adj[v]) {
// if vertex u is not explored before
if (visited[u] == false) {
// mark present vertices as visited
visited[u] = true;
// mark its color opposite to its parent
color[u] = !color[v];
// if the subtree rooted at vertex v is not bipartite
if (!isBipartite(adj, u, visited, color))
return false;
}
// if two adjacent are colored with same color then
// the graph is not bipartite
else if (color[u] == color[v])
return false;
}
return true;
}
// Driver Code
int main()
{
// no of nodes
int N = 6;
// to maintain the adjacency list of graph
vector<int> adj[N + 1];
// to keep a check on whether
// a node is discovered or not
vector<bool> visited(N + 1);
// to color the vertices
// of graph with 2 color
vector<int> color(N + 1);
// adding edges to the graph
addEdge(adj, 1, 2);
addEdge(adj, 2, 3);
addEdge(adj, 3, 4);
addEdge(adj, 4, 5);
addEdge(adj, 5, 6);
addEdge(adj, 6, 1);
// marking the source node as visited
visited[1] = true;
// marking the source node with a color
color[1] = 0;
// Function to check if the graph
// is Bipartite or not
if (isBipartite(adj, 1, visited, color)) {
cout << "Graph is Bipartite";
}
else {
cout << "Graph is not Bipartite";
}
return 0;
}
// 使用DFS检查连接的图是否为二分图的Java程序
import java.util.*;
class GFG{
// 存储连接节点的函数
static void addEdge(ArrayList<ArrayList<Integer>> adj,
int u, int v)
{
adj.get(u).add(v);
adj.get(v).add(u);
}
// 检查图是否为二分图的函数
static boolean isBipartite(ArrayList<ArrayList<Integer>> adj,
int v, boolean visited[],
int color[])
{
for(int u : adj.get(v))
{
// 如果顶点u以前没有被探索过
if (visited[u] == false)
{
// 将当前顶点标记为已访问
visited[u] = true;
// 将当前顶点的颜色标记为其父节点的颜色相反
color[u] = 1 - color[v];
// 如果以顶点v为根的子树不是二分图
if (!isBipartite(adj, u, visited, color))
return false;
}
// 如果两个相邻的顶点使用相同的颜色，则图不是二分图
else if (color[u] == color[v])
return false;
}
return true;
}
// 主函数
public static void main(String args[])
{
// 节点数
int N = 6;
// 为图维护邻接表
ArrayList<
ArrayList<Integer>> adj = new ArrayList<
ArrayList<Integer>>(N + 1);
// 初始化所有顶点
for(int i = 0; i <= N; i++)
{
adj.add(new ArrayList<Integer>());
}
// 为了标记节点是否被发现
boolean visited[] = new boolean[N + 1];
// 用两种颜色为图的顶点着色
int color[] = new int[N + 1];
// 颜色数组colorArr[i]的值为'-1'表示顶点'i'没有被赋颜色，值为1表示赋予了第一种颜色，值为0表示赋予了第二种颜色。
Arrays.fill(color, -1);
// 向图中添加边
addEdge(adj, 1, 2);
addEdge(adj, 2, 3);
addEdge(adj, 3, 4);
addEdge(adj, 4, 5);
addEdge(adj, 5, 6);
addEdge(adj, 6, 1);
// 标记起始节点为已访问
visited[1] = true;
// 用颜色标记起始节点
color[1] = 0;
// 检查图是否为二分图的函数
if (isBipartite(adj, 1, visited, color))
{
System.out.println("该图为二分图");
}
else
{
System.out.println("该图不是二分图");
}
}
}
// 本代码由adityapande88贡献
# 使用DFS检查连接的图是否为二分图的Python3程序
# 存储连接节点的函数
def addEdge(adj, u, v):
adj[u].append(v)
adj[v].append(u)
# 检查图是否为二分图的函数
def isBipartite(adj, v, visited, color):
for u in adj[v]:
# 如果顶点u在之前没有被探索过
if (visited[u] == False):
# 将当前节点标记为已访问
visited[u] = True
# 将该节点的颜色设置成与其父节点相反的颜色
color[u] = not color[v]
# 如果以顶点v为根的子树不是二分图
if (not isBipartite(adj, u, visited, color)):
return False
# 如果两个相邻节点被着相同的颜色，则该图不是二分图
elif (color[u] == color[v]):
return False
return True
# 驱动程序
if __name__=='__main__':
# 节点数
N = 6
# 维护图的邻接表
adj = [[] for i in range(N + 1)]
# 用于检查某个节点是否被探索过
visited = [0 for i in range(N + 1)]
# 用两种颜色对图的顶点进行着色
color = [0 for i in range(N + 1)]
# 向图中添加边
addEdge(adj, 1, 2)
addEdge(adj, 2, 3)
addEdge(adj, 3, 4)
addEdge(adj, 4, 5)
addEdge(adj, 5, 6)
addEdge(adj, 6, 1)
# 将源节点标记为已访问
visited[1] = True
# 用一种颜色标记源节点
color[1] = 0
# 检查图是否为二分图的函数
if (isBipartite(adj, 1, visited, color)):
print("该图为二分图")
else:
print("该图不是二分图")
// 使用 DFS 检查连接图是否为二分图的 C# 程序
using System;
using System.Collections.Generic;
class GFG{
// 存储相连节点的函数
static void addEdge(List<List<int>> adj, int u, int v)
{
adj[u].Add(v);
adj[v].Add(u);
}
// 检查图是否为二分图的函数
static bool isBipartite(List<List<int>> adj, int v, bool []visited, int []color)
{
foreach(int u in adj[v])
{
// 如果顶点 u 尚未被探索
if (visited[u] == false)
{
// 标记当前顶点为已访问
visited[u] = true;
// 标记其颜色与其父节点相反
color[u] = 1 - color[v];
// 如果以顶点 v 为根的子树不是二分图
if (!isBipartite(adj, u, visited, color))
return false;
}
// 如果相邻节点用相同的颜色着色，则不是二分图
else if (color[u] == color[v])
return false;
}
return true;
}
// 主函数
public static void Main(String []args)
{
// 节点数
int N = 6;
// 维护图的邻接列表
List<List<int>> adj = new List<List<int>>(N + 1);
// 初始化所有顶点
for(int i = 0; i <= N; i++)
{
adj.Add(new List<int>());
}
// 用于检查节点是否已被发现
bool []visited = new bool[N + 1];
// 用 2 种颜色着色图的各个顶点
int []color = new int[N + 1];
// 颜色数组中的值“-1”表示未分配顶点“i”的任何颜色。值“1”用于指示已分配第一个颜色，而值“0”表示已分配第二个颜色。
for(int i = 0; i <= N; i++)
color[i] = -1;
// 添加边到图中
addEdge(adj, 1, 2);
addEdge(adj, 2, 3);
addEdge(adj, 3, 4);
addEdge(adj, 4, 5);
addEdge(adj, 5, 6);
addEdge(adj, 6, 1);
// 标记源节点为已访问
visited[1] = true;
// 以颜色标记源节点
color[1] = 0;
// 检查图是不是二分图的函数
if (isBipartite(adj, 1, visited, color))
{
Console.WriteLine("Graph is Bipartite");
}
else
{
Console.WriteLine("Graph is not Bipartite");
}
}
}
// 本代码由 Princi Singh 贡献
<script>
// Javascript程序：使用DFS检查连接的图形是二部图还是不是
// 存储连接节点的函数
function addEdge(adj, u, v)
{
adj[u].push(v);
adj[v].push(u);
}
// 检查图形是否为二部图的函数
function isBipartite(adj, v, visited, color)
{
adj[v].forEach(u => {
// 如果顶点u以前没有探索过
if (visited[u] == false) {
// 将当前顶点标记为已访问
visited[u] = true;
// 将其颜色标记为与其父节点相反的颜色
color[u] = !color[v];
// 如果以顶点 v 为根的子树不是二部图
if (!isBipartite(adj, u, visited, color))
return false;
}
// 如果相邻的两个顶点颜色相同，则该图不是二部图
else if (color[u] == color[v])
return false;
});
return true;
}
// 驱动代码
// 节点数量
var N = 6;
// 用于维护图的邻接表
var adj = Array.from(Array(N+1), ()=>Array());
// 用于检查节点是否被发现
var visited = Array(N+1);;
// 用于将图形节点涂上2种颜色
var color = Array(N+1);
// 向图形中添加边缘
addEdge(adj, 1, 2);
addEdge(adj, 2, 3);
addEdge(adj, 3, 4);
addEdge(adj, 4, 5);
addEdge(adj, 5, 6);
addEdge(adj, 6, 1);
// 将源节点标记为已访问
visited[1] = true;
// 将源节点涂上颜色
color[1] = 0;
// 检查图形是否为二部图的函数
if (isBipartite(adj, 1, visited, color)) {
document.write( "Graph is Bipartite");
}
else {
document.write( "Graph is not Bipartite");
}
</script>```
**输出**
```cpp
Graph is Bipartite
时间复杂度:
- 时间复杂度： O(N)
- 辅助空间: O(N)