图论复习之前向星存图
引子
本来还没打算开始复习图论，今天做搜索题目的时侯要遍历单向边的图，我直觉用二维数组存图，存是方便，但是遍历复杂度比较高。只好复习一下更好的存图方式。
理论
性质
前向星是一种特殊的边集数组。
前向星数组对应的其实是边的信息，下标就是边的下标。
操作
把边集数组中的每一条边按照起点从小到大排序，如果起点相同就按照终点从小到大。并且记录下以某个点为起点的所有边在数组中的起始位置和存储边数。
\(len[i]\)数组记录以\(i\)为起点的边在数组中的存储边数。
\(head[i]\)数组记录以\(i\)为边集在数组中的第一个存储(起始)位置(哪条边)
举例
input
1 2
2 3
3 4
1 3
4 1
1 5
4 5
对边进行排序后
| 编号 | 起点 | 终点 |
|---|---|---|
| 1 | 1 | 2 |
| 2 | 1 | 3 |
| 3 | 1 | 5 |
| 4 | 2 | 3 |
| 5 | 3 | 4 |
| 6 | 4 | 1 |
| 7 | 4 | 5 |
len[1]=3, head[1]=1
len[2]=1, head[2]=4
len[3]=1, head[3]=5
len[4]=2, head[4]=6
代码
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int cnt = 0;
int head[N];
struct note{
int from;
int to;
int w;
}edge[N];
bool cmp(note a, note b){
if(a.from == b.from && a.to == b.to)return a.w < b.w;
if(a.from == b.from)return a.to < b.to;
return a.from < b.from;
}
void add(int u, int v, int w){
edge[cnt].from = u;
edge[cnt].to = v;
edge[cnt++].w = w;
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
}
sort(edge, edge + m, cmp);
memset(head, -1 ,sizeof(head));
head[edge[0].from] = 0;
for(int i = 1; i < m; i++){
if(edge[i].from != edge[i - 1].from)/
head[edge[i].from] = i;
}
int start;
scanf("%d", &start);
for(int k = head[start]; edge[k].from == start && k < m; k++){
cout << edge[k].from << " " << edge[k].to << " "<< edge[k].w << endl;
}
return 0;
}