图论方法
考过的点
- 2024年省赛考察：最小生成树
- 2023年国赛考察：分层图（
01
B
F
S
01BFS
01BFS双端队列） - 2022年国赛考察：Floyd算法
2024国赛准备
重点掌握
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra、
S
P
F
A
SPFA
SPFA、
F
l
o
y
d
Floyd
Floyd、
P
r
i
m
Prim
Prim、
K
r
u
s
k
a
l
Kruskal
Kruskal基本思路和解题
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra算法(n个结点，m条边) 只能用于非负边权图- 朴素版：
O
(
n
2
)
O(n^2)
O(n2) 用于稠密图- 更新
n
−
1
n-1
n−1次，每次选取一个非s集合中的距离最小的结点，去更新每一个结点的距离。
- 更新
- 堆优化版：
O
(
m
l
o
g
n
)
O(mlogn)
O(mlogn) 用于稀疏图- 基本思路就是用堆去优化选取非s集合中的距离最小的结点。更新的化就是遍历与当前结点所有相邻的结点进行更新，只有当某个结点被更新时才放入堆中。
- 朴素版：
S
P
F
A
SPFA
SPFA算法(n个结点,m条边) 可以用于含有负权边的图- 时间复杂度：一般情况
O
(
m
)
O(m)
O(m) 最坏O
(
n
m
)
O(nm)
O(nm) - 基本思路：当一个结点的距离变小时，通过这个结点就有可能将到其他结点的距离减小。因此只需要建立一个队列，每次将距离变小的点放入队列即可，用队列中的点更新其他点。
- 时间复杂度：一般情况
F
l
o
y
d
Floyd
Floyd(n个结点) 多源最短路- 时间复杂度：
O
(
n
3
)
O(n^3)
O(n3) - 基本思路：每次利用一个结点(
k
k
k)更新所有结点(遍历(i
,
j
i,j
i,j))之间的距离。 k
,
i
,
j
k,i,j
k,i,j的方式枚举，转移：d
[
i
]
[
j
]
=
m
i
n
(
d
[
i
]
[
j
]
,
d
[
i
]
[
k
]
+
d
[
k
]
[
j
]
)
d[i][j] = min(d[i][j],d[i][k]+d[k][j])
d[i][j]=min(d[i][j],d[i][k]+d[k][j])
- 时间复杂度：
P
r
i
m
Prim
Prim(n个结点，m条边)- 朴素版：
O
(
n
2
)
O(n^2)
O(n2) 用于稠密图- 思路类似
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra - 更新n次(选n个点)，每次选取一个非s集合中距离集合最近的点，去更新不在集合s中的点到集合s的距离。
- 思路类似
- 堆优化版：
O
(
m
l
o
g
n
)
O(mlog n)
O(mlogn) 用于稀疏图- 思路也是类似于
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra - 注意点就是要用一个
c
n
t
cnt
cnt进行计数，判断最后是否能构成最小生成树。如果存在孤立点c
n
t
cnt
cnt肯定小于n
- 思路也是类似于
- 朴素版：
K
r
u
s
k
a
l
Kruskal
Kruskal(n个结点，m条边)- 时间复杂度：
O
(
m
l
o
g
m
)
O(mlogm)
O(mlogm) 用于稀疏图 - 基本思路：先用三元组把边存起来，然后按小到大排序，依次枚举每条边判断是否在一个集合中，不在一个集合中就加上这条边，并放到集合中，用并查集实现。
- 时间复杂度：
其他一些搜索算法的作用
多源
B
F
S
BFS
BFS
- 基本思想就是把所有的起点都先放进队列，然后再开始
B
F
S
BFS
BFS
- 基本思想就是把所有的起点都先放进队列，然后再开始
双端队列
- 主要就是解决权值有0有1的问题，权值为0的放入队列的左边，权值为1的放到队列的右边。与堆优化版
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra一样必须在出对时才知道每个点的最小值，而和一般的B
F
S
BFS
BFS不一样。
- 主要就是解决权值有0有1的问题，权值为0的放入队列的左边，权值为1的放到队列的右边。与堆优化版
双向广搜
- 主要解决的就是搜索空间爆炸的问题。基本思想就是用两个队列一个从起点
B
F
S
BFS
BFS一个从终点B
F
S
BFS
BFS，每次扩展一层。哪个队列的元素少就扩展哪一层。
- 主要解决的就是搜索空间爆炸的问题。基本思想就是用两个队列一个从起点
A*
- 基本思想是启发式搜索减少搜索空间，优化
B
F
S
BFS
BFS，比如第k
k
k短路问题，暴力做法就是B
F
S
BFS
BFS暴力搜索。这样的化状态空间直接爆炸。感觉应该是不会考察这东西。 - 上面那个问题是用
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra反向计算最短路作为到终点的估计值。然后A
s
t
a
r
Astar
Astar函数优先队列存放[
d
i
s
t
a
n
c
e
+
w
[
i
]
+
d
i
s
t
[
j
]
,
[
d
i
s
t
a
n
c
e
+
w
[
i
]
,
j
]
[distance+w[i]+dist[j],[distance+w[i],j]
[distance+w[i]+dist[j],[distance+w[i],j]其中d
i
s
t
a
n
c
e
distance
distance存放的是A
s
t
a
r
Astar
Astar的到当前点的距离，w
[
i
]
w[i]
w[i]是i
i
i这条边的长度，d
i
s
t
[
j
]
dist[j]
dist[j]表示结点j
j
j的估值函数的值也就是D
i
j
k
s
t
r
a
Dijkstra
Dijkstra计算的值。一个点出队k
k
k次表示当前的d
i
s
t
a
n
c
e
distance
distance是它的第k
k
k短路径。与D
i
j
k
s
t
r
a
Dijkstra
Dijkstra不同的是当枚举x
x
x临界点时，每个点都需要入队，而D
i
j
k
s
t
r
a
Dijkstra
Dijkstra则是更新了的点才入队。
- 基本思想是启发式搜索减少搜索空间，优化
