- 图
- 广度优先、深度优先算法
- 拓扑排序算法, 最小生成树, 单元最小距离
- 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 }
深度优先搜索
- 算法
- 用栈
- 根节点入栈(入栈前打印节点)
- 当栈中还有节点时，循环
- 弹出节点
- 取出节点的一个不在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 }
拓扑排序算法
- 适用条件
- 有向图
- 有入度为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 }
最小生成树
- 概念
- 所有节点都连通，而节点间连通权值最小
- 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 } - 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 }
单元最短路径
- 图中某节点到各个节点的最短路径
- 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 }
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]