图
- 广度优先、深度优先算法
- 拓扑排序算法, 最小生成树, 单元最小距离
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
}

新练习

  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]
  - 锁定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
  }

新练习

  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]

上篇Rust·算法·二叉树

下篇Rust·算法基础·前缀树·贪心算法