在 Python 中查找无向图是否包含给定大小的独立集
假设我们有一个给定的无向图;我们必须检查它是否包含大小为 l 的独立集。如果存在大小为 l 的任何独立集,则返回"是",否则返回"否"。
我们必须记住,图中的独立集定义为一组不直接相互连接的顶点。
因此,如果输入为 L = 4,

则输出为是
为了解决这个问题,我们将遵循以下步骤 −
定义一个函数 is_valid() 。这将获取 graph, arr
对于 i 在 0 到 arr 大小的范围内,执行
对于 j 在 i + 1 到 arr 大小的范围内,执行
如果 graph[arr[i], arr[j]] 与 1 相同,则
返回 False
返回 True
定义一个函数 resolve() 。这将采用 graph、arr、k、index、sol
如果 k 与 0 相同,则
如果 is_valid(graph, arr) 与 True 相同,则
sol[0] := True
返回
否则,
如果 index >= k,则
return(solve(graph, arr[from index 0 to end] concatenate a list with [index], k-1, index-1, sol) or solve(graph, arr[from index 0 to end], k, index-1, sol))
否则,
return solve(graph, arr[from index 0 to end] concatenate a list with [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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

