图的存储方式 - 链式前向星

对于点数较多的稀疏图,邻接矩阵无法容纳,而用 vector 实现的邻接表比较慢,于是就有了链式向前星这种存储结构。

说明

添加边:(fromtoval分别是边的起点,终点,权值)

add_edge(int from, int to, int val);

遍历p结点联结的所有边:

for (int i = head[p]; ~i; i = g[i].next)

初始化:

memset(head, -1, sizeof head);

模板

#include <iostream>
#include <stdio.h>
#include <cstring>
#define MAXN 10005
#define MAXM 100005
using namespace std;

struct node {
int to, next, val;
}g[MAXM * 2];

int gsize, head[MAXN];
inline void add_edge(int from, int to, int val) {
g[gsize].to = to;
g[gsize].next = head[from];
g[gsize].val = val;
head[from] = gsize++;
}

int main() {
memset(head, -1, sizeof head);
//visit
int p = 1;
for (int i = head[p]; ~i; i = g[i].next) {
int to = g[i].to;
int val = g[i].val;
}
return 0;
}