判断二分图
00 min
2024-7-17
2024-7-17
type
status
date
slug
summary
tags
category
icon
password
 

题目:判断二分图

 
存在一个 无向图 ,图中有 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 。
 
示例 1:
notion image
 
示例 2:
notion image
 
提示:
  • graph.length == n
  • 1 <= n <= 100
  • 0 <= graph[u].length < n
  • 0 <= graph[u][i] <= n - 1
  • graph[u] 不会包含 u
  • graph[u] 的所有值 互不相同
  • 如果 graph[u] 包含 v,那么 graph[v] 也会包含 u
 

题解

要判断一个无向图是否为二分图,我们可以采用染色法。基本思路是给每个节点分配两种颜色之一,使得没有两个相邻的节点拥有相同的颜色。如果能够以这种方式成功地为图中的所有节点着色,那么这个图就是二分图。实现步骤如下:
初始化一个数组 colors 来存储每个节点的颜色。0 值表示节点尚未着色,1-1 将代表两种不同的颜色。 遍历每个节点。如果节点未着色,则用一种颜色(比如 1)着色,然后使用深度优先搜索(DFS)或广度优先搜索(BFS)为所有相邻节点着上另一种颜色(-1)。 在 DFSBFS 过程中,如果发现一个相邻节点已经被着上了与当前节点相同的颜色,则图不能被划分为二分图,返回 false。 如果成功为图中的所有节点着色而没有冲突,返回 true
以下是使用 BFS 实现的 JavaScript 代码示例:
 

附录

 
上一篇
超级回文数
下一篇
统计美丽子字符串 II