Breadth First Search (BFS)

from collections import deque

# Breadth First Search (BFS)

def bfs(graph, start_node):

    visited = set()
    queue = deque([start_node])

    visited.add(start_node)

    while queue:

        node = queue.popleft()   # Dequeue
        print(node, end=" ")

        # Visit neighbors
        for neighbor in graph[node]:

            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)   # Enqueue


graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': [],
    'F': []
}

print("BFS Traversal:")
bfs(graph, 'A')

import java.util.*;

public class BFSExample {

    static void bfs(Map<String, List<String>> graph,
                    String startNode) {

        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();

        queue.add(startNode);
        visited.add(startNode);

        while (!queue.isEmpty()) {

            String node = queue.poll();   // Dequeue
            System.out.print(node + " ");

            for (String neighbor : graph.get(node)) {

                if (!visited.contains(neighbor)) {

                    visited.add(neighbor);
                    queue.add(neighbor);  // Enqueue
                }
            }
        }
    }

    public static void main(String[] args) {

        Map<String, List<String>> graph = new HashMap<>();

        graph.put("A", Arrays.asList("B","C"));
        graph.put("B", Arrays.asList("D","E"));
        graph.put("C", Arrays.asList("F"));
        graph.put("D", new ArrayList<>());
        graph.put("E", new ArrayList<>());
        graph.put("F", new ArrayList<>());

        System.out.println("BFS Traversal:");

        bfs(graph, "A");
    }
}

#include <stdio.h>

#define N 6

void bfs(int graph[N][N], int start) {

    int visited[N] = {0};
    int queue[N];
    int front = 0, rear = 0;

    queue[rear++] = start;
    visited[start] = 1;

    while (front < rear) {

        int node = queue[front++];
        printf("%d ", node);

        for (int i = 0; i < N; i++) {

            if (graph[node][i] && !visited[i]) {

                visited[i] = 1;
                queue[rear++] = i;
            }
        }
    }
}

int main() {

    int graph[N][N] = {
        {0,1,1,0,0,0},
        {0,0,0,1,1,0},
        {0,0,0,0,0,1},
        {0,0,0,0,0,0},
        {0,0,0,0,0,0},
        {0,0,0,0,0,0}
    };

    printf("BFS Traversal:\n");

    bfs(graph, 0);

    return 0;
}

#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <set>
using namespace std;

void bfs(map<char, vector<char>>& graph,
         char start) {

    set<char> visited;
    queue<char> q;

    q.push(start);
    visited.insert(start);

    while (!q.empty()) {

        char node = q.front();
        q.pop();

        cout << node << " ";

        for (char neighbor : graph[node]) {

            if (visited.count(neighbor) == 0) {

                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
}

int main() {

    map<char, vector<char>> graph;

    graph['A'] = {'B','C'};
    graph['B'] = {'D','E'};
    graph['C'] = {'F'};
    graph['D'] = {};
    graph['E'] = {};
    graph['F'] = {};

    cout << "BFS Traversal:" << endl;

    bfs(graph, 'A');

    return 0;
}