การสำรวจเส้นทางในกราฟด้วย Breadth First Search (BFS) และการใช้งานในภาษา Fortran

 

การค้นหาข้อมูลในกราฟเป็นสิ่งสำคัญที่อยู่ในพื้นฐานของอัลกอริธึมคอมพิวเตอร์ต่างๆ หนึ่งในวิธีที่พบได้บ่อยคือการใช้เทคนิคที่เรียกว่า Breadth First Search (BFS) อัลกอริธึมนี้ช่วยให้เราสำรวจทุกๆ โหนดในกราฟที่อยู่ในระดับเดียวกันก่อนที่จะลงไปสู่ระดับที่ลึกกว่า ซึ่งสามารถใช้ในการค้นหาเส้นทางในกราฟ การวิเคราะห์เครือข่ายสังคม หรือแม้กระทั่งในการสร้างจำลองสถานการณ์ต่างๆ

 

BFS คืออะไร?

**Breadth First Search (BFS)** คืออัลกอริธึมสำหรับการค้นหาในกราฟที่ทำงานโดยการสำรวจโหนดที่อยู่ในระดับเดียวกันก่อน จากนั้นจึงขยายไปสู่โหนดที่อยู่ในระดับถัดไป โดยวิธีการทำงาน BFS จะใช้โครงสร้างข้อมูลแบบ **Queue** เพื่อช่วยในการจัดการกับโหนดที่ต้องการสำรวจ โดยขั้นตอนการทำงานของ BFS มีดังนี้:

1. เริ่มจากโหนดต้น (source node) แล้วเพิ่มเข้าไปใน queue.

2. ขณะ queue ยังไม่ว่าง ให้ทำการดึงโหนดออกมาจาก queue.

3. สำรวจเพื่อนบ้าน (neighbor) ของโหนดที่ดึงออกมา:

- ถ้ายังไม่ถูกสำรวจ ให้เพิ่มเข้าไปใน queue และทำการบันทึก.

4. ทำซ้ำกระบวนการนี้จนกว่า queue จะว่างหมด.

 

ตัวอย่าง Use Case ของ BFS ในโลกจริง

- Social Networks: เมื่อเราต้องการค้นหาความสัมพันธ์ระหว่างคนในเครือข่ายสังคม BFS ช่วยให้เราสามารถค้นหาความสัมพันธ์ในระดับชั้นได้ - Routing Algorithms: ในการค้นหาทางเดินที่สุดระหว่างจุด A และ B ในแผนที่ BFS สามารถช่วยให้สามารถหาทางเข้าไปยังจุดหมายได้อย่างมีประสิทธิภาพ - Web Crawlers: ใช้ BFS ในการค้นหาข้อมูลบนอินเทอร์เน็ต โดยเริ่มจากหน้าหลักแล้วขยายไปยังหน้าต่างๆ ที่เชื่อมโยง

 

ตัวอย่างโค้ด BFS ในภาษา Fortran

ด้านล่างนี้คือการใช้งาน BFS ในภาษา Fortran โดยสมมติว่าเรามีกราฟที่เป็นแบบ adjacency list:

 program bfs_example
  implicit none

  integer, parameter :: max_nodes = 100
  integer :: graph(max_nodes, max_nodes), queue(max_nodes)
  integer :: visited(max_nodes)
  integer :: front, rear, i, start_node, n, total_nodes

  ! Initialize the graph
  data graph / 0, 1, 0, 0, 0, 0, 0, 0, &
               1, 0, 1, 1, 0, 0, 0, 0, &
               0, 1, 0, 0, 0, 0, 0, 0, &
               0, 1, 0, 0, 1, 1, 0, 0, &
               0, 0, 0, 1, 0, 1, 1, 0, &
               0, 0, 0, 1, 1, 0, 0, 0, &
               0, 0, 0, 0, 1, 0, 0, 0, &
               0, 0, 0, 0, 0, 0, 0, 0 /

  ! Initialize visited array
  visited = 0

  ! Set starting node example
  start_node = 1
  total_nodes = 7

  ! BFS
  front = 0
  rear = -1
  rear = rear + 1
  queue(rear + 1) = start_node
  visited(start_node) = 1

  print *, "Breadth First Search starting from node ", start_node
  do while (front <= rear)
    front = front + 1
    print *, "Visited node: ", queue(front)

    do i = 1, total_nodes
      if (graph(queue(front), i) == 1 .and. visited(i) == 0) then
        rear = rear + 1
        queue(rear + 1) = i
        visited(i) = 1
      end if
    end do
  end do
end program bfs_example

ในตัวอย่างข้างต้น เราใช้กราฟจำลองโดยเป็น adjacency matrix และสำรวจกราฟด้วย BFS โดยเริ่มจากโหนดที่กำหนด เราใช้ array `visited` เพื่อช่วยในการติดตามว่าโหนดนั้นๆ ได้ถูกสำรวจหรือยัง โดยพิมพ์โหนดแต่ละโหนดที่ถูกเยี่ยมชมออกมา

 

การวิเคราะห์ Complexity ของ BFS

BFS มีความซับซ้อนทางเวลา (Time Complexity) เท่ากับ O(V + E) โดยที่ V คือจำนวนโหนด (vertices) และ E คือจำนวนขอบ (edges) ในกราฟ นั่นคือ อัลกอริธึมนี้จะทำการสำรวจโหนดทั้งหมดและขอบทั้งหมดที่เชื่อมโยงกัน

ในด้านความซับซ้อนทางพื้นที่ (Space Complexity) จะมีค่าเป็น O(V) เนื่องจากเราใช้ queue ซึ่งต้องเก็บข้อมูลโหนดที่ต้องสำรวจ

 

ข้อดีและข้อเสียของ BFS

ข้อดี:

- ใช้งานง่ายและตรงไปตรงมา

- เหมาะสำหรับการหาค่าที่อยู่ใกล้เคียงหรือเส้นทางที่สั้นที่สุดในกราฟที่มีน้ำหนักเท่ากัน

ข้อเสีย:

- การใช้พื้นที่สูง หากกราฟมีขนาดใหญ่ อาจทำให้หน่วยความจำหมด

- อาจมีประสิทธิภาพต่ำถ้าใช้กับกราฟที่มีน้ำหนัก โดยอาจจำเป็นต้องใช้ Dijkstra’s Algorithm แทน

 

สรุป

การค้นหาเส้นทางในกราฟเป็นเรื่องสำคัญในหลายๆ แวดวง โดย BFS เป็นหนึ่งในเครื่องมือที่จำเป็นและมีประโยชน์มาก อย่างไรก็ตาม ควรใช้มันอย่างระมัดระวังเมื่อเผชิญกับกราฟที่มีขนาดใหญ่หรือมีความซับซ้อนสูง

หากคุณต้องการเรียนรู้เพิ่มเติมเกี่ยวกับการเขียนโปรแกรมและการใช้งานอัลกอริธึม เช่น BFS ด้วยภาษา Fortran หรือภาษาอื่นๆ เราขอเชิญคุณเข้าเรียนที่ Expert-Programming-Tutor (EPT) ที่นี่ เรามีคอร์สที่หลากหลายพร้อมกับอาจารย์ผู้มีประสบการณ์รอช่วยเหลือคุณ! คุณจะได้เรียนรู้การเขียนโค้ดอย่างมีประสิทธิภาพ และนำไปสู่การประยุกต์ใช้ได้อย่างจริงจังในโลกแห่งเทคโนโลยี!

 

 

หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง