链式前向星
介绍
链式前向星是一种用于存图的数据结构,比较适用于存稀疏图.其综合了邻接表,邻接矩阵的优缺点,然后在前向星的基础上进行改进.
时间复杂度,空间复杂度,查询复杂度都是O(m)
初始化
1
2
3
4
| void CFSInit() { // 链式前向星初始化
cnt = 1; // 其实这里是0也无所谓
memset(head, 0, sizeof(head));
}
|
插入
1
2
3
4
5
6
| void add(int u, int v, int w) { // 有向边,无向图需要正反各加一次
edge[cnt].w = w;
edge[cnt].e = v; //edge[i]表示第i条边的终点
edge[cnt].next = head[u]; //head[i]表示以i为起点的最后一条边的储存位置
head[u] = cnt++;
}
|
遍历某点的所有出边
1
2
3
4
| int start;
cin >> start;
for (int i = head[start]; i != 0; i = edge[i].next)
cout << start << "->" << edge[i].e << " " << edge[i].w << endl;
|
模板
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
| #include<bits/stdc++.h>
using namespace std;
#define MAXN 100501
struct NODE{
int w;
int e;
int next; //next[i]表示与第i条边同起点的上一条边的储存位置
}edge[MAXN];
int cnt;
int head[MAXN];
void add(int u,int v,int w){
edge[cnt].w=w;
edge[cnt].e=v; //edge[i]表示第i条边的终点
edge[cnt].next=head[u]; //head[i]表示以i为起点的最后一条边的储存位置
head[u]=cnt++;
}
int main(){
memset(head,0,sizeof(head));
cnt=1;
int n;
cin>>n;
int a,b,c;
while(n--){
cin>>a>>b>>c;
add(a,b,c);
}
int start;
cin>>start;
for(int i=head[start];i!=0;i=edge[i].next)
cout<<start<<"->"<<edge[i].e<<" "<<edge[i].w<<endl;
return 0;
}
|
