23.20 Graphs
Graphs
Overview
A Graph is a collection of nodes (vertices) connected by edges. It can be directed or undirected.
Topics
- Representations (Adjacency List, Adjacency Matrix)
- Graph Traversals (DFS, BFS)
Examples
Adjacency List Representation
use std::collections::HashMap;
let mut graph: HashMap<i32, Vec<i32>> = HashMap::new();
graph.insert(1, vec![2, 3]);
graph.insert(2, vec![4]);
graph.insert(3, vec![4]);
graph.insert(4, vec![]);
println!("{:?}", graph);
DFS Traversal
fn dfs(node: i32, graph: &HashMap<i32, Vec<i32>>, visited: &mut Vec<i32>) {
if visited.contains(&node) {
return;
}
visited.push(node);
for &neighbor in &graph[&node] {
dfs(neighbor, graph, visited);
}
}
let mut visited = Vec::new();
dfs(1, &graph, &mut visited);
println!("DFS: {:?}", visited);