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. Ifadj_matrix[i][j]
istrue
, it means there is an edge from nodei
to nodej
.
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 theGraph
struct with the specifiedsize
. - It initialises the adjacency matrix with
size
rows and columns, filled withfalse
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 nodesv
andw
by setting the corresponding entry in the adjacency matrix totrue
.
bfs
Method:
fn bfs(&self, start: usize) -> Vec<usize> { ... }
- The
bfs
method performs BFS traversal on the graph starting from the specifiedstart
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
andpath
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
)
}
Top comments (1)
I would like breadth firstable trait better as you can implement that for multiple ds like tree trie etc.