深度优先搜索

  1. use std::collections::HashSet;
  2. use std::collections::VecDeque;
  4. // Perform a Depth First Search Algorithm to find a element in a graph
  5. //
  6. // Return a Optional with a vector with history of vertex visiteds
  7. // or a None if the element not exists on the graph
  8. pub fn depth_first_search(graph: &Graph, root: Vertex, objective: Vertex) -> Option<Vec<u32>> {
  9.     let mut visited: HashSet<Vertex> = HashSet::new();
  10.     let mut history: Vec<u32> = Vec::new();
  11.     let mut queue = VecDeque::new();
  12.     queue.push_back(root);
  14.     // While there is an element in the queue
  15.     // get the first element of the vertex queue
  16.     while let Some(current_vertex) = queue.pop_front() {
  17.         // Added current vertex in the history of visiteds vertex
  18.         history.push(current_vertex.value());
  20.         // Verify if this vertex is the objective
  21.         if current_vertex == objective {
  22.             // Return the Optional with the history of visiteds vertex
  23.             return Some(history);
  24.         }
  26.         // For each over the neighbors of current vertex
  27.         for neighbor in current_vertex.neighbors(graph).into_iter().rev() {
  28.             // Insert in the HashSet of visiteds if this value not exist yet
  29.             if visited.insert(neighbor) {
  30.                 // Add the neighbor on front of queue
  31.                 queue.push_front(neighbor);
  32.             }
  33.         }
  34.     }
  36.     // If all vertex is visited and the objective is not found
  37.     // return a Optional with None value
  38.     None
  39. }
  41. // Data Structures
  43. #[derive(Copy, Clone, PartialEq, Eq, Hash)]
  44. pub struct Vertex(u32);
  45. #[derive(Copy, Clone, PartialEq, Eq, Hash)]
  46. pub struct Edge(u32, u32);
  47. #[derive(Clone)]
  48. pub struct Graph {
  49.     vertices: Vec<Vertex>,
  50.     edges: Vec<Edge>,
  51. }
  53. impl Graph {
  54.     pub fn new(vertices: Vec<Vertex>, edges: Vec<Edge>) -> Self {
  55.         Graph { vertices, edges }
  56.     }
  57. }
  59. impl From<u32> for Vertex {
  60.     fn from(item: u32) -> Self {
  61.         Vertex(item)
  62.     }
  63. }
  65. impl Vertex {
  66.     pub fn value(&self) -> u32 {
  67.         self.0
  68.     }
  70.     pub fn neighbors(&self, graph: &Graph) -> VecDeque<Vertex> {
  71.         graph
  72.             .edges
  73.             .iter()
  74.             .filter(|e| e.0 == self.0)
  75.             .map(|e| e.1.into())
  76.             .collect()
  77.     }
  78. }
  80. impl From<(u32, u32)> for Edge {
  81.     fn from(item: (u32, u32)) -> Self {
  82.         Edge(item.0, item.1)
  83.     }
  84. }
  86. #[cfg(test)]
  87. mod tests {
  88.     use super::*;
  90.     #[test]
  91.     fn find_1_fail() {
  92.         let vertices = vec![1, 2, 3, 4, 5, 6, 7];
  93.         let edges = vec![(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7)];
  95.         let root = 1;
  96.         let objective = 99;
  98.         let graph = Graph::new(
  99.             vertices.into_iter().map(|v| v.into()).collect(),
  100.             edges.into_iter().map(|e| e.into()).collect(),
  101.         );
  103.         assert_eq!(
  104.             depth_first_search(&graph, root.into(), objective.into()),
  105.             None
  106.         );
  107.     }
  109.     #[test]
  110.     fn find_1_sucess() {
  111.         let vertices = vec![1, 2, 3, 4, 5, 6, 7];
  112.         let edges = vec![(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7)];
  114.         let root = 1;
  115.         let objective = 7;
  117.         let correct_path = vec![1, 2, 4, 5, 3, 6, 7];
  119.         let graph = Graph::new(
  120.             vertices.into_iter().map(|v| v.into()).collect(),
  121.             edges.into_iter().map(|e| e.into()).collect(),
  122.         );
  124.         assert_eq!(
  125.             depth_first_search(&graph, root.into(), objective.into()),
  126.             Some(correct_path)
  127.         );
  128.     }
  130.     #[test]
  131.     fn find_2_sucess() {
  132.         let vertices = vec![0, 1, 2, 3, 4, 5, 6, 7];
  133.         let edges = vec![
  134.             (0, 1),
  135.             (1, 3),
  136.             (3, 2),
  137.             (2, 1),
  138.             (3, 4),
  139.             (4, 5),
  140.             (5, 7),
  141.             (7, 6),
  142.             (6, 4),
  143.         ];
  145.         let root = 0;
  146.         let objective = 6;
  148.         let correct_path = vec![0, 1, 3, 2, 4, 5, 7, 6];
  150.         let graph = Graph::new(
  151.             vertices.into_iter().map(|v| v.into()).collect(),
  152.             edges.into_iter().map(|e| e.into()).collect(),
  153.         );
  155.         assert_eq!(
  156.             depth_first_search(&graph, root.into(), objective.into()),
  157.             Some(correct_path)
  158.         );
  159.     }
  161.     #[test]
  162.     fn find_3_sucess() {
  163.         let vertices = vec![0, 1, 2, 3, 4, 5, 6, 7];
  164.         let edges = vec![
  165.             (0, 1),
  166.             (1, 3),
  167.             (3, 2),
  168.             (2, 1),
  169.             (3, 4),
  170.             (4, 5),
  171.             (5, 7),
  172.             (7, 6),
  173.             (6, 4),
  174.         ];
  176.         let root = 0;
  177.         let objective = 4;
  179.         let correct_path = vec![0, 1, 3, 2, 4];
  181.         let graph = Graph::new(
  182.             vertices.into_iter().map(|v| v.into()).collect(),
  183.             edges.into_iter().map(|e| e.into()).collect(),
  184.         );
  186.         assert_eq!(
  187.             depth_first_search(&graph, root.into(), objective.into()),
  188.             Some(correct_path)
  189.         );
  190.     }
  191. }