(标签-链表|关键词-结构体)

Question

这个结构体链表是怎么用的？定义结构体里面这个edge(){};有什么用？

#include<bits/stdc++.h>
using namespace std;
const int N=1001;
const int M=10001;
struct edge{
    int v,w,next;
    edge(){};
    edge(int _v,int _w,int _next){
        v=_v;
        w=_w;
        next=_next; 
    }
} e[M*2];
int head[N],size;
void init(){
    memset(head,-1,sizeof(head));
    size=0;
} 
void insert1(int u,int v,int w){
    e[size]=edge(v,w,head[u]);
    head[u]=size++;
}
void insert2(int u,int v,int w){
    insert1(u,v,w);
    insert1(v,u,w);
}
int n,m;
int dis[N];
bool vis[N];
void dijkstra(int u){
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    dis[u]=0;
    for(int i=0;i<n;i++){
        int mind=1000000000,minj=1;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&dis[j]<mind){
                minj=j;
                mind=dis[j];
            }
        }
        if(minj==-1){
            return ;
        }
        vis[minj]=true;
        for(int j=head[minj];j!=-1;j=e[j].next){
            int v=e[j].v;
            int w=e[j].w;
            if(!vis[v]&&dis[v]>dis[minj]+w){
                dis[v]=dis[minj]+w; 
            }
        }
    }
}
int main(){
    init();
    int u,v,w;
    cin>>n>>m;
    while(m--){
        cin>>u>>v>>w;
        insert2(u,v,w);
    }
    dijkstra(1);
    cout<<dis[n]<<endl;
    return 0;
} 

Answer 1

让【道友老李】来帮你解答，本回答参考gpt编写，并整理提供，如果还有疑问可以点击头像关注私信或评论。

如果答案让您满意，请采纳、关注，非常感谢！

这个问题涉及到链表和图的实现。针对代码中的结构体 `edge` 和相关链表的实现，我将逐步解答，并利用代码示例来详细解析其用法。

一、结构体 edge 的定义

struct edge {
    int v, w, next;
    edge() {}; // 默认构造函数
    edge(int _v, int _w, int _next) {
        v = _v;
        w = _w;
        next = _next; 
    }
};

解析： - edge 结构体表示图中的一条边，其中： - v 表示边的另一个端点（目标节点）。 - w 表示边的权重（成本）。 - next 是一个指向链表中下一个节点的指针（索引），用于实现邻接链表结构。

• 默认构造函数 edge() 是一个空构造函数，可以在不提供参数的情况下创建 edge 对象。它的存在使得这个结构体可以用于初始化数组或在需要时创建未赋值的边。

二、链表的用途

在图论中，使用链表存储图的边是常用的数据结构，特别是在稀疏图的场景。每一个节点的边 (edge) 通过 next 指向下一个边，形成一个链表。邻接链表相较于邻接矩阵更加节省空间，尤其适合节点较少但边较多的情况。

三、主要函数解析

1. 初始化链表

void init(){
    memset(head, -1, sizeof(head));
    size = 0;
}

• head[N] 数组用于存储每个节点的边的起始位置，初始化时将所有头指针设置为 -1。
• size 初始化为 0，表示当前边的数量。
• 插入边

void insert1(int u, int v, int w){
    e[size] = edge(v, w, head[u]); // 创建一条新边
    head[u] = size++; // 更新 head[u]，并递增size
}

• insert1 用于向链表中添加一条边从 u 到 v，权重为 w。新边存储在数组 e 中，并且更新 head[u] 指向新边在数组中的位置。
• 双向插入边

void insert2(int u, int v, int w) {
    insert1(u, v, w); // 插入 u 到 v
    insert1(v, u, w); // 插入 v 到 u，让图是无向图
}

• insert2 函数用于插入无向边 (双向边)。这对于构建无向图是必要的。

四、Dijkstra 算法实现

void dijkstra(int u) {
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    dis[u] = 0; // 起始节点到自身的距离为0
    for (int i = 0; i < n; i++) {
        int mind = 1000000000, minj = -1;
        for (int j = 1; j <= n; j++) { // 从1到n寻找最小的未访问节点
            if (!vis[j] && dis[j] < mind) {
                minj = j;
                mind = dis[j];
            }
        }
        if (minj == -1) {
            return; // 如果没有可访问的点，结束
        }
        vis[minj] = true; // 标记为已访问
        for (int j = head[minj]; j != -1; j = e[j].next) { // 遍历所有与minj相连的节点
            int v = e[j].v; // 目标节点
            int w = e[j].w; // 边权
            if (!vis[v] && dis[v] > dis[minj] + w) {
                dis[v] = dis[minj] + w; // 更新到目标节点的距离
            }
        }
    }
}

• Dijkstra 算法用于计算从起始节点到所有其他节点的最短路径。通过在每次循环中选择当前距离最小的未访问节点，更新与之相连的所有边的距离。

五、完整例子

假设输入图为：

5 6
1 2 2
1 3 4
2 3 1
2 4 7
3 5 3
4 5 1

int main() {
    init(); // 初始化链表
    int u, v, w;
    cin >> n >> m; // 读取节点和边的数量
    while (m--) {
        cin >> u >> v >> w; // 读取边的信息
        insert2(u, v, w); // 插入边
    }
    dijkstra(1); // 从节点1开始执行Dijkstra算法
    cout << dis[n] << endl; // 输出到节点n的最短距离
    return 0;
}

总结

• edge 结构体是链表中单个边的表达，利用 v, w, next 成员实现邻接链表结构。
• 通过 insert1 和 insert2 方法构建图的边，支持无向图。
• dijkstra 函数实现最短路径算法，通过链表遍历相连边来更新节点间的距离。 这样的结构和实现方式在图论算法中相当有效，能够高效处理稀疏图的边表。