โปรแกรมตรวจสอบว่ามีโหนดร่วมที่ไปถึงได้ในกราฟหรือไม่ใน Python

สมมติว่าเรามีรายการขอบ (edge list) ของกราฟทิศทาง มี n โหนด ชื่อโหนดคือ 0 ถึง n-1 เรายังมีค่าจำนวนเต็มสองค่า a และ b เราต้องตรวจสอบว่ามีโหนด c ใดๆ ที่สามารถไปจาก c ไป a และจาก c ไป b ได้หรือไม่

เช่น ถ้าอินพุตเป็นกราฟดังภาพ และ a = 2, b = 3 ผลลัพธ์จะเป็น True เพราะ c = 0 มีเส้นทางจาก 0 ไป 2 และ 0 ไป 3

ขั้นตอนการแก้ปัญหา

1. กำหนดฟังก์ชัน DFS(graph, node, visited):
   • ถ้า node ยังไม่ได้เยี่ยมชม:
     • ทำเครื่องหมาย node ว่าเยี่ยมชมแล้ว
     • สำหรับแต่ละ x ใน graph[node] เรียก DFS(graph, x, visited)
2. จากเมธอดหลัก:
   • graph := สร้าง adjacency list จาก edge_list
   • visited_a, visited_b := เซตว่างสองเซต
   • DFS(graph, a, visited_a), DFS(graph, b, visited_b)
   • ans := รายการใหม่จาก intersection ของ visited_b และ visited_a
   • ถ้า ans ไม่ว่าง คืนค่า True
   • คืนค่า False

ตัวอย่างการใช้งาน

def edge_list_to_graph(edges):
    s = set()
    for x, y in edges:
        s.add(x)
        s.add(y)
    s = len(list(s))
    graph = [[] for x in range(s)]
    for x, y in edges:
        graph[y].append(x)
    return graph

def DFS(graph, node, visited):
    if node not in visited:
        visited.add(node)
        for x in graph[node]:
            DFS(graph, x, visited)

def solve(edges, a, b):
    graph = edge_list_to_graph(edges)
    visited_a, visited_b = set(), set()
    DFS(graph, a, visited_a)
    DFS(graph, b, visited_b)
    ans = list(visited_a.intersection(visited_b))
    if ans:
        return True
    return False

ed_list = [(0, 4), (4, 3), (1, 2), (0, 1), (0, 2), (1, 1)]
a = 2
b = 3
print(solve(ed_list, a, b))

อินพุต

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

เอาต์พุต

True