数据结构-图实验 · Auceptin's Blog

实现一个邻接表

基本结构，一个链表头结点vec代指每个顶点

type Link= Option<Box<Node>>;
//第一项表示起始节点索引，第二项表示指向节点索引
struct Edge(usize, usize);

struct Graph{
    // 图是一个链表头结点向量
    vertices:Vec<Head>,
}

struct Head{
    //头结点，同时记录出度
    index: usize,
    len : usize,
    first:Link,
}

#[derive(Clone)]
// 节点，依据索引排序，记录权重
struct Node{
    weight : isize,
    index : usize,
    next : Link,
}

impl Graph{
    fn new(size:usize)->Graph{
        let mut vertices = Vec::with_capacity(size);
        for i in 0..size {
            vertices.push(Head::new());
            vertices[i].index = i +1;
        }
        Graph { vertices }
    }

    fn create(&mut self , input : Vec<Edge>){
        for edge in input {
            let in_v = edge.0 - 1;
            let ex_v = edge.1;
            print!("{}插入",in_v);
            self.vertices[in_v].insert(&edge);
        }
    }

    fn create_unorder(&mut self , input : Vec<Edge>){
        for edge in input {
            let in_v = edge.0 - 1;
            let ex_v = edge.1 - 1;
            print!("{}插入",in_v);
            self.vertices[in_v].insert(&edge);
            self.vertices[ex_v].insert(&edge.reverse());
        }
    }

    fn print(&self){
        for v in &self.vertices{
            v.print();
        }
    }
}


impl Head{
    fn new() -> Head{
        return Head{len:0,first:None,index:0};
    }

    fn insert(&mut self, edge:&Edge){
        println!("{}",edge.1);
        let index : usize = edge.1;
        let weight = 1; // 不涉及，默认
        //处理为空
        if self.len == 0{
            self.first = Some(Box::new(Node{weight,index,next:None}));
            self.len += 1;
            return;
        }
        // 处理仅有一个节点但是不访问第二个节点
        if let Some(ref mut first_node) = self.first {
            if first_node.index > index {
                let new_node = Node {
                    weight,
                    index,
                    next: self.first.take(),
                };
                self.first = Some(Box::new(new_node));
                self.len += 1;
                return;
            } else if first_node.index == index {
                // 重复索引，不处理
                return;
            }
        }
        //
        let mut current = &mut self.first;
        while let Some(node) = current{
            if let Some(ref next_node) = node.next {
                if next_node.index == index {
                    // 重复索引，不处理
                    return;
                } else if next_node.index > index {
                    // 在当前位置插入
                    let new_node = Node {
                        weight,
                        index,
                        next: node.next.take(),
                    };
                    node.next = Some(Box::new(new_node));
                    self.len += 1;
                    return;
                }
                // 继续向后遍历
                current = &mut node.next;
            } else {
                // 到达链表末尾，在末尾插入
                let new_node = Node {
                    weight,
                    index,
                    next: None,
                };
                node.next = Some(Box::new(new_node));
                self.len += 1;
                return;
            }
        }

    }

    fn print(&self){
        print!("顶点{}通向的边有：",self.index);
        let mut current = &self.first;
        while let Some(node) = current{
            print!("{} ",node.index);
            current = &node.next;
        }
        println!("");
    }
}

impl Edge{
    fn reverse(&self) -> Edge{
        return Edge(self.1, self.0);
    }
}

#[cfg(test)]
mod test{
    use super::{Edge, Graph};
    #[test]
    fn test_create(){
        let edges : Vec<Edge> = vec![Edge(1,2),Edge(1,3)];
        let mut g = Graph::new(5);
        g.create_unorder(edges);
        g.print();
    }
}

图遍历的演示

[问题描述]

很多涉及图操作的算法都是以图的遍历操作为基础的。试写一个程序，演示无向图的遍历操作。

[基本要求]

以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历方式的结点访问序列和相应生成树的边集。

[测试数据]

依据软件工程的测试技术自己确定，注意测试边界数据，如单个结点。

[实现提示]

设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1, 2, …, n）。通过输入图的全部边的方式输入一个图，每条边为一个数对，可以对边的输入顺序做出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。

实现

首先是dfs，需要额外的数据结构来记录节点被访问与结果，结果包括节点访问序列和生成树，需要处理好两种索引之间的转换

因为进入递归时没有调用者，所以需要caller是Option的

fn dfs(&self, start: usize)-> (Vec<usize>, Vec<Edge>) {
    let mut visited = HashSet::new();
    let mut result = Vec::new();
    let mut spanning_tree = Vec::new();
    self.dfs_recursive(start - 1, &mut visited, &mut result, &mut spanning_tree, None);
    //输出
    for i in result.clone() {
        print!("{} ",i);
    }
    (result, spanning_tree)
}

fn dfs_recursive(&self, node: usize, visited: &mut HashSet<usize>, result: &mut Vec<usize>, spanning_tree: &mut Vec<Edge>, caller: Option<usize>) {
    if visited.contains(&node) {
        return;
    }

    visited.insert(node);
    result.push(node + 1); // 1-based 索引
    if let Some(caller_node) = caller {
        spanning_tree.push(Edge(caller_node + 1, node + 1));
    }
    // 遍历所有邻居
    let mut current = &self.vertices[node].first;
    while let Some(node_ptr) = current {
        let neighbor = node_ptr.index - 1; // 转换为 0-based 索引
        self.dfs_recursive(neighbor, visited, result, spanning_tree, Some(node));
        current = &node_ptr.next;
    }
}

#[test]
fn test_dfs() {
    let edges: Vec<Edge> = vec![
        Edge(1, 2),
        Edge(1, 3),
        Edge(2, 4),
        Edge(2, 5),
        Edge(3, 6),
        Edge(3, 7),
    ];
    let mut g = Graph::new(7);
    g.create(edges);

    let dfs_result = g.dfs(1);
    assert_eq!(dfs_result,vec![1,2,4,5,3,6,7]);
    let expected_edges = vec![
        Edge(1, 2),
        Edge(2, 4),
        Edge(2, 5),
        Edge(1, 3),
        Edge(3, 6),
        Edge(3, 7),
    ];
    assert_eq!(dfs_result.1, expected_edges);
}

然后是bfs，思路类似，同样用一个hashset记录visited，一个vec记录结果，把递归换成队列

fn bfs(&self, start: usize) -> (Vec<usize>, Vec<Edge>) {
    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();
    let mut result = Vec::new();
    let mut spanning_tree = Vec::new();

    queue.push_back(start - 1); // 转换为 0-based 索引
    visited.insert(start - 1);

    while let Some(node) = queue.pop_front() {
        result.push(node + 1); // 转换回 1-based 索引

        // 遍历所有邻居
        let mut current = &self.vertices[node].first;
        while let Some(node_ptr) = current {
            let neighbor = node_ptr.index - 1;
            if !visited.contains(&neighbor) {
                visited.insert(neighbor);
                queue.push_back(neighbor);
                spanning_tree.push(Edge(node + 1, neighbor + 1));
            }
            current = &node_ptr.next;
        }
    }

    (result,spanning_tree)
}

#[test]
fn test_bfs(){
    let edges: Vec<Edge> = vec![
        Edge(1, 2),
        Edge(1, 3),
        Edge(2, 4),
        Edge(2, 5),
        Edge(3, 6),
        Edge(3, 7),
    ];
    let mut g = Graph::new(7);
    g.create(edges);

    let bfs_result = g.bfs(1);
    assert_eq!(bfs_result.0,vec![1,2,3,4,5,6,7]);
    let expected_edges = vec![
        Edge(1, 2),
        Edge(1, 3),
        Edge(2, 4),
        Edge(2, 5),
        Edge(3, 6),
        Edge(3, 7),
    ];
    assert_eq!(bfs_result.1, expected_edges);
}

借助于栈类型（自己定义和实现）将深度优先遍历用非递归算法实现

没想到什么优雅地记录生成树的办法，只能使用额外的空间记录每个节点的父节点

 fn dfs_aio(&self, start: usize)-> (Vec<usize>, Vec<Edge>){
    let mut visited = HashSet::new();
    let mut stack = Vec::new();
    let mut result = Vec::new();
    let mut spanning_tree = Vec::new();
    let mut parent = vec![None; self.vertices.len()];

    stack.push(start - 1); // 转换为 0-based 索引

    while let Some(node) = stack.pop() {
        if visited.contains(&node) {
            continue;
        }

        visited.insert(node);
        result.push(node + 1); // 转换回 1-based 索引

        // 记录生成树边（如果不是起始节点）
        if let Some(parent_node) = parent[node] {
            spanning_tree.push(Edge(parent_node + 1, node + 1));
        }

        // 将邻居按逆序压入栈中
        let mut neighbors = Vec::new();
        let mut current = &self.vertices[node].first;
        while let Some(node_ptr) = current {
            let neighbor = node_ptr.index - 1;
            if !visited.contains(&neighbor) {
                neighbors.push(neighbor);
                // 记录父节点关系
                parent[neighbor] = Some(node);
            }
            current = &node_ptr.next;
        }

        // 逆序压入栈
        for neighbor in neighbors.iter().rev() {
            stack.push(*neighbor);
        }
    }

    (result, spanning_tree)
}

实现有向图的遍历操作

以上均适配有向图操作