โปรแกรมค้นหาขอบวิกฤตและวิกฤตหลอกในกราฟใน Python

สมมติว่าเราได้รับกราฟที่มีจุดยอด n จุดที่มีตัวเลข 0 ถึง n -1 กราฟไม่มีทิศทางและแต่ละขอบมีน้ำหนัก จากกราฟ เราต้องหาขอบวิกฤตและขอบวิกฤตหลอกในกราฟ MST ขอบจะเรียกว่าขอบวิกฤต หากการลบขอบนั้นทำให้น้ำหนัก MST เพิ่มขึ้น ขอบวิกฤตหลอกคือขอบที่สามารถปรากฏในกราฟ MST ทั้งหมดได้ แต่ไม่ใช่ทั้งหมด เราหาดัชนีของขอบจากกราฟเป็นอินพุต

ดังนั้นหากอินพุตเป็นแบบ

และจำนวนจุดยอดคือ 5 จากนั้นผลลัพธ์จะเป็น [[], [0, 1, 2, 3, 4]]ไม่มีขอบวิกฤตในกราฟที่กำหนดและขอบทั้งหมดนั้นวิกฤตหลอก เนื่องจากขอบทั้งหมดมีน้ำหนักเท่ากัน ขอบทั้ง 3 มุมจากกราฟจะสร้าง MST

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน find_mst() สิ่งนี้จะใช้เวลา num_vertices, กราฟ, init :=null, exl :=null

• กำหนดฟังก์ชันตัวช่วยหนึ่งตัว visit() สิ่งนี้จะพาคุณ

• k[u] :=จริง

• สำหรับแต่ละ v, w ในกราฟ[u, รายการว่าง], ทำ

  • ถ้า exl และ u อยู่ใน exl และ v อยู่ใน exl แล้ว

    • ไปทำซ้ำต่อไป

  • ถ้าไม่ใช่ k[v] จะเป็น True แล้ว

    • ดัน triplet (w,u,v) เข้าไปใน heap tmp

• res :=0

• k :=รายการใหม่ของขนาด num_arrays ที่มีค่าเป็นเท็จ

• tmp :=ฮีปใหม่

• ถ้า init เป็น non-null แล้ว

  • u :=เริ่มต้น

  • v :=เริ่มต้น

  • w :=init

  • res :=res + w

  • k[u] :=จริง

  • k[v] :=จริง

  • เยี่ยมชม (u) หรือเยี่ยมชม (v)

• มิฉะนั้น

  • เยี่ยมชม(0)

• ในขณะที่ tmp ไม่ว่างเปล่าให้ทำ

  • w :=ป๊อปรายการที่เล็กที่สุดจาก heap tmp

  • u :=ป๊อปรายการที่เล็กที่สุดจาก heap tmp

  • v :=ป๊อปรายการที่เล็กที่สุดจาก heap tmp

  • ถ้า k[u] และ k[v] ไม่ใช่ศูนย์ ดังนั้น

    • ไปทำซ้ำต่อไป

  • res :=res + w

  • ถ้าไม่ใช่ k[u] จะเป็น True แล้ว

    • มาเยี่ยม(u)

  • ถ้าไม่ใช่ k[v] จะเป็น True แล้ว

    • เยี่ยมชม(v)

• คืนค่า res หาก k ทั้งหมดเป็น True ไม่เช่นนั้นให้คืนค่าอนันต์

• จากวิธีหลัก ให้ทำดังนี้:

• กราฟ :=กราฟที่กำหนด

• temp :=find_mst(num_vertices, กราฟ)

• c_edge :=รายการใหม่

• p_edge :=รายการใหม่

• สำหรับผมอยู่ในช่วง 0 ถึงขนาดของขอบ ทำ

  • ถ้า find_mst(num_vertices, graph, exl =edge[i, index 2 to end])> temp แล้ว

    • ใส่ i ที่ท้าย c_edge

  • มิฉะนั้น ถ้า find_mst(num_vertices, graph, init =Edge[i]) เหมือนกับ temp แล้ว

    • ใส่ i ที่ท้าย p_edge

• กลับ [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]]