資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式檢查給定圖是否為二分圖
假設我們有一個無向圖，我們需要檢查該圖是否為二分圖。眾所周知，當我們可以將圖的節點分成兩個集合 A 和 B，並且圖中的每條邊 {u,v} 都有一個節點 u 在 A 中，另一個節點 v 在 B 中時，該圖就是二分圖。
所以，如果輸入是這樣的
那麼輸出將是 True，[0,4] 在集合 A 中，[1,2,3] 在集合 B 中，並且所有邊都從 A 到 B 或 B 到 A，而不是 A 到 A 或 B 到 B。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 dfs()。這將獲取源節點
對於graph[source]中的每個頂點，執行以下操作：
如果color[vertex]不等於 -1，則
如果color[vertex]與color[source]相同，則
result[0] := False
返回
繼續下一個迭代
color[vertex] := 1 - color[source]
dfs(vertex)
從主方法中，執行以下操作：
n := arr的大小
graph := 頂點 0 到 n-1 的空鄰接表
對於範圍 0 到 n 中的 i，執行以下操作：
對於arr[i]中的每個 j，執行以下操作：
將 i 插入到 graph[j] 中
將 j 插入到 graph[i] 中
color := 一個大小為 n 的列表，並填充為 -1
result := 一個包含一個 True 值的列表
對於範圍 0 到 n 中的 i，執行以下操作：
如果color[i]與 -1 相同，則
dfs(i)
返回result[0]
讓我們看看以下實現以獲得更好的理解：
示例
from collections import defaultdict class Solution: def solve(self, arr): n = len(arr) graph = [set() for i in range(n)] for i in range(n): for j in arr[i]: graph[j].add(i) graph[i].add(j) color = [-1] * n result = [True] def dfs(source): for child in graph[source]: if color[child] != -1: if color[child] == color[source]: result[0] = False return continue color[child] = 1 - color[source] dfs(child) for i in range(n): if color[i] == -1: dfs(i) return result[0] ob = Solution() graph = [[1,2,3],[0],[0,4],[0,4],[2,3]] print(ob.solve(graph))
輸入
graph = [[1,2,3],[0],[0,4],[0,4],[2,3]]
輸出
True
更新於: 2020年10月5日
671 次檢視
廣告