Struct graph_algorithms::list_of_algorithms::dfs::dfs::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 d_fs(&self, u: usize, visited: &mut HashSet<usize>) -> Vec<usize>

DFS algorithm Performs a Depth-First Search on a given graph represented as an adjacency list and returns a vector of 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_vertex - The index of the vertex to start the Depth-First Search from.

Returns

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

Example

use depth_first_search::dfs;

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 = dfs(&adj_list, start_vertex);

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