Struct graph_algorithms::list_of_algorithms::bfs::bfs::Graph

pub struct Graph {
    pub edges: Vec<Vec<usize>>,
    pub vertices: usize,
}

A graph data structure with adjacency list representation.

Fields

edges: Vec<Vec<usize>>

The edges of the graph stored as adjacency lists.

vertices: usize

The total number of vertices in the graph.

Implementations

impl Graph

pub fn new(vertices: usize) -> Self

pub fn add_edge(&mut self, u: usize, v: usize)

Adds an edge between two vertices in the graph.

Arguments

• u - The index of the first vertex.
• v - The index of the second vertex.

Example

use my_crate::Graph;

let mut graph = Graph::new(5);

graph.add_edge(0, 1);
graph.add_edge(1, 2);
graph.add_edge(2, 3);
graph.add_edge(3, 4);

pub fn b_fs(&self, start: usize) -> Vec<usize>

BFS algorithm Performs a Breadth-First Search on a given graph represented as an adjacency list and returns visited vertices in the order they were visited.

Arguments

• adj_list - A graph represented as an adjacency list. Each vector in the adjacency list represents the vertices that the corresponding vertex has an outgoing edge to.
• start - The index of the vertex to start the Breadth-First Search from.

Returns

• visited - A vector of visited vertices in the order they were visited during the Breadth-First Search.

Example

  use breadth_first_search::bfs;

 let adj_list = vec![
 vec![1, 2], // Node 0 has edges to nodes 1 and 2
 vec![3, 4], // Node 1 has edges to nodes 3 and 4
 vec![5], // Node 2 has edge to node 5  
 vec![6], // Node 3 has edge to node 6
 vec![], // Node 4 has no outgoing edges
 vec![7, 8], // Node 5 has edges to nodes 7 and 8
 vec![], // Node 6 has no outgoing edges
 vec![9], // Node 7 has edge to node 9
 vec![], // Node 8 has no outgoing edges
 vec![], // Node 9 has no outgoing edges
 ];
 let start_vertex = 0;
  
 let visited = bfs(&adj_list, start_vertex);

 assert_eq!(visited, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);