Antonio Perrone

Posted on

# A Weekly RustðŸ¦€ Pill #5

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 ðŸ¦€.

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

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

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();

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,
}
``````
• 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) {
}
``````
• 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);

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

## Top comments (1)

I would like breadth firstable trait better as you can implement that for multiple ds like tree trie etc.