A Weekly Rust🦀 Pill #5
Tags: rust, programming
Published: 2023-08-30 12:26:49

A Weekly Rust🦀 Pill is a post series where on a weekly base, I share some implementations of the most popular algorithms and data structures to share my learnings on Rust 🦀.

# Breadth-First Search
Graphs are fundamental data structures used to represent relationships between various entities. They find applications in various fields, from social networks and transportation systems to computer networks and recommendation systems. One of the most essential algorithms for traversing graphs is the Breadth-First Search (BFS) algorithm. In this blog post, we'll delve into the BFS, understanding how it works and analysing a Rust implementation.

## Understanding BFS
Breadth-First Search (BFS) is a graph traversal algorithm that explores a graph by visiting all its nodes in breadth-first order. Unlike depth-first traversal, which goes as deep as possible before backtracking, BFS explores nodes level by level, starting from the root (or a chosen starting node). The algorithm ensures that all nodes at a given depth level are visited before proceeding to the next depth level.

## Step-by-Step Walkthrough
Start with an initial node and mark it as visited.
Enqueue the initial node into a queue (FIFO data structure).
While the queue is not empty:
a. Dequeue a node from the front of the queue.
b. Process the node (e.g., print its value).
c. Enqueue all unvisited neighbours of the current node into the queue and mark them as visited.
Repeat step 3 until the queue becomes empty.

## Applications of BFS
- **Shortest Path and Distance Calculation**: BFS can be used to find the shortest path between two nodes in an unweighted graph. By systematically exploring nodes layer by layer, BFS guarantees that the shortest path is found when the destination node is reached.
- **Connectivity and Component Analysis**: BFS helps identify connected components within a graph. It is particularly useful in determining whether a graph is connected or not.
- **Web Crawling**: BFS can be employed to crawl web pages, exploring websites and their links in a systematic and organised manner.
- **Social Network Analysis**: BFS assists in analysing social networks by identifying friends and connections within a certain distance from a given individual.

# Implementation
Here's a sample implementation

```rust
struct Graph {
    size: usize,
    adj_matrix: Vec<Vec<bool>>,
}

impl Graph {
    fn new(size: usize) -> Graph {
        Graph {
            size,
            adj_matrix: vec![vec![false; size]; size],
        }
    }

    fn add_edge(&mut self, v: usize, w: usize) {
        self.adj_matrix[v][w] = true;
    }

    fn bfs(&self, start: usize) -> Vec<usize> {
        let mut visited: Vec<bool> = vec![false; self.size];
        let mut queue: VecDeque<usize> = VecDeque::new();
        let mut path: Vec<usize> = vec![];

        visited[start] = true;
        path.push(start);
        queue.push_back(start);
        while !queue.is_empty() {
            let node = queue.pop_front();

            let node_adj = &self.adj_matrix[node.unwrap() as usize];
            for i in 0..node_adj.len() {
                if visited[i] == false && node_adj[i] {
                    visited[i] = true;
                    queue.push_back(i);

                    path.push(i);
                }
            }
        }

        path
    }
}
```

The provided code snippet defines a Rust struct called `Graph` along with its implementation, which includes methods for creating a new graph, adding edges, and performing Breadth-First Search (BFS) traversal on the graph. 

Let's break down the code and its components:

**Struct Definition:**
   ```rust
   struct Graph {
       size: usize,
       adj_matrix: Vec<Vec<bool>>,
   }
   ```
   - The `Graph` struct represents a graph with an adjacency matrix.
   - `size` represents the number of nodes in the graph.
   - `adj_matrix` is a 2D vector (a vector of vectors) that stores the adjacency matrix of the graph. It uses boolean values to indicate whether there is an edge between two nodes. If `adj_matrix[i][j]` is `true`, it means there is an edge from node `i` to node `j`.

**Implementation:**
   ```rust
   impl Graph {
       // Method to create a new graph
       fn new(size: usize) -> Graph { ... }

       // Method to add an edge between two nodes
       fn add_edge(&mut self, v: usize, w: usize) { ... }

       // Method to perform BFS traversal
       fn bfs(&self, start: usize) -> Vec<usize> { ... }
   }
   ```

**`new` Method:**
   ```rust
   fn new(size: usize) -> Graph {
       Graph {
           size,
           adj_matrix: vec![vec![false; size]; size],
       }
   }
   ```
   - The `new` method creates a new instance of the `Graph` struct with the specified `size`.
   - It initialises the adjacency matrix with `size` rows and columns, filled with `false` values to indicate no edges initially.

**`add_edge` Method:**
   ```rust
   fn add_edge(&mut self, v: usize, w: usize) {
       self.adj_matrix[v][w] = true;
   }
   ```
   - The `add_edge` method adds an edge between nodes `v` and `w` by setting the corresponding entry in the adjacency matrix to `true`.

**`bfs` Method:**
   ```rust
   fn bfs(&self, start: usize) -> Vec<usize> { ... }
   ```
   - The `bfs` method performs BFS traversal on the graph starting from the specified `start` node.
   - It initialises data structures for tracking visited nodes (`visited`), nodes to visit (`queue`), and the traversal path (`path`).
   - The method uses a loop that continues until the `queue` is empty.
   - Within the loop, it dequeues a node from the front of the queue and explores its neighbours, adding them to the queue and updating the `visited` and `path` data structures.
   - The method returns the traversal path as a vector of node indices.

## Sample application
The following code is a sample usage of BFS algorithm

```rust
fn main() {
    let mut g = Graph::new(6);

    g.add_edge(0, 1);
    g.add_edge(0, 2);
    g.add_edge(1, 2);
    g.add_edge(2, 0);
    g.add_edge(2, 3);
    g.add_edge(3, 3);

    let result = g.bfs(0);
    println!(
        "Following is Breadth First Traversal (starting from vertex 0): {:?}",
        result
    )
}
```