breadth first search in Golang

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

BFS คืออะไร?

Breadth First Search เป็นรูปแบบหนึ่งของการเดินทางผ่าน (traversal algorithm) ที่เริ่มจากโหนดราก (root node) และสำรวจทุกโหนดในทุกระดับก่อนที่จะขยับไปยังระดับถัดไป มันใช้เทคนิคของ Queue เพื่อจัดการกับการอ่านโหนดที่ร้อนเย็นตามลำดับ Breadth First Search เป็นวิธีที่ดีในการค้นหาเส้นทางหรือเพลินเพลินวัตถุจากต้นไม้หรือกราฟที่เกี่ยวข้องกับการหา Shortest Path หรือการทำ Graph Connectivity

ใน Golang, สามารถใช้แพ็คเกจ "container/list" เพื่อสร้าง queue ซึ่งใช้ในการทำ BFS ได้ ต่อไปนี้เป็นตัวอย่างของ code ที่ใช้ BFS:

package main

import (
	"container/list"
	"fmt"
)

// Graph แทนกราฟด้วยรายการของ edges
type Graph struct {
	vertices int
	edges    map[int][]int
}

// NewGraph สร้างกราฟใหม่
func NewGraph(v int) *Graph {
	return &Graph{
		vertices: v,
		edges:    make(map[int][]int),
	}
}

// AddEdge เพิ่มขอบเข้าไปในกราฟ
func (g *Graph) AddEdge(v, w int) {
	g.edges[v] = append(g.edges[v], w)
}

// BFS ดำเนินการค้นหา BFS จากจุดเริ่มต้น
func (g *Graph) BFS(startingNode int) {
	visited := make(map[int]bool)
	queue := list.New()

	visited[startingNode] = true
	queue.PushBack(startingNode)

	for queue.Len() > 0 {
		vertex := queue.Remove(queue.Front()).(int)
		fmt.Printf("%v ", vertex)

		for _, w := range g.edges[vertex] {
			if !visited[w] {
				visited[w] = true
				queue.PushBack(w)
			}
		}
	}
}

func main() {
	graph := NewGraph(4)
	graph.AddEdge(0, 1)
	graph.AddEdge(0, 2)
	graph.AddEdge(1, 2)
	graph.AddEdge(2, 0)
	graph.AddEdge(2, 3)
	graph.AddEdge(3, 3)

	fmt.Println("Breadth First Search starting from vertex 2:")
	graph.BFS(2)
}

ในโลกจริง BFS มีกรณีการใช้ (use cases) ในหลากหลายสถานการณ์ เช่น ในเกมส์หาทางออกจาก Maze, สำหรับเครือข่ายโซเชียลเพื่อค้นหาความสัมพันธ์ระดับกันเฟรนด์, ในโลกอินเทอร์เน็ตใช้สำหรับระบบชือด้วย Web Crawler ในการสร้าง Search Engine Index หรือ Plotting Points of interest on Maps และอื่น ๆ

Complexity ของ BFS มี Time Complexity อยู่ที่ O(V + E) โดยที่ V คือจำนวนโหนดและ E คือจำนวนขอบ และ Space Complexity คือ O(V) เพราะมันเก็บรายการของ vertices ที่ได้เยี่ยมชมแล้ว

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

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

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