面试题：Rust闭包在图算法中的应用

使用闭包处理权重计算逻辑：
- 在Dijkstra算法中，需要计算从一个节点到其邻居节点的权重。可以将权重计算逻辑封装在闭包中，这样可以根据具体的图结构和权重定义灵活调整计算方式。
- 例如，假设图的边权重存储在边结构体中，闭包可以接收边结构体并返回权重值。
闭包相较于普通函数的优势：
- 捕获环境变量：闭包可以捕获其定义所在作用域中的变量，这在需要根据外部状态动态调整权重计算逻辑时非常有用。例如，如果权重计算依赖于某个全局配置或动态变化的参数，闭包可以轻松捕获并使用这些变量，而普通函数则需要将这些变量作为显式参数传递。
- 代码简洁性和灵活性：闭包可以作为参数直接传递给其他函数，使代码结构更加紧凑。在复杂算法中，这种灵活性可以使代码更易于理解和维护，特别是在需要传递不同权重计算逻辑的情况下，无需定义多个不同签名的普通函数。
核心代码片段：

use std::collections::BinaryHeap;

// 定义图的节点和边
struct Node {
    id: usize,
    distance: i32,
}

impl Ord for Node {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        // 这里使用distance的反向排序，因为BinaryHeap默认是最大堆，而我们需要最小堆
        other.distance.cmp(&self.distance)
    }
}

impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Eq for Node {}

impl PartialEq for Node {
    fn eq(&self, other: &Self) -> bool {
        self.distance == other.distance
    }
}

struct Edge {
    to: usize,
    weight: i32,
}

type Graph = Vec<Vec<Edge>>;

fn dijkstra(graph: &Graph, start: usize, weight_calculator: &impl Fn(&Edge) -> i32) -> Vec<i32> {
    let mut distances = vec![std::i32::MAX; graph.len()];
    distances[start] = 0;
    let mut heap = BinaryHeap::new();
    heap.push(Node { id: start, distance: 0 });

    while let Some(Node { id, distance }) = heap.pop() {
        if distance > distances[id] {
            continue;
        }
        for edge in &graph[id] {
            let new_distance = distance + (weight_calculator)(edge);
            if new_distance < distances[edge.to] {
                distances[edge.to] = new_distance;
                heap.push(Node { id: edge.to, distance: new_distance });
            }
        }
    }
    distances
}

你可以这样调用这个函数：

fn main() {
    let graph: Graph = vec![
        vec![Edge { to: 1, weight: 1 }, Edge { to: 2, weight: 4 }],
        vec![Edge { to: 0, weight: 1 }, Edge { to: 2, weight: 2 }, Edge { to: 3, weight: 5 }],
        vec![Edge { to: 0, weight: 4 }, Edge { to: 1, weight: 2 }, Edge { to: 3, weight: 1 }],
        vec![Edge { to: 1, weight: 5 }, Edge { to: 2, weight: 1 }],
    ];
    let start = 0;
    let distances = dijkstra(&graph, start, &|edge| edge.weight);
    println!("{:?}", distances);
}

在上述代码中，weight_calculator 是一个闭包，通过 &impl Fn(&Edge) -> i32 这种泛型方式传递给 dijkstra 函数，在计算最短路径时动态计算权重。

星途面试题库

面试题：Rust闭包在图算法中的应用

知识考点

面试题答案