Pythonのグラフでクリティカルエッジと疑似クリティカルエッジを見つけるプログラム

0からn-1までの番号が付けられたn個の頂点を含むグラフが与えられたとします。グラフは無向であり、各エッジには重みがあります。したがって、グラフが与えられた場合、グラフMSTのクリティカルエッジと疑似クリティカルエッジを見つける必要があります。エッジを削除するとMSTの重みが増加する場合、そのエッジはクリティカルエッジと呼ばれます。疑似クリティカルエッジは、すべてではなく、すべてのグラフMSTに表示できるエッジです。グラフを入力として与えられたエッジのインデックスを見つけます。

したがって、入力が次のような場合

頂点の数が5の場合、出力は[[]、[0、1、2、3、4]]になります。指定されたグラフにはクリティカルエッジがなく、すべてのエッジが疑似クリティカルです。すべてのエッジの重みが同じであるため、グラフの3つのエッジがMSTになります。

これを解決するには、次の手順に従います-

• 関数find_mst（）を定義します。これには、num_vertices、graph、init：=null、exl：=null

  が必要です。

• 1つのヘルパー関数visit（）を定義します。これにはuがかかります

• k [u]：=True

• グラフ[u、空のリスト]の各v、w inに対して、実行

  • exlとuがexlにあり、vがexlにある場合、

    • 次のイテレーションに行く

  • k [v]がTrueでない場合、

    • トリプレット（w、u、v）をヒープtmpにプッシュします

• res：=0

• k：=値Falseを含むサイズnum_arraysの新しいリスト

• tmp：=新しいヒープ

• initがnullでない場合、

  • u：=init

  • v：=init

  • w：=init

  • res：=res + w

  • k [u]：=True

  • k [v]：=True

  • visit（u）またはvisit（v）

• それ以外の場合

  • visit（0）

• tmpが空でない間は、実行してください

  • w：=ヒープtmpから最小のアイテムをポップ

  • u：=ヒープtmpから最小のアイテムをポップ

  • v：=ヒープtmpから最小のアイテムをポップ

  • k[u]およびk[v]がゼロ以外の場合、

    • 次のイテレーションに行く

  • res：=res + w

  • k [u]がTrueでない場合、

    • visit（u）

  • k [v]がTrueでない場合、

    • visit（v）

• kがすべてTrueの場合はresを返し、そうでない場合は無限大を返します

• mainメソッドから、次の手順を実行します。

• グラフ：=与えられたグラフ

• temp：=find_mst（num_vertices、graph）

• c_edge：=新しいリスト

• p_edge：=新しいリスト

• 0からエッジのサイズまでの範囲のiの場合、実行します

  • find_mst（num_vertices、graph、exl =edge [i、index 2 to end]）> tempの場合、

    • c_edgeの最後にiを挿入します

  • それ以外の場合、find_mst（num_vertices、graph、init =edge [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]]