深度优先搜索

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