在 Python 中查找无向图是否包含给定大小的独立集

pythonserver side programmingprogramming更新于 2025/10/10 8:44:17

假设我们有一个给定的无向图;我们必须检查它是否包含大小为 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

相关文章


有用资源