A Weekly Rust🦀 Pill #5

#rust #programming

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

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:

   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:

   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:

   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:

   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:

   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

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
    )
}