สมมติว่าเรามีรายการขอบของกราฟกำกับ มี n โหนด และชื่อโหนดคือ 0 ถึง n- 1 นอกจากนี้เรายังมีค่าจำนวนเต็มสองค่า a และ b เราต้องตรวจสอบว่ามีโหนดใดที่เราสามารถไปจาก c ถึง a และ c ถึง b ได้หรือไม่
ดังนั้นหากอินพุตเป็นแบบ
และ a =2, b =3 แล้วผลลัพธ์จะเป็น True เพราะที่นี่ c =0 ดังนั้นเราจึงมีเส้นทางจาก 0 ถึง 2 และ 0 ถึง 3 ด้วย
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดฟังก์ชัน DFS() นี่จะใช้เวลากราฟ โหนด เยี่ยมชม
- ถ้าโหนดไม่ได้รับการเยี่ยมชมแล้ว
- ทำเครื่องหมายโหนดว่าเข้าชมแล้ว
- สำหรับแต่ละ x ในกราฟ[โหนด] ทำ
- DFS(กราฟ, x, เข้าชมแล้ว)
- จากวิธีหลัก ให้ทำดังต่อไปนี้ −
- กราฟ :=สร้างรายการที่อยู่ติดกันจาก edge_list
- visited_a, visit_b :=ชุดว่างสองชุด
- DFS(กราฟ, a, visit_a)
- DFS(กราฟ, b, visit_b)
- ans :=รายการใหม่จากสี่แยก visit_b และ visit_a
- ถ้าไม่ว่างก็
- คืนค่า True
- คืนค่าเท็จ
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
