สมมุติว่าเรามีกราฟดาวแบบไม่มีทิศทางหนึ่งกราฟที่มีโหนด n ตัวกำกับอยู่ตั้งแต่ 1 ถึง n อย่างที่เราทราบกันดีว่ากราฟดาวคือกราฟที่มีโหนดกลางหนึ่งโหนดและขอบ n-1 ที่เชื่อมต่อโหนดกลางกับโหนดอื่นทุกโหนด เราต้องหาจุดศูนย์กลางของกราฟดาวที่กำหนด
ดังนั้นหากอินพุตเป็นแบบ
แล้วเอาท์พุตจะเป็น 3 เนื่องจาก 3 อยู่ตรงกลาง
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
เห็นแล้ว :=ชุดใหม่
-
สำหรับแต่ละขอบ (u,v) ในกราฟ ทำ
-
ถ้าคุณอยู่ในสายตาแล้ว
-
คืนคุณ
-
-
ถ้าเห็น v แล้ว
-
กลับ วี
-
-
แทรกคุณให้เห็น
-
ใส่ v เข้าไป
-
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(graph):
seen = set()
for u,v in graph:
if u in seen:
return u
if v in seen:
return v
seen.add(u)
seen.add(v)
graph = [(1,3),(2,3),(4,3),(5,3),(6,3)]
print(solve(graph)) อินพุต
[(1,3),(2,3),(4,3),(5,3),(6,3)]
ผลลัพธ์
3
