Short Python and Rust Implementations of Each Algorithm
A* Search in Python
import heapq
def astar(graph, start, goal, h):
pq = [(h[start], 0, start, [start])]
seen = set()
while pq:
f, g, node, path = heapq.heappop(pq)
if node == goal: return path
if node in seen: continue
seen.add(node)
for nxt, cost in graph.get(node, []): heapq.heappush(pq, (g + cost + h[nxt], g + cost, nxt, path + [nxt]))
Brief Code explanation:
1. heapq is used as a priority queue so the most promising path is explored first.
2. Each queue item stores total estimated cost f, actual cost g, current node, and path.
3. h is the heuristic map that estimates distance from each node to the goal.
4. The algorithm stops as soon as the goal node is reached.
5. seen prevents repeated work on nodes already processed.
6. Each neighbor is evaluated with its travel cost added to the current path cost.
7. A* ranks paths using g + h, combining actual progress with estimated remaining distance.
8. The result is the discovered path, which makes the example easy to understand educationally.
A* Search in Rust
use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap, HashSet};
fn astar(graph: &HashMap<&str, Vec<(&str, i32)>>, start: &str, goal: &str, h: &HashMap<&str, i32>) -> Vec<&str> {
let mut heap = BinaryHeap::from([Reverse((h[start], 0, start, vec![start]))]); let mut seen = HashSet::new();
while let Some(Reverse((_, g, node, path))) = heap.pop() {
if node == goal { return path; }
if !seen.insert(node) { continue; }
for (nxt, cost) in &graph[node] { let mut p = path.clone(); p.push(nxt); heap.push(Reverse((g + cost + h[nxt], g + cost, *nxt, p))); }
} vec![]
}
Brief Code explanation:
1. BinaryHeap is used to prioritize the lowest estimated-cost path.
2. Reverse turns Rust’s default max-heap into min-heap behavior.
3. The graph is stored as an adjacency list with neighbor and cost pairs.
4. The heuristic map h provides estimated remaining distance to the goal.
5. Each heap entry stores estimated total cost, actual path cost, current node, and full path.
6. seen ensures the same node is not processed repeatedly.
7. The path is cloned and extended as neighbors are explored.
8. An empty vector is returned if no route to the goal is found.
Breadth-First Search in Python
from collections import deque
def bfs(graph, start):
visited, queue = set([start]), deque([start])
while queue:
node = queue.popleft()
print(node)
for n in graph[node]:
if n not in visited: visited.add(n); queue.append(n)
Brief Code explanation:
1. BFS uses a queue to process nodes in first-in, first-out order.
2. visited prevents repeated processing of the same node.
3. The algorithm starts from a chosen node.
4. popleft() ensures the oldest queued node is processed first.
5. Printing the node shows traversal order for learning purposes.
6. The loop checks every direct neighbor of the current node.
7. Unvisited neighbors are marked and added to the queue.
8. This level-by-level expansion is what makes BFS useful for shortest paths in unweighted graphs.
Breadth-First Search in Rust
use std::collections::{HashMap, HashSet, VecDeque};
fn bfs(graph: &HashMap>, start: i32) {
let (mut visited, mut queue) = (HashSet::from([start]), VecDeque::from([start]));
while let Some(node) = queue.pop_front() {
println!("{}", node);
for n in &graph[&node] {
if visited.insert(*n) { queue.push_back(*n); }
}
}
}
Brief Code explanation:
1. Rust uses VecDeque as an efficient queue structure.
2. HashSet tracks visited nodes and avoids duplicates.
3. The graph is represented as an adjacency list with HashMap.
4. pop_front() removes the next node in BFS order.
5. println! makes the traversal visible during execution.
6. The code iterates over neighbors of the current node.
7. visited.insert(*n) returns true only for new nodes.
8. New nodes are added to the back of the queue for later processing.
Merge Sort in Python
def merge_sort(arr):
if len(arr) <= 1: return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]); right = merge_sort(arr[mid:])
result = []; i = j = 0
while i < len(left) and j < len(right):
result.append(left[i] if left[i] < right[j] else right[j]); i += left[i] < right[j]; j += left[i] >= right[j]
return result + left[i:] + right[j:]
Brief Code explanation:
1. Arrays of length 0 or 1 are already sorted.
2. The list is split into two smaller halves.
3. Each half is sorted recursively using the same function.
4. The merge phase combines both sorted halves.
5. Two pointers track the current position in each half.
6. The smaller value is appended to the result first.
7. Remaining items are added after one side is exhausted.
8. This divide-and-conquer pattern gives Merge Sort its consistency.
Merge Sort in Rust
fn merge_sort(arr: Vec) -> Vec {
if arr.len() <= 1 { return arr; }
let mid = arr.len() / 2;
let (left, right) = (merge_sort(arr[..mid].to_vec()), merge_sort(arr[mid..].to_vec()));
let (mut out, mut i, mut j) = (Vec::new(), 0, 0);
while i < left.len() && j < right.len() { if left[i] < right[j] { out.push(left[i]); i += 1; } else { out.push(right[j]); j += 1; } }
out.extend_from_slice(&left[i..]); out.extend_from_slice(&right[j..]); out
}
Brief Code explanation:
1. The function returns a newly sorted vector.
2. A vector with one or zero elements is already sorted.
3. The input is split into two parts at the midpoint.
4. Each part is sorted recursively before merging.
5. i and j track positions in the left and right halves.
6. The smaller current element is pushed into the output vector.
7. Remaining elements are appended once one side finishes.
8. This version favors clarity so readers can follow the merge logic easily.
