幅優先探索 (BFS)

1from collections import deque2
3
4def bfs(graph, start):5    visited = {start}6    queue = deque([start])7    order = []8    while queue:9        node = queue.popleft()10        order.append(node)11        for neighbor in graph[node]:12            if neighbor not in visited:13                visited.add(neighbor)  # mark on enqueue, not dequeue14                queue.append(neighbor)15    return order16
17
18graph = {19    "A": ["B", "C"],20    "B": ["D", "E"],21    "C": ["F"],22    "D": [],23    "E": ["F"],24    "F": [],25}26
27print("BFS order:", " -> ".join(bfs(graph, "A")))

1const graph = {2    A: ["B", "C"],3    B: ["D", "E"],4    C: ["F"],5    D: [],6    E: ["F"],7    F: [],8};9
10function bfs(start) {11    const visited = new Set([start]);12    const queue = [start];13    const order = [];14    while (queue.length > 0) {15        const node = queue.shift(); // Dequeue the oldest node16        order.push(node);17        for (const next of graph[node]) {18            if (!visited.has(next)) {19                visited.add(next);20                queue.push(next);21            }22        }23    }24    return order;25}26
27console.log("BFS from A:", bfs("A").join(" -> "));

1import java.util.ArrayDeque;2import java.util.List;3import java.util.Queue;4
5public class Main {6    public static void main(String[] args) {7        List<List<Integer>> adj = List.of(8            List.of(1, 2),    // neighbors of 09            List.of(0, 3, 4), // neighbors of 110            List.of(0, 5),11            List.of(1),12            List.of(1, 5),13            List.of(2, 4)14        );15        boolean[] visited = new boolean[adj.size()];16        Queue<Integer> queue = new ArrayDeque<>();17        visited[0] = true;18        queue.add(0);19
20        StringBuilder order = new StringBuilder("BFS from 0:");21        while (!queue.isEmpty()) {22            int node = queue.poll();23            order.append(" ").append(node);24            // Mark neighbors when enqueued so nothing enters twice25            for (int next : adj.get(node)) {26                if (!visited[next]) {27                    visited[next] = true;28                    queue.add(next);29                }30            }31        }32        System.out.println(order);33    }34}

1#include <iostream>2#include <queue>3#include <vector>4
5void bfs(int start, const std::vector<std::vector<int>>& adj) {6    std::vector<bool> visited(adj.size(), false);7    std::queue<int> frontier;8    visited[start] = true;9    frontier.push(start);10    // Visit nodes level by level11    while (!frontier.empty()) {12        int node = frontier.front();13        frontier.pop();14        std::cout << node << " ";15        for (int next : adj[node]) {16            if (!visited[next]) {17                visited[next] = true;18                frontier.push(next);19            }20        }21    }22}23
24int main() {25    // 6-node undirected graph as an adjacency list26    std::vector<std::vector<int>> adj = {27        {1, 2},     // 028        {0, 3, 4},  // 129        {0, 5},     // 230        {1},        // 331        {1, 5},     // 432        {2, 4},     // 533    };34    std::cout << "BFS from node 0: ";35    bfs(0, adj);36    std::cout << "\n";37    return 0;38}

1#include <stdbool.h>2#include <stdio.h>3
4#define N 65
6void bfs(int start, const int adj[N][N]) {7    bool visited[N] = {false};8    int queue[N];  // fixed-size queue: head chases tail9    int head = 0, tail = 0;10    visited[start] = true;11    queue[tail++] = start;12    // Visit nodes level by level13    while (head < tail) {14        int node = queue[head++];15        printf("%d ", node);16        for (int next = 0; next < N; next++) {17            if (adj[node][next] && !visited[next]) {18                visited[next] = true;19                queue[tail++] = next;20            }21        }22    }23}24
25int main(void) {26    // 6-node undirected graph as an adjacency matrix27    int adj[N][N] = {28        {0, 1, 1, 0, 0, 0},29        {1, 0, 0, 1, 1, 0},30        {1, 0, 0, 0, 0, 1},31        {0, 1, 0, 0, 0, 0},32        {0, 1, 0, 0, 0, 1},33        {0, 0, 1, 0, 1, 0},34    };35    printf("BFS from node 0: ");36    bfs(0, adj);37    printf("\n");38    return 0;39}