广度优先搜索

  1. use std::collections::HashSet;
  2. use std::collections::VecDeque;
  4. /// Perform a breadth-first search on Graph `graph`.
  5. ///
  6. /// # Parameters
  7. ///
  8. /// - `graph`: The graph to search.
  9. /// - `root`: The starting node of the graph from which to begin searching.
  10. /// - `target`: The target node for the search.
  11. ///
  12. /// # Returns
  13. ///
  14. /// If the target is found, an Optional vector is returned with the history
  15. /// of nodes visited as its contents.
  16. ///
  17. /// If the target is not found or there is no path from the root,
  18. /// `None` is returned.
  19. ///
  20. pub fn breadth_first_search(graph: &Graph, root: Node, target: Node) -> Option<Vec<u32>> {
  21.     let mut visited: HashSet<Node> = HashSet::new();
  22.     let mut history: Vec<u32> = Vec::new();
  23.     let mut queue = VecDeque::new();
  25.     visited.insert(root);
  26.     queue.push_back(root);
  27.     while let Some(currentnode) = queue.pop_front() {
  28.         history.push(currentnode.value());
  30.         // If we reach the goal, return our travel history.
  31.         if currentnode == target {
  32.             return Some(history);
  33.         }
  35.         // Check the neighboring nodes for any that we've not visited yet.
  36.         for neighbor in currentnode.neighbors(graph) {
  37.             if !visited.contains(&neighbor) {
  38.                 visited.insert(neighbor);
  39.                 queue.push_back(neighbor);
  40.             }
  41.         }
  42.     }
  44.     // All nodes were visited, yet the target was not found.
  45.     None
  46. }
  48. // Data Structures
  50. #[derive(Copy, Clone, PartialEq, Eq, Hash)]
  51. pub struct Node(u32);
  53. #[derive(Copy, Clone, PartialEq, Eq, Hash)]
  54. pub struct Edge(u32, u32);
  56. #[derive(Clone)]
  57. pub struct Graph {
  58.     nodes: Vec<Node>,
  59.     edges: Vec<Edge>,
  60. }
  62. impl Graph {
  63.     pub fn new(nodes: Vec<Node>, edges: Vec<Edge>) -> Self {
  64.         Graph { nodes, edges }
  65.     }
  66. }
  68. impl From<u32> for Node {
  69.     fn from(item: u32) -> Self {
  70.         Node(item)
  71.     }
  72. }
  74. impl Node {
  75.     pub fn value(&self) -> u32 {
  76.         self.0
  77.     }
  79.     pub fn neighbors(&self, graph: &Graph) -> Vec<Node> {
  80.         graph
  81.             .edges
  82.             .iter()
  83.             .filter(|e| e.0 == self.0)
  84.             .map(|e| e.1.into())
  85.             .collect()
  86.     }
  87. }
  89. impl From<(u32, u32)> for Edge {
  90.     fn from(item: (u32, u32)) -> Self {
  91.         Edge(item.0, item.1)
  92.     }
  93. }
  95. #[cfg(test)]
  96. mod tests {
  97.     use super::*;
  99.     /* Example graph #1:
  100.      *
  101.      *            (1)   <--- Root
  102.      *           /   \
  103.      *         (2)   (3)
  104.      *        / |     | \
  105.      *     (4) (5)   (6) (7)
  106.      *          |
  107.      *         (8)
  108.      */
  109.     fn graph1() -> Graph {
  110.         let nodes = vec![1, 2, 3, 4, 5, 6, 7];
  111.         let edges = vec![(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7), (5, 8)];
  113.         Graph::new(
  114.             nodes.into_iter().map(|v| v.into()).collect(),
  115.             edges.into_iter().map(|e| e.into()).collect(),
  116.         )
  117.     }
  119.     #[test]
  120.     fn breadth_first_search_graph1_when_node_not_found_returns_none() {
  121.         let graph = graph1();
  122.         let root = 1;
  123.         let target = 10;
  125.         assert_eq!(
  126.             breadth_first_search(&graph, root.into(), target.into()),
  127.             None
  128.         );
  129.     }
  131.     #[test]
  132.     fn breadth_first_search_graph1_when_target_8_should_evaluate_all_nodes_first() {
  133.         let graph = graph1();
  134.         let root = 1;
  135.         let target = 8;
  137.         let expected_path = vec![1, 2, 3, 4, 5, 6, 7, 8];
  139.         assert_eq!(
  140.             breadth_first_search(&graph, root.into(), target.into()),
  141.             Some(expected_path)
  142.         );
  143.     }
  145.     /* Example graph #2:
  146.      *
  147.      *     (1) --- (2)     (3) --- (4)
  148.      *            / |     /       /
  149.      *          /   |   /       /
  150.      *        /     | /       /
  151.      *     (5)     (6) --- (7)     (8)
  152.      */
  153.     fn graph2() -> Graph {
  154.         let nodes = vec![1, 2, 3, 4, 5, 6, 7, 8];
  155.         let undirected_edges = vec![
  156.             (1, 2),
  157.             (2, 1),
  158.             (2, 5),
  159.             (5, 2),
  160.             (2, 6),
  161.             (6, 2),
  162.             (3, 4),
  163.             (4, 3),
  164.             (3, 6),
  165.             (6, 3),
  166.             (4, 7),
  167.             (7, 4),
  168.             (6, 7),
  169.             (7, 6),
  170.         ];
  172.         Graph::new(
  173.             nodes.into_iter().map(|v| v.into()).collect(),
  174.             undirected_edges.into_iter().map(|e| e.into()).collect(),
  175.         )
  176.     }
  178.     #[test]
  179.     fn breadth_first_search_graph2_when_no_path_to_node_returns_none() {
  180.         let graph = graph2();
  181.         let root = 8;
  182.         let target = 4;
  184.         assert_eq!(
  185.             breadth_first_search(&graph, root.into(), target.into()),
  186.             None
  187.         );
  188.     }
  190.     #[test]
  191.     fn breadth_first_search_graph2_should_find_path_from_4_to_1() {
  192.         let graph = graph2();
  193.         let root = 4;
  194.         let target = 1;
  196.         let expected_path = vec![4, 3, 7, 6, 2, 1];
  198.         assert_eq!(
  199.             breadth_first_search(&graph, root.into(), target.into()),
  200.             Some(expected_path)
  201.         );
  202.     }
  203. }