图的前向星表示（带注释）

发表于 更新于 分类于

该内容在紫书中有详述

这里贴一份模板方便讲解使用

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
//////////////////////////////////////////////////
// 链式前向星建图

const int maxN = 1100;
const int maxM = 110000;
int first[maxN];    // 每个顶点发出的边的边链表头结点，该数组可初始化为 -1 表示每个顶点都还没有边
int nex[maxM];      // 同个顶点发出的边的边结点 next 域
int u[maxM];        // 边的发出顶点
int v[maxM];        // 边的收入顶点
int w[maxM];        // 边的权值
int tp;             // 全局“内存分配”“指针”，就是模拟分配内存时，tp从0开始逐个增加

// 比如 first[1]，表示顶点 V1 发出的第一条边的“指针”，这里就是数组编号
// nex[first[1]] 表示顶点 V1 发出的边的链表的第二个结点编号
// nex[nex[first[1]]] 表示顶点 V1 发出的边的链表的第三个结点编号 ...
// u[first[1]] 顶点 V1
// v[first[1]] 顶点 V1 发出的第一条边的另一端的顶点编号，比如 v[first[1]] == 3 就表示 V1 连着 V3
// w[first[1]] 顶点 V1 发出的第一条边的权值

void AddEdge(int s, int e, int weight)
{
    // 建图：表示顶点 s 向顶点 e 发出了一条权重为 weight 的有向边
    // 程序开始时 tp 初始为 0
    nex[tp] = first[s]; // 类似链表头插法
    first[s] = tp;
    u[tp] = s;
    v[tp] = e;
    w[tp] = weight;
    tp ++;
}
void DbEdge(int s, int e, int weight)
{
    // 如果表示无向图，那简单，两个方向都建一条有向边就好
    AddEdge(s, e, weight);
    AddEdge(e, s, weight);
    // 结合 tp 的属性，你会发现，可以很容易找到两个顶点之间成对的双向边
    // 比如 i 是 s 发向 e 的边的编号，那么 i^1 （异或操作） 就是 e 发向 s 的边
}

//////////////////////////////////////////////////
// 以深度优先搜索为例遍历全图，感受前向星的使用
bool vis[maxN] = {0};
void DFS(int now)
{
    for(int i = first[now]; i != -1; i = nex[i])
    {
        // 类似链表访问过程，i = first[now] 从头结点获得第一条边的指针
        // i = nex[i] 即链表指针域往后遍历
        // i != -1 即判断是否到链表末尾
        // u[i]、v[i]、w[i] 都是链表结点的数据域，当然你可以把 nex、u、v、w 封装在 struct 里
        if(!vis[v[i]])
        {
            vis[v[i]] = true;
            DFS(v[i]);
        }
    }
}
//////////////////////////////////////////////////
// 以迪杰斯特拉最短路算法体验前向星的使用
#include<queue>
#include<algorithm>
struct Node
{
    int vNum;
    int pathLen;
    Node(){}
    Node(int v_, int p_){vNum = v_, pathLen = p_;}
    bool operator<(const Node &b)const
    {
        return pathLen > b.pathLen;
    }
};
int key[maxN];  // 动态更新每个结点与起点的距离
int Dijkstra(int s, int e)
{
    memset(key, 0x3f, sizeof(key));
    key[s] = 0;
    std::priority_queue<Node> q;
    q.push(Node(0, 0));
    while(!q.empty())
    {
        Node now = q.top();
        q.pop();
        if(now.pathLen != key[now.vNum])
            continue;
        if(now.vNum == e)
            return now.pathLen;
        for(int i = first[now.vNum]; i != -1; i = nex[i])
        {
            if(now.pathLen + w[i] < key[v[i]])
            {
                key[v[i]] = now.pathLen + w[i];
                q.push(Node(v[i], key[v[i]]));
            }
        }
    }
    return 0x3f3f3f3f;
}