Hexo
0%

链式前向星

发表于 更新于 分类于
链式前向星学习笔记

今天王佬给我讲了链式前向星，非常开心，去年暑假的时候学了一次，后来就再也没学会，这次终于又又又会了，希望以后别忘记。
一、前期准备
1、首先以边的出发节点为分类节点，对有向边进行分类，分类节点为u，与u相连的所有节点代号为v。w数组记录的是u、v之间的边权。
2、一个数组用来记录节点的编号v，w数组记录的是u、v之间的边权。next数组记录的是同样与u节点相连的下一个v节点的值。
3、需要一个index变量来记录数组的使用情况。其实链式前向星将所有的节点编号v和边权w全部存在对应的两个数组中，每存完一个边就令index的值加一。以节点为例，从物理存储上看所有的节点v都存在了一个数组中，只不过链式前向星巧妙地使用next数组对齐进行了串联，将所有出发节点为u的边的终止节点v都串在了一起。所以head[u]的本质就是最后一个以u为分类节点的v所在的数组中的index。
二、头插法
链式前向星是一个链表，这个链表的维护采用的是头插法，就是每次记录的是与节点u相连的其他节点v串成的链表的头结点，需要的时候就会往链表头结点后面插入一个节点，节点序号为v。

1
2
3
4
5
6
void add(int u, int v, int w) {
    e[index] = v;//e数组负责记录v的值
    w[index] = w;//w数组负责记录u、v两点之间的边权
    next[index] = head[u];//因为head[u]里面记录着上一个v的index信息，所以这里使用没有经过更新的head[u]来更新next数组的信息
    head[u] = index++;//将这次加入分类节点链表的v的index更新到head[u]数组中
}

就比如想要插入的边为（1，2，1）和（1，3，1）。首先，将head[u]的值初始化为-1，证明这个head指针后面没有节点。假设此时index = 0。
分类节点为1，所以有

1
2
3
4
e[0] = 2;//e数组记录v的值
w[0] = 1;//w数组记录的是对应index位置v和u的边权为1
next[0] = -1;//此时最先插入该分类节点链表中的节点的next为-1，是表的终点的标志
head[1] = 0;//表示此时head指向了index 0，意味着分类节点为1的链表上一个v被存放在了数组0号位置

下面是头插法在已经有了一个节点的链表中插入一个节点

1
2
3
4
e[1] = 3；//e数组记录v的值
w[1] = 1;//w数组记录的是对应index位置v和u的边权为1
next[1] = head[1] = 0;//此时插入链表的节点在头结点的下一个，它的下一个节点是前一次插入的节点
head[1] = 1;//表示此时head指向了index 1，意味着分类节点为1的链表上一个v被存在了数组1号位置

三、链式前向星的遍历

1
2
3
4
5
6
7
8
for(int i = head[index]; i != -1; i = next[i]) {
    int j = e[i];
    
    if(dis[j] > dis[index] + w[i]) {
        dis[j] = dis[index] + w[i];
        que.push({dis[j], j});
    }
}

四、链式前向星实现Dj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>

using namespace std;

const int N = 200010, M = 200010;

typedef pair<int, int> PII;

int head[M], e[M], w[M], ne[M], idx;

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = head[a];
    head[a] = idx++;
}

int n, m;

int dis[N];

int dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII> > que;
    que.push({0, 1});
    
    while(que.size()) {
        auto t = que.top();
        que.pop();
        
        int d = t.first;
        int id = t.second;
        
        if(dis[id] < d) continue; //加一个小优化，不然会TLE
        
        for(int i = head[id]; i != -1; i = ne[i]) {
            int j = e[i];
            
            if(dis[j] > dis[id] + w[i]) {
                dis[j] = dis[id] + w[i];
                que.push({dis[j], j});
            }
        }
    }
    
    if(dis[n] == 0x3f3f3f3f) return -1;
    else return dis[n];
}

int main() {
    scanf("%d%d", &n, &m);
    memset(head, -1, sizeof head);
    
    for(int i = 0; i < m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
    }
    printf("%d", dijkstra());
    return 0;
}