zzoce 🧊
链式前向星

链式前向星

Fri Oct 04 2024
zzcoe
2 分钟
数据结构与算法 图论
234 字

一种简单高效的存图方法，由邻接表演变而来，本质上是用链表实现的邻接表

特点：

  • 缺点：存各种图都很合适，但不能快速查询一条边是否存在，也不能方便地对一个点的出边进行排序
  • 优点：边是代编号的，有时会非常有用，而且如果tot的初始值为偶数，存双向边时i^1就是i的反边（常用于网络流），即第一条边在i的位置其反边在i+1的位置
CPP
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
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
const int maxn = 1e5+5;
struct E{
    int to,w,next;//节点，权值，指针
}Edge[maxn<<1];
int tot,Head[maxn];
inline void AddEdge(int u,int v,int w){
	Edge[tot].to=v;
    Edge[tot].w=w;
    Edge[tot].next=Head[u];//表头插入的方式
    Head[u]=tot++;
}
int main ()
{
    memset(Head,-1,sizeof (Head));//初始化链表结尾为1，相当于NULL
    int n;
    cin>>n;
    
    for (int i=1,u,v,w;i<=n;i++){
        cin>>u>>v>>w;
        AddEdge(u,v,w);
        AddEdge(v,u,w);
    }
    for (int u=1;u<=n;u++){
	    cout<<u;
    	for (int i=Head[u];~i;i=Edge[i].next){//对i按位取反，~(-1)==0;
			int v=Edge[i].to,w=Edge[i].w;
			cout<<"->"<<v<<","<<w;
		}
		cout<<endl;
	}
    return 0;
}