BFS 廣度優先

Breadth-first search

是一種圖形搜尋演算法。簡單的說，BFS 是從根節點開始，沿著樹的寬度遍歷樹的節點。如果所有節點均被訪問，則演算法中止。廣度優先搜尋的實現一般採用 open-closed 表。

// build graph:
//     A
//    / \
//   B   C
//  / \   \
// D   E   F
fun main() {
    val nodeA = Node("A")
    val nodeB = Node("B")
    val nodeC = Node("C")
    val nodeD = Node("D")
    val nodeE = Node("E")
    val nodeF = Node("F")

    nodeA.neighbors.apply {
		add(nodeB)
		add(nodeC)
	}
    nodeB.neighbors.apply {
	    add(nodeD)
	    add(nodeE)
    }
    nodeC.neighbors.add(nodeF)

    bfs(nodeA) // 訪問圖的節點
}

fun bfs(start: Node) {
    val queue: Queue<Node> = LinkedList(listOf(start))
    val visited = mutableSetOf<Node>(start)

    while (queue.isNotEmpty()) {
        val current = queue.poll()
        println("Visiting node: ${current.name}")

        for (neighbor in current.neighbors) {
            if (neighbor !in visited) {
                queue.add(neighbor)
                visited.add(neighbor)
                println("  - Queueing node: ${neighbor.name}")
            }
        }
    }
}

class Node(val name: String) {
    val neighbors = mutableListOf<Node>()
}