กราฟและอัลกอริทึมการเดินทาง (Graph Traversal Algorithms)

กราฟ (Graph)

โครงสร้างข้อมูลแบบ Non-linear ประกอบด้วย Nodes และ Edges ที่เชื่อมต่อ ขอบอาจเป็น Directed หรือ Undirected

แทนได้เป็น G(V, E) เช่น G({A,B,C,D,E}, {(A,B), (B,D), (D,E), (B,C), (C,A)})

Breadth First Search (BFS)

อัลกอริทึมเยี่ยมชมทุกโหนด เลือกโหนดหนึ่ง แล้วเยี่ยมเพื่อนบ้านทีละตัว จบเพื่อนบ้านแล้วค่อยไปโหนดถัดไป

อัลกอริทึม BFS

bfs(vertices, start)
  define empty queue que
  mark all nodes unvisited
  add start to que
  while que not empty:
    delete from que → u
    display u
    for all vertices i adjacent to u:
      if vertices[i] unvisited:
        mark temporarily visited
        add to queue
    mark u completely visited

Depth First Search (DFS)

อัลกอริทึมเดินทางกราฟ ให้โหนดเริ่มต้น พบเพื่อนบ้าน → เดินไปเพื่อนบ้านนั้นก่อน แล้วค่อยทำต่อในลักษณะเดียวกัน

อัลกอริทึม DFS

dfs(vertices, start)
  mark all nodes unvisited
  push start to stack
  while stack not empty:
    pop from stack → u
    display u
    if u not visited:
      mark u visited
      for all nodes i connected to u:
        if i unvisited:
          push i to stack
          mark i visited