图论
存图
- 邻接矩阵:查找+稠密图 可用于矩乘递推
- 邻接表:遍历 预排序可将查询优化至O(logm)
- 链式前向星:遍历+可储存边的信息 每个节点对应一个链表串联起储存的边
struct edge {
int u, v, w;
};
vector<int> head(n + 1, -1), e, nxt;
// 链表储存对应元素下标
void add_edge(int u, int v, int w) {
e.ep({u, v, w});
nxt.ep(head[u]);
// 同时扩增,下标一致性
head[u] = e.size() - 1;
}
for (int i = head[u]; ~i; i = nxt[i]) { // ~i相当于i!=-1
cout << e[i].u << " " << e[i].v << " " e[i].v;
}
// 遍历链表(e对应下标)
// 链表初始是-1,不断从开头扩展链表,故最终遍历到-1结束