在Python中找出图形中的关键边和虚关键边的程序

在Python中找出图形中的关键边和虚关键边的程序

假设我们有一个包含从0到n-1编号的n个顶点的图形。该图是无向的,每条边都有一个权重。因此,给定图形后,我们必须找出图形的MST(最小生成树)中的关键边和虚关键边。如果删除该边会导致MST权重增加,则称该边为关键边。伪关键边是一条边,它可以出现在所有图形的MST中,但并非所有图形。我们找出给定图形作为输入的边的索引。

因此,如果输入如下:

在Python中找出图形中的关键边和虚关键边的程序

并且顶点数为5,则输出将是[[], [0, 1, 2, 3, 4]]。给定图形中没有关键边,所有边都是伪关键边。由于所有边的权重相同,从图形中任选3条边都可以构成MST。

要解决这个问题,我们将按以下步骤操作−

  • 定义一个函数find_mst(),它将带有num_vertices、graph、init := null、exl := null

  • 定义一个帮助函数visit(),它将以u为参数

  • k[u] := True

  • 对于图形[u,空列表]中的每个v、w,执行以下操作:

    • 如果exl和u在exl中,v也在,则
      • 转到下一个迭代
    • 如果not k[v] is True,则
      • 将三元组(w,u,v)推入堆tmp中
  • res := 0

  • k :=一个新的大小为num_arrays的列表,其值均为False

  • tmp :=一个新的堆

  • 如果init非空,则

    • u:= init

    • v:= init

    • w:= init

    • res := res + w

    • k[u] := True

    • k[v] := True

    • visit(u)或visit(v)

  • 否则,

    • visit(0)
  • 当tmp不为空时,执行以下操作:
    • 从堆tmp中弹出最小的项,w:= pop

    • 从堆tmp中弹出最小的项,u:= pop

    • 从堆tmp中弹出最小的项,v:= pop

    • 如果k[u]和k[v]都不为零,则

      • 转到下一个迭代
    • res := res + w

    • 如果not k[u] is True,则

      • visit(u)
    • 如果not k[v] is True,则
      • visit(v)
  • 如果k中所有值都为True,则返回res,否则返回无穷大

  • 从主方法中执行以下操作:

  • graph :=给定图形

  • temp :=find_mst(num_vertices, graph)

  • c_edge :=一个新的列表

  • p_edge :=一个新的列表

  • 对于i在范围0到边的大小之间,执行以下操作

    • 如果find_mst(num_vertices, graph, exl = edges[i,index 2 to end]) > temp,则
      • 在c_edge末尾插入i
    • 否则,如果find_mst(num_vertices, graph, init = edges[i])与temp相同,则
      • 在p_edge末尾插入i
  • 返回[c_edge,p_edge]

示例

让我们看一下以下实现,以更好地理解。

from heapq import heappop, heappush
def solve(num_vertices, edges):
   graph = dict()
   for u, v, w in edges:
      graph.setdefault(u, []).append((v, w))
      graph.setdefault(v, []).append((u, w))
   temp = find_mst(num_vertices, graph)
   c_edge, p_edge = [], []
   for i in range(len(edges)):
      if find_mst(num_vertices, graph, exl = edges[i][:2]) > temp:
         c_edge.append(i)
      elif find_mst(num_vertices, graph, init = edges[i]) == temp:
         p_edge.append(i)
   return [c_edge, p_edge]


def find_mst(num_vertices, graph, init = None, exl = None):
   def visit(u):
      k[u] = True
      for v, w in graph.get(u, []):
         if exl and u in exl and v in exl:
            continue
         if not k[v]:
            heappush(tmp, (w, u, v))
   res = 0
   k = [False] * num_vertices
   tmp = []
   if init:
      u, v, w = init
      res += w
      k[u] = k[v] = True
      visit(u) or visit(v)
   else:
      visit(0)

   while tmp:
      w, u, v = heappop(tmp)
      if k[u] and k[v]: continue
      res += w
      if not k[u]:
         visit(u)
      if not k[v]:
         visit(v)

   return res if all(k) else inf

print(solve(5, [[0,1,10],[1,2,10],[2,3,10],[3,4,10],[4,0,10]]))

输入

5, [[0,1,10],[1,2,10],[2,3,10],[3,4,10],[4,0,10]]

输出

[[], [0, 1, 2, 3, 4]]

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程