dsa::algorithms::graph_traversal

Function depth_first_search

Source 
pub fn depth_first_search<T: Eq + Hash + Clone>(
    graph: &Graph<T>,
    start: Rc<TreeNode<T>>,
) -> Vec<T>
Expand description

Performs a depth-first search (DFS) on the given graph starting from the start node.

This function explores the graph by going as deep as possible along each branch before backtracking. It returns the nodes in the order they were visited.

§Examples

use std::rc::Rc;
use dsa::algorithms::graph_traversal::depth_first_search;
use dsa::data_structures::graph::Graph;
use dsa::data_structures::tree::TreeNode;
 
let mut graph = Graph::new();
let node1 = Rc::new(TreeNode::new(1));
let node2 = Rc::new(TreeNode::new(2));
let node3 = Rc::new(TreeNode::new(3));

graph.add_edge(Rc::clone(&node1), Rc::clone(&node2), Some(1));
graph.add_edge(Rc::clone(&node1), Rc::clone(&node3), Some(1));

let result = depth_first_search(&graph, Rc::clone(&node1));
assert_eq!(result, vec![1, 2, 3]);

§Parameters

  • graph: A reference to the graph in which the search will take place.
  • start: The node from which the search begins.

§Returns

A vector containing the values of the nodes in the order they were visited.