图的储存
***图，通俗地说是由边和点组成的，一条边连接两个点，边会有权值（点也会有，直接用数组储存即可，不做讨论）***。
设有
n
n
n个点，
m
m
m条边。
方式1.邻接矩阵
设
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示从
i
i
i到
j
j
j的边的权值。
按题目要求，当
i
i
i到
j
j
j有多条边时，选取贡献最大的一条。
空间复杂度：
O
(
n
2
)
O(n^2)
O(n2)。
优点：实现简单，使用方便。
缺点：空间太大，一般的题目都存储不下。
方式2.邻接表
设
p
[
i
]
p[i]
p[i]表示
i
i
i点的出度，
g
[
i
]
[
j
]
g[i][j]
g[i][j]为从
i
i
i出发可到达的第
j
j
j个点，
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示
g
[
i
]
[
j
]
g[i][j]
g[i][j]对应的边权。
空间复杂度：随机数据时一般小于
O
(
n
2
)
O(n^2)
O(n2)，当出现一个点与其余的所有点相连时
O
(
n
∗
m
)
O(n*m)
O(n∗m)。
优点：随机数据下空间较小。
缺点：极限数据浪费空间大。
方式3.边集数组
设
f
[
i
]
.
f
r
f[i].fr
f[i].fr，
f
[
i
]
.
t
o
f[i].to
f[i].to，
f
[
i
]
.
l
e
n
f[i].len
f[i].len分别表示第
i
i
i条边的起点、终点和权值。
空间复杂度：
O
(
m
)
O(m)
O(m)
优点：节约空间。
缺点：搜索时需要把所有的边枚举一遍，太浪费时间。
方式4.排序前向星
和上一点类似。
在边集数组的基础上按
f
[
i
]
.
f
r
f[i].fr
f[i].fr排序，然后设
h
[
i
]
h[i]
h[i]表示以
i
i
i为起点的边在
f
f
f数组中最早出现的位置，每次只需从
f
[
h
[
x
]
]
f[h[x]]
f[h[x]]开始往下搜索，直到当前的
f
[
i
]
≠
x
f[i]≠x
f[i]̸=x。
优点：节约空间。
缺点：排序时间大。
方式5.链式前向星
f
f
f数组同上。我们想办法减去排序的时间。
设
l
a
s
t
[
i
]
last[i]
last[i]表示以
i
i
i为起点的边在
f
f
f数组中最后一次出现的位置，设
n
e
x
t
[
i
]
next[i]
next[i]表示起点为
f
[
i
]
.
f
r
f[i].fr
f[i].fr的边在第
i
i
i条边之前上一次出现的位置。
从
i
=
l
a
s
t
[
x
]
i=last[x]
i=last[x]开始，每次
i
=
n
e
x
t
[
i
]
i=next[i]
i=next[i]，直到
i
=
0
i=0
i=0，即可快速找出所有以
x
x
x为起点的边。
void add(int x,int y,int l)
{
f[++num].fr=x,f[num].to=y,f[num].len=l;
next[num]=last[x];
last[x]=num;
}
void find(int x)
{
for(i=last[x];i;i=next[i]) search();
}
优点：快速且节约空间。
缺点：暂无。
以上为图的储存各种方式，我们要按照需要选取最合适的方式。