Breadth-First Search (BFS) Algorithm (WIP)

Breadth-First Search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or an arbitrary node of a graph) and explores the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.

use std::collections::{HashMap, VecDeque};

fn bfs(graph: &HashMap<i32, Vec<i32>>, start: i32) -> Vec<i32> {
    let mut visited = Vec::new();
    let mut queue = VecDeque::new();
    queue.push_back(start);

    while let Some(node) = queue.pop_front() {
        if !visited.contains(&node) {
            visited.push(node);
            if let Some(neighbors) = graph.get(&node) {
                for &neighbor in neighbors {
                    queue.push_back(neighbor);
                }
            }
        }
    }

    visited
}

fn main() {
    let mut graph = HashMap::new();
    graph.insert(1, vec![2, 3]);
    graph.insert(2, vec![4, 5]);
    graph.insert(3, vec![6, 7]);
    graph.insert(4, vec![]);
    graph.insert(5, vec![]);
    graph.insert(6, vec![]);
    graph.insert(7, vec![]);

    let start_node = 1;
    let result = bfs(&graph, start_node);
    println!("BFS traversal starting from node {}: {:?}", start_node, result);
}
  1. Graph Representation: The graph is represented using a HashMap where each key is a node, and the value is a vector of its neighbors.
  2. BFS Function: The bfs function takes a reference to the graph and a starting node. It uses a VecDeque as a queue to manage the nodes to be explored.
  3. Traversal: The function iterates over the queue, marking nodes as visited and adding their neighbors to the queue if they haven't been visited yet.
  4. Main Function: The main function initializes the graph, calls the bfs function, and prints the result of the BFS traversal.

This example demonstrates a basic BFS traversal of a graph in Rust. You can modify the graph and the starting node to see how the traversal changes.