Rust·算法·图

 

图 广度优先、深度优先算法 拓扑排序算法, 最小生成树, 单元最小距离 BinaryHeap 最大/最小堆 如何为Rc<RefCell<T>>实现Hash特性 PartialEq和PartialOrd的区别

    • 广度优先、深度优先算法
    • 拓扑排序算法, 最小生成树, 单元最小距离
  • 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)
    • 更新
      • 更新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]
      • 锁定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]
      • 锁定B点
    • 循环:从剩余节点中找距离最小的节点
  • 算法实现

      /* 查询最小距离的节点 */
      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]