เริ่มต้นใช้งานเริ่มต้นใช้งานได้ฟรี

การ implement DFS สำหรับกราฟ

ในแบบฝึกหัดนี้ จะได้ implement อัลกอริทึม depth first search เพื่อท่องไปในกราฟ

ขั้นตอนโดยสรุป:

  1. เริ่มต้นที่ vertex ใดก็ได้
  2. เพิ่ม vertex นั้นลงในรายการ visited vertices
  3. สำหรับแต่ละ adjacent vertex ของ node ปัจจุบัน
    • ถ้าเยี่ยมชมแล้ว -> ข้ามไป
    • ถ้ายังไม่ได้เยี่ยมชม -> เรียก DFS แบบ recursive

เพื่อช่วยในการทดสอบโค้ด กราฟต่อไปนี้ถูกโหลดมาในรูปแบบ dictionary แล้ว

Graphical representation of a graph.

graph = {
  '0' : ['1','2'],
  '1' : ['0', '2', '3'],
  '2' : ['0', '1', '4'],
  '3' : ['1', '4'],
  '4' : ['2', '3']
}

แบบฝึกหัดนี้เป็นส่วนหนึ่งของหลักสูตร

โครงสร้างข้อมูลและอัลกอริทึมใน Python

ดูคอร์ส

คำแนะนำการฝึกหัด

  • ตรวจสอบว่า current_vertex ยังไม่ถูกเยี่ยมชม
  • เพิ่ม current_vertex เข้าไปใน visited_vertices
  • เรียกใช้ dfs() แบบ recursive โดยส่งค่าที่เหมาะสมเข้าไป

แบบฝึกหัดเชิงโต้ตอบแบบลงมือทำ

ลองทำแบบฝึกหัดนี้โดยเติมโค้ดตัวอย่างนี้ให้สมบูรณ์

def dfs(visited_vertices, graph, current_vertex):
    # Check if current_vertex hasn't been visited yet
    if current_vertex not in ____:
        print(current_vertex)
        # Add current_vertex to visited_vertices
        ____.add(____)
        for adjacent_vertex in graph[current_vertex]:
            # Call recursively with the appropriate values
            ____(____, ____, ____)
            
dfs(set(), graph, '0')
แก้ไขและรันโค้ด