课程规划
(
cg: &mut Graph<T>,
course: Vertex<T>,
schedule: &mut Vec<String>,
mut has_circle: bool)
| 98 | |
| 99 | // 课程规划 |
| 100 | fn course_scheduling<T>( |
| 101 | cg: &mut Graph<T>, |
| 102 | course: Vertex<T>, |
| 103 | schedule: &mut Vec<String>, |
| 104 | mut has_circle: bool) |
| 105 | where T: Eq + PartialEq + Clone + Hash + Display |
| 106 | { |
| 107 | // 克隆，防止可变引用冲突 |
| 108 | let edges = cg.edges.clone(); |
| 109 | |
| 110 | // 对依赖课程进行探索 |
| 111 | let dependencies = edges.get(&course.key); |
| 112 | if !dependencies.is_none() { |
| 113 | for dependency in dependencies.unwrap().iter() { |
| 114 | let course = cg.vertices.get(dependency).unwrap().clone(); |
| 115 | if Color::White == course.color { |
| 116 | cg.vertices.get_mut(dependency).unwrap().color = Color::Gray; |
| 117 | course_scheduling(cg, course, schedule, has_circle); |
| 118 | if has_circle { |
| 119 | return; // 遇到环，退出 |
| 120 | } |
| 121 | } else if Color::Gray == course.color { |
| 122 | has_circle = true; // 遇到环，退出 |
| 123 | return; |
| 124 | } |
| 125 | } |
| 126 | } |
| 127 | |
| 128 | // 修改课程节点颜色，表示当前课程节点探索完成，加入 schedule |
| 129 | cg.vertices.get_mut(&course.key).unwrap().color = Color::Black; |
| 130 | schedule.push(course.key.to_string()); |
| 131 | } |
| 132 | |
| 133 | fn find_topological_order<T>(course_num: usize, pre_requisites: Vec<Vec<T>>) |
| 134 | where T: Eq + PartialEq + Clone + Hash + Display |