資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 Python 查詢無向圖中是否存在給定大小的獨立集
假設我們有一個給定的無向圖；我們需要檢查它是否包含大小為 l 的獨立集。如果存在大小為 l 的獨立集，則返回“Yes”，否則返回“No”。
我們需要記住，圖中的獨立集定義為一組頂點，這些頂點彼此之間沒有直接連線。
所以，如果輸入類似於 L = 4，
那麼輸出將是 yes
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 is_valid()。它將接收圖和陣列 arr 作為引數。
從 i = 0 到 arr 的大小迴圈：
從 j = i + 1 到 arr 的大小迴圈：
如果 graph[arr[i], arr[j]] 等於 1，則：
返回 False
返回 True
定義一個函式 solve()。它將接收圖、陣列 arr、k、索引 index 和陣列 sol 作為引數。
如果 k 等於 0，則：
如果 is_valid(graph, arr) 等於 True，則：
sol[0] := True
返回
否則，
如果 index >= k，則：
返回 (solve(graph, arr[從索引 0 到結束] 連線一個包含 [index] 的列表, k-1, index-1, sol) 或 solve(graph, arr[從索引 0 到結束], k, index-1, sol))
否則，
返回 solve(graph, arr[從索引 0 到結束] 連線一個包含 [index] 的列表, k-1, index-1, sol)
示例
讓我們看看以下實現，以更好地理解：
def is_valid(graph, arr):
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if graph[arr[i]][arr[j]] == 1:
return False
return True
def solve(graph, arr, k, index, sol):
if k == 0:
if is_valid(graph, arr) == True:
sol[0] = True
return
else:
if index >= k:
return (solve(graph, arr[:] + [index], k-1, index-1, sol) or solve(graph, arr[:], k, index-1, sol))
else:
return solve(graph, arr[:] + [index], k-1, index-1, sol)
graph = [
[1, 1, 0, 0, 0],
[1, 1, 1, 1, 1],
[0, 1, 1, 0, 0],
[0, 1, 0, 1, 0],
[0, 1, 0, 0, 1]]
k = 4
arr = []
sol = [False]
solve(graph, arr[:], k, len(graph)-1, sol)
if sol[0]:
print("Yes")
else:
print("No")輸入
[[1, 1, 0, 0, 0], [1, 1, 1, 1, 1], [0, 1, 1, 0, 0], [0, 1, 0, 1, 0], [0, 1, 0, 0, 1]], 4
輸出
Yes
更新於: 2020年8月25日
238 次瀏覽
廣告