链式前向星
S宿舍666
·
·
个人记录
思想
目的
存入一个图
建立
结构体数组edge[ ].(zhi,to,next)，数组head[ ]，变量cnt。
原理
如同链表，edge代表链表，每个小节为每一条边，head[u]记录以u为起点第一条边
优点
可避免浪费不必要的空间，特别是存稀疏图的时候
时间复杂度
O_{(n)}
空间复杂度
O_{(n)}
样例
输入
暂无，后续会添加，欢迎提供
结果
暂无，后续会添加，欢迎提供
过程
edge[cnt].zhi=w//$第$cnt$条边的权值为$w
edge[cnt].to=v//$第$cnt$条边的指向$v
edge[cnt].next=head[u]//$下一条同起点的边的$cnt
$cnt++//$新的小节
#### **注意！！！**
把$cnt$初值设为$1$,与$head$数组的初值$0$区分
# 代码
### 设置
```cpp
struct eee{
int zhi;
int to;
int next;
}edge[];
int cnt=1,head[];
```
### 输入
```cpp
scanf("%d",&n);
for(int q=1;q<=n;q++){
scanf("%d%d%d",&u,&v,&w);
lian(u,v,w);
}
```
### 函数
```cpp
void lian(int u,int v,int w){
edge[cnt].zhi=w;
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
```
### 调用
```cpp
for(int q=1;q<=n;q++){
for(int e=head[q];e!=0;e=edge[e].next){
printf("%d %d %d\n",q,edge[e].to,edge[e].zhi);
}
}
```
###### 最新一次修改：2021-12-25，10：34：24