Skip to content

Graph｜链式前向星

链式前向星存图

截屏2024-10-28 10.06.39

对于上面这张图，链式前向星存储它的边。

截屏2024-10-28 10.06.54

顶点 第一条相连的边 第二条相连的边 第三条相连的边 第四条相连的边
1 1 4 5 NULL
2 2 NULL
3 3 6 NULL
4 NULL
5 NULL

链式前向星有 head[] 数组，通过 head[u] 和 next[] 可以访问以该节点为起点的"所有边"

把从每个节点 u 出发的边用链表链起来，这样只要记录 head[u] 表示节点 u 边表的第一条边是谁就可以了

节点 边表中的第一条边 边表中的第二条边 边表中的第三条边 边表中的第四条边
u head[u] next[head[u]] next[next[head[u]]] next[next[next[head[u]]]
1 5 4 1 NULL
2 2 NULL
3 6 3 NULL

具体实现

数据结构定义

1
2
3
4
5
6
7
struct Edge{
    int to;
    int w;
    int next;
} edges[N];
int head[N];
int cnt = 0;
  • to: 边的终点
  • w: 边的权值
  • next: 代表与这条边起点相同的上一条边的编号
  • head[i]: 以 i 为起点的最后一条边的编号
  • cnt: 边数，用以给边编号

加边函数

1
2
3
4
5
6
7
void add_edge (int u, int v, int w) {   // u:起点; v:终点
    cnt++;  // 边的编号
    edges[cnt].to = v;  // 终点
    edges[cnt].w = w;   
    edges[cnt].next = head[u];  // 同起点的上一条边
    head[u] = cnt;  // 更新自己为"上一条边"
}

读入一张有 n 个顶点，m 条边的无向图:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int n, m;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, & w);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    ...
    return 0;
}

遍历点的邻边

对于顶点 u ，从以 u 为起点的最后一条边 head[u] 开始，循环查找上一条边，直到遇见 NULL (0)

1
2
3
for (int i = head[u]; i != 0; i = edges[i].next) {
    ...
}

dfs 遍历图

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void dfs(int u, int fa) {
    ...
    for (int i = head[u]; i != 0; i = edges[i].next) {
        if (edges[i].to != fa && !vis[edges[i].to]) {
            // edges[i].to != fa 一句若为无向图则需加上，防止死循环
            vis[edges[i].to] = 1;
            dfs(edges[i].to, u);
            vis[edges[i].to] = 0;
        }
    }
}

上机题

计组 P2 上机一道有关图的题，要求用 MIPS 汇编解答。不过给出了 C 代码 (当时没看懂)，上机的时候就直接翻译了🌟

Q: n个顶点，m条边，编号为k的顶点能到达多少个出度为0的点

C代码:

 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
#include <stdio.h>
#define N 256
struct Edge{
    int to;
    int next;
}edges[N];

int head[N];    
int out[N];
int vis[N];
int edge_cnt = 0;
int n, m, k;
int cnt = 0;

void addEdge(int u, int v){
    out[u]++;
    edge_cnt++;
    edges[edge_cnt].to = v;
    edges[edge_cnt].next = head[u];
    head[u] = edge_cnt;     // 更新以u为起点的最后一条边的编号
}

void dfs(int u) {
    if (u != k && out[u] == 0) {
        cnt++;
        return;
    }
    for (int i = head[u]; i != 0; i = edges[i].next) {
        if (!vis[edges[i].to]) {
            vis[edges[i].to] = 1;
            dfs(edges[i].to);
            //vis[edges[i].to] = 0;     // 不能加这句!会重复计算!
        }
    }
}

int main(int argc, const char * argv[]) {

    scanf("%d%d%d", &n, &m, &k);
    int u, v;
    int i;
    for (i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);  // 从顶点u到顶点v的边
        addEdge(u, v);
    }

    vis[k] = 1;
    dfs(k);
    printf("%d\n", cnt);

    return 0;
}

参考资料:

博客园｜浅谈链式前向星

博客园｜链式前向星存图详细解析