字梯图-广度优先搜索
(
g: &mut Graph<String>,
start: Vertex<String>,
end: Vertex<String>,
len: usize,
)
| 165 | |
| 166 | // 字梯图-广度优先搜索 |
| 167 | fn word_ladder( |
| 168 | g: &mut Graph<String>, |
| 169 | start: Vertex<String>, |
| 170 | end: Vertex<String>, |
| 171 | len: usize, |
| 172 | ) -> u32 { |
| 173 | // 判断起始点是否存在 |
| 174 | if !g.vertices.contains_key(&start.key) { return 0; } |
| 175 | if !g.vertices.contains_key(&end.key) { return 0; } |
| 176 | |
| 177 | // 准备队列，加入起始点 |
| 178 | let mut vertex_queue = Queue::new(len); |
| 179 | let _r = vertex_queue.enqueue(start); |
| 180 | |
| 181 | while vertex_queue.len() > 0 { |
| 182 | // 节点出队 |
| 183 | let curr = vertex_queue.dequeue().unwrap(); |
| 184 | for nbr in curr.get_neighbors() { |
| 185 | // 克隆，避免和图中数据起冲突 |
| 186 | // Graph 的 vertices 用 RefCell 包裹就不需要克隆 |
| 187 | let mut nbv = g.vertices.get(nbr).unwrap().clone(); |
| 188 | |
| 189 | if end.key != nbv.key { |
| 190 | // 只有白色的才可以入队列，其他颜色都处理过了 |
| 191 | if Color::White == nbv.color { |
| 192 | // 节点更新颜色和距离并加入队列 |
| 193 | nbv.color = Color::Gray; |
| 194 | nbv.distance = curr.distance + 1; |
| 195 | |
| 196 | // 图中的节点也需要更新颜色和距离 |
| 197 | g.vertices.get_mut(nbr).unwrap().color = Color::Gray; |
| 198 | g.vertices.get_mut(nbr).unwrap().distance = curr.distance + 1; |
| 199 | |
| 200 | // 白色节点加入队列 |
| 201 | let _r = vertex_queue.enqueue(nbv); |
| 202 | } |
| 203 | // 其他颜色不需要处理，用两个颜色就够了 |
| 204 | // 所以代码里也没用 Black 枚举值 |
| 205 | } else { |
| 206 | // curr 的邻点里有 end，所以再转换一次就够了 |
| 207 | return curr.distance + 1; |
| 208 | } |
| 209 | } |
| 210 | } |
| 211 | |
| 212 | 0 |
| 213 | } |
| 214 | |
| 215 | fn main() { |
| 216 | let words = vec![ |