广度优先搜索

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. }