- 图
- 广度优先、深度优先算法
- 拓扑排序算法, 最小生成树, 单元最小距离
- BinaryHeap 最大/最小堆
- 如何为
Rc<RefCell<T>>
实现Hash特性 - PartialEq和PartialOrd的区别
图
数据结构
用边集和点集表示一幅图
struct Graph {
nodes: HashMap<i32, RefNode>, // 点集
edges: Vec<RefEdge>, // 边集
}
创建一幅图
- 通过数组[[权值, from, to], …]创建一个图
- 算法
- 取到w, from, to
- 创建
- 结点node
- 创建from、to结点
- 并graph.nodes.add(from, to)
- 边edge
- 创建边edge = (w, from, to)
- 并graph.edges.add(edge)
- 结点node
- 更新
- 更新to.in++
- 更新from.out++, from.nexts.add(to), from.edges(edge)
- 更新graph.edges.add(edge)
-
实现
fn create_graph(matrix: Vec<[i32; 3]>) -> Graph { let mut graph = Graph::new(); for node_info in matrix.iter() { let weight = node_info[0]; let from = node_info[1]; let to = node_info[2]; // 将from, to 两个节点加入图中 graph.nodes.entry(from).or_insert(RefNode::new(from)); graph.nodes.entry(to).or_insert(RefNode::new(to)); // 新建一条边(weight, from, to) let edge = RefEdge::new(Edge::new( weight, RefNode( graph.nodes.get(&from) .expect(format!("未发现{}号节点", from).as_str()) .0.clone(), ), RefNode( graph.nodes.get(&to) .expect(format!("未发现{}号节点", to).as_str()) .0.clone(), ), )); /* 更新to节点:to.in ++ */ graph.nodes.entry(to) .and_modify(|node| node.0.borrow_mut().in_degree += 1); /* 更新from节点: 1. from.nexts.add(to_node) 2. from.out++ 3. from.edges.add(edge) */ let to_node = graph.nodes.get(&to).unwrap().0.clone(); graph.nodes.entry(from).and_modify(|node| { node.0.borrow_mut().out_degree += 1; node.0.borrow_mut().nexts.push(RefNode(to_node)); node.0.borrow_mut().edges.push(RefEdge(edge.0.clone())); }); graph.edges.push(edge); } graph }
广度优先搜索
- 算法
- 使用队列
- 把根节点入队列(同时放入set中)
- 弹出节点,打印节点内容
- 把它不在set中的邻居节点入队
- 同时节点放入set中
- 循环
-
算法实现
fn bfs(root: RefNode) -> Vec<i32> { let mut res: Vec<i32> = vec![11]; // 根节点是11 let mut queue: VecDeque<RefNode> = VecDeque::new(); let mut set: HashSet<RefNode> = HashSet::new(); queue.push_back(root); while let Some(node) = queue.pop_front() { for node_next in node.0.borrow().nexts.iter() { if !set.contains(node_next) { res.push(node_next.0.borrow().elem); queue.push_back(RefNode(node_next.0.clone())); set.insert(RefNode(node_next.0.clone())); } } } res }
-
新练习
fn bfs(&self, start: &NodeLink<T>) { let mut queue: VecDeque<NodeLink<T>> = VecDeque::new(); let mut set: HashSet<NodeLink<T>> = HashSet::new(); let root = start.clone(); queue.push_front(root); while let Some(node) = queue.pop_back() { if set.contains(&node) { continue; } print!("{}, ", node.inner().no); set.insert(node.clone()); for next in &node.inner().next { if !set.contains(next) { queue.push_front(next.clone()); } } } println!(); }
深度优先搜索
- 算法
- 用栈
- 根节点入栈(入栈前打印节点)
- 当栈中还有节点时,循环
- 弹出节点
- 取出节点的一个不在set中的邻居节点
- 自己再入栈
- 打印这个邻居节点
- 邻居节点入栈
- 邻居节点入set
-
算法实现
fn dfs(root: RefNode) -> Vec<i32> { let mut res: Vec<i32> = vec![11]; let mut stack: Vec<RefNode> = vec![]; let mut set: HashSet<RefNode> = HashSet::new(); stack.push(root); while let Some(node) = stack.pop() { for next in node.0.borrow().nexts.iter() { if !set.contains(next) { res.push(next.0.borrow().elem); stack.push(RefNode(node.0.clone())); stack.push(RefNode(next.0.clone())); set.insert(RefNode(next.0.clone())); break; } } } res }
-
新练习
fn dfs(&self, start: &NodeLink<T>) { let mut stack: Vec<NodeLink<T>> = Vec::new(); let mut set: HashSet<NodeLink<T>> = HashSet::new(); let root = start.clone(); print!("{}, ", root.inner().no); set.insert(root.clone()); stack.push(root); while let Some(node) = stack.pop() { for next in &node.inner().next { if !set.contains(&next) { stack.push(node.clone()); stack.push(next.clone()); print!("{}, ", next.inner().no); set.insert(next.clone()); break; } } } println!(); }
拓扑排序算法
- 适用条件
- 有向图
- 有入度为0的节点
- 没有环
- 应用:编译顺序
- 算法
- 找到in=0的节点A
- 把A的影响去除
- 循环
-
算法实现
fn sorted_topology<T>(graph: &Graph<T>) -> Vec<T> where T: Hash + Eq + Display + Copy, { let mut map: HashMap<RefNode<T>, i32> = HashMap::new(); let mut zero_in: VecDeque<RefNode<T>> = VecDeque::new(); let mut res: Vec<T> = vec![]; for node in graph.nodes.values() { map.insert(node.clone(), node.0.borrow().in_degree); if node.0.borrow().in_degree == 0 { zero_in.push_back(node.clone()); } } while let Some(node) = zero_in.pop_back() { res.push(node.0.borrow().elem); for next in node.0.borrow().nexts.iter() { map.entry(next.clone()).and_modify(|in_degree| { *in_degree -= 1; if *in_degree == 0 { zero_in.push_back(next.clone()); } }); } } res }
-
新练习
fn find_zero_indegree(&self) -> NodeLink<T> { for node in self.nodes.values() { if node.inner().in_dgree == 0 { return node.clone(); } } NodeLink(None) } fn sorted_topology(&self) { if self.find_zero_indegree().is_none() { println!("没有入度为0的节点"); return; } print!("拓扑序列:["); let mut zero_in: Vec<NodeLink<T>> = Vec::new(); zero_in.push(self.find_zero_indegree()); while let Some(node) = zero_in.pop() { print!("{} -> ", node.inner().no); for next in &node.inner().next { next.as_ref().map(|node| { node.borrow_mut().in_dgree -= 1; if node.borrow().in_dgree == 0 { zero_in.push(next.clone()); } }); } } println!("END]"); }
最小生成树
- 概念
- 所有节点都连通,而节点间连通权值最小
- K算法
- 从边的最小值开始加
- 每加一条边就检查有没有形成环
- 形成环则不加
- 具体算法
- 将图所有节点放入并查集UnionFind中
- 将所有边放入最小堆
- 只要最小堆不空
- 取出最小边
- 查看边两端节点是否在一个集合中
- 在:形成环
- 不在:不在不形成环
- 未形成环的边加入res
- 合并边的两端到并查集中
- 循环
-
kruskal算法实现
fn kruskal_mst<T: Display>(graph: &Graph<T>) -> Vec<RefEdge<T>> { let mut nodes: Vec<RefNode<T>> = vec![]; let mut min_heap = BinaryHeap::new(); let mut res: Vec<RefEdge<T>> = vec![]; graph.nodes.values() .for_each(|node| nodes.push(RefNode(node.0.clone()))); let mut union_find = UnionFindSet::new(nodes); for edge in graph.edges.iter() { min_heap.push(Reverse(RefEdge(edge.0.clone()))); } while let Some(Reverse(edge)) = min_heap.pop() { if !union_find.is_same_set( RefNode(edge.0.borrow().from.0.clone()), RefNode(edge.0.borrow().to.0.clone()), ) { res.push(RefEdge(edge.0.clone())); union_find.union_set( RefNode(edge.0.borrow().from.0.clone()), RefNode(edge.0.borrow().to.0.clone()), ); } } res }
-
新练习
fn kruskal_mst(&self) { println!("\n克鲁斯卡尔最小生成树:"); let mut min_heap = BinaryHeap::new(); let mut set = HashSet::new(); let mut nodes: Vec<NodeLink<T>> = vec![]; for edge in &self.edges { min_heap.push(Reverse(edge.clone())); set.insert(edge.inner().from.clone()); set.insert(edge.inner().to.clone()); } for n in set { nodes.push(self.nodes.get(&n).unwrap().clone()); } let mut ufset = UnionFindSet::from(&nodes[..]); let mut from; let mut to; while let Some(Reverse(edge)) = min_heap.pop() { from = self.nodes.get(&edge.inner().from).unwrap().clone(); to = self.nodes.get(&edge.inner().to).unwrap().clone(); if !ufset.is_same(&from, &to) { println!("{}", edge); ufset.union(&from, &to); } } }
-
- prime算法
- 从任意节点开始
- 从权值最小的边走到to节点
- 再从to节点沿权值最小边继续走
- 要求权值最小边的目的to节点没有走过
- 权值最小边可以用min_heap
- 目的节点没有走过,可以HashSet判断
-
prime算法实现
fn prime_mst<T>(graph: &Graph<T>) -> Vec<RefEdge<T>> { let mut set: HashSet<RefNode<T>> = HashSet::new(); let mut min_heap: BinaryHeap<Reverse<RefEdge<T>>> = BinaryHeap::new(); let mut res: Vec<RefEdge<T>> = vec![]; for node in graph.nodes.values() { set.insert(RefNode(node.0.clone())); node.0.borrow().edges.iter() .for_each(|edge| min_heap.push(Reverse(RefEdge(edge.0.clone())))); while let Some(Reverse(min_edge)) = min_heap.pop() { let to_node = RefNode(min_edge.0.borrow().to.0.clone()); if !set.contains(&to_node) { res.push(RefEdge(min_edge.0.clone())); to_node.0.borrow().edges.iter() .for_each(|edge| min_heap.push( Reverse(RefEdge(edge.0.clone()) ))); set.insert(to_node); } } } res }
-
新练习
fn prime_mst(g: &Graph<T>) { let mut min_heap: BinaryHeap<Reverse<EdgeLink<T>>> = BinaryHeap::new(); let mut node_set: HashSet<NodeLink<T>> = HashSet::new(); let mut edge_set: HashSet<EdgeLink<T>> = HashSet::new(); let start = g.nodes.values().next().unwrap().clone(); for edge in &start.inner().edges { min_heap.push(Reverse(edge.clone())); edge_set.insert(edge.clone()); } node_set.insert(start.clone()); println!("prime最小生成树: "); while let Some(Reverse(edge)) = min_heap.pop() { let from = g.nodes.get(&edge.inner().from).unwrap(); let to = g.nodes.get(&edge.inner().to).unwrap(); if node_set.contains(from) && node_set.contains(to) { continue; } println!("{}, ", edge); let node = if !node_set.contains(from) { from } else { to }; node_set.insert(node.clone()); for e in &node.inner().edges { if !edge_set.contains(e) { min_heap.push(Reverse(e.clone())); } } } println!("END]"); }
-
单元最短路径
- 图中某节点到各个节点的最短路径
- Dijkstra算法(要求:没有权值为负的环)
- 初始化表:w: [0, MAX, MAX, MAX, MAX]
- w[0]表示A->A的距离为0
- w[1]:A -> B的距离为MAX
- 每次找距离最短的点
- 找出A点
- A有3条路:AB(3), AC(15), AD(9)
- A沿路向下走,并更新距离表w
- 路3到B,有
A(0) + 3 -> B(0+3=3) < B(MAX)
,更新w[1] = 3 - 路15到C:
A(0) + 15 -> C(0+15=15) < C(Max)
,w[2] = 15 - 路9到D:
A(0) + 9 -> D(9) < D(Max)
,更新w[3] = 9 - 距离表更新为 w:[0, 3, 15, 9, MAX]
- 路3到B,有
- 锁定A点
- 从剩余节点中找距离最小的节点
- 找到节点B
- B有3条路:BA(3), BC(2), BE(200)
- B沿路向下走,并更新距离表w
- 沿路3到A:
B(3) + 3 = A(6) > A(0)
,不更新 - 沿路2到C:
B(3) + 2 = C(5) < C(15)
,更新w[2] = 5 - 沿路200到E:
B(3) + 200 = E(203) < E(Max)
,更新w[4] = 203 - 距离表更新为 w: [0, 3, 5, 9, 203]
- 沿路3到A:
- 锁定B点
- 循环:从剩余节点中找距离最小的节点
- 初始化表:w: [0, MAX, MAX, MAX, MAX]
-
算法实现
/* 查询最小距离的节点 */ fn get_min_w<T>( weight_map: &HashMap<RefNode<T>, i32>, set: &HashSet<RefNode<T>>, ) -> Option<RefNode<T>> { let mut min_w = i32::MAX; let mut res = None; weight_map.iter().for_each(|(node, &weight)| { if !set.contains(node) && weight < min_w { min_w = weight; res = Some(RefNode(node.0.clone())); } }); res } /* 更新不在锁定集中的距离表元素 */ fn update<T>(distance_map: &mut HashMap<RefNode<T>, i32>, node: &RefNode<T>) { let distance = *distance_map.get(node).unwrap(); node.0.borrow().edges.iter().for_each(|edge| { distance_map .entry(RefNode(edge.0.borrow().to.0.clone())) .and_modify(|w| *w = cmp::min(*w, distance + edge.0.borrow().weight)); }); } fn dijkstra<T: Copy>(graph: &Graph<T>, start: &RefNode<T>) -> Vec<(T, i32)> { // 锁定走过的节点 let mut cloked: HashSet<RefNode<T>> = HashSet::new(); // 距离表 [0, MAX, MAX, MAX, ...] let mut distance_map: HashMap<RefNode<T>, i32> = HashMap::new(); graph.nodes.values().for_each(|node| { distance_map.insert(RefNode(node.0.clone()), i32::MAX); }); distance_map .entry(RefNode(start.0.clone())) .and_modify(|w| *w = 0); while let Some(min_w_node) = get_min_w(&distance_map, &cloked) { if !cloked.contains(&min_w_node) { update(&mut distance_map, &min_w_node); cloked.insert(min_w_node); } } let mut res: Vec<(T, i32)> = vec![]; distance_map.iter().for_each(|(node, weight)| { res.push((node.0.borrow().elem, *weight)); }); res }
- 新练习
fn find_node(g: &Graph<T>, no: T) -> NodeLink<T> { g.nodes.get(&no).unwrap().clone() } fn find_mindist( node_dist: &HashMap<NodeLink<T>, u32>, set: &HashSet<NodeLink<T>>, ) -> NodeLink<T> { let mut minval: u32 = u32::MAX; let mut node: NodeLink<T> = NodeLink(None); for (k, v) in node_dist { if set.contains(k) { continue; } if minval > *v { minval = *v; node = k.clone(); } } node } fn dijkstra(g: &Graph<T>, start: &NodeLink<T>) { let mut node_dist: HashMap<NodeLink<T>, u32> = HashMap::new(); let mut set: HashSet<NodeLink<T>> = HashSet::new(); for node in g.nodes.values() { node_dist.insert(node.clone(), u32::MAX); } node_dist.insert(start.clone(), 0); let mut node = start.clone(); while node.is_some() { for edge in &node.inner().edges { let to = Graph::find_node(g, edge.inner().to); let from = Graph::find_node(g, edge.inner().from); let origin_dist = *node_dist.get(&to).unwrap(); let new_dist = *node_dist.get(&from).unwrap() + edge.inner().weight as u32; if origin_dist > new_dist { *node_dist.get_mut(&to).unwrap() = new_dist; } } set.insert(node.clone()); node = Graph::find_mindist(&node_dist, &set); } print!("Djkstra [A] 到其他节点的最短路径:"); for (k, v) in &node_dist { print!("({}: {}) ", k.inner().no, v); } println!() }
Hash的实现
当出现如下错误时:
the method `insert` exists for struct `HashSet<Rc<RefCell<graph::Node>>>`, but its trait bounds were not satisfied
the following trait bounds were not satisfied:
`Rc<RefCell<graph::Node>>: Eq`
`Rc<RefCell<graph::Node>>: Hash`rustcE0599
- 想到通过系统的
#[derive(Hash, PartialEq, Eq)]
来实现这个类型的Hash
特性 - 那么首先尝试为
Node
实现Eq和Hash - 结果出现
RefCell<graph::Node>: Hash
不满足- 由于孤儿规则,我们无法实现:
impl Hash for RefCell<T>
- 因为
RefCell
类型不在我们的代码中定义 - 只能为
RefCell
在我们的代码中单独包装一个类型 - 又因为对
RefCell<T>
的Hash,我用T的地址作为Hash计算值 - 所以把
Rc<RefCell<T>>
包装成一个好了,可以认为它的地址就是T的地址
- 由于孤儿规则,我们无法实现:
-
所以重新定义一个
RefNode
结构体,为它实现Hash, Eq
特性struct RefNode{ link: Rc<RefCell<Node>> }; impl Hash for RefNode { fn hash<H: Hasher>(&self, state: &mut H) { (self.link.as_ptr()).hash(state) } } impl PartialEq for RefNode { fn eq(&self, other: &Self) -> bool { self.link.as_ptr() == other.link.as_ptr() } } impl Eq for RefNode {} impl RefNode { fn new(elem: i32) -> Self { Self(Rc::new(RefCell::new(Node::new(elem)))) } }
Eq
是一个标签,如果用系统的#[derive(Eq)]
,它会要求Node也实现Eq,但我们这里不需要,所以自己定义了Eq
,让它直接使用PartialEq
BinaryHeap 最大/最小堆
用二叉堆实现的优先队列,默认是最大堆
当一个项目在堆中时,如果对其进行修改,使其相对于任何其他项目的顺序发生变化(由Ord特性决定),这是一个逻辑错误。这通常只能通过单元格、RefCell、全局状态、I/O或不安全代码来实现。这种逻辑错误导致的行为没有被指定,但不会导致未定义行为。这可能包括恐慌、不正确的结果、中止、内存泄漏和不终止。
创建一个最大堆
let heap = BinaryHeap::from([1, 5, 2]);
创建最小堆
use std::cmp::Reverse;
let mut heap = BinaryHeap::new();
heap.push(Reverse(1));
heap.push(Reverse(5));
heap.push(Reverse(2));
assert_eq!(heap.pop(), Some(Reverse(1)));
assert_eq!(heap.pop(), Some(Reverse(2)));
assert_eq!(heap.pop(), Some(Reverse(5)));
assert_eq!(heap.pop(), None);
Eq 和 Ord 的区别
- Eq, PartialEq
- 用于
==
的计算 - 结果是true/false
- 用于
- Ord, PartialOrd
- 用于比较运算
- 结果是
Ording::[Less, Equal, Greater]