图论方法
考过的点
- 2024年省赛考察:最小生成树
- 2023年国赛考察:分层图(
01
B
F
S
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
- 朴素版:
O
(
n
2
)
O(n^2)
- 更新
n
−
1
n-1
- 更新
- 堆优化版:
O
(
m
l
o
g
n
)
O(mlogn)
- 基本思路就是用堆去优化选取非s集合中的距离最小的结点。更新的化就是遍历与当前结点所有相邻的结点进行更新,只有当某个结点被更新时才放入堆中。
- 朴素版:
S
P
F
A
SPFA
- 时间复杂度:一般情况
O
(
m
)
O(m)
O
(
n
m
)
O(nm)
- 基本思路:当一个结点的距离变小时,通过这个结点就有可能将到其他结点的距离减小。因此只需要建立一个队列,每次将距离变小的点放入队列即可,用队列中的点更新其他点。
- 时间复杂度:一般情况
F
l
o
y
d
Floyd
- 时间复杂度:
O
(
n
3
)
O(n^3)
- 基本思路:每次利用一个结点(
k
k
i
,
j
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])
- 时间复杂度:
P
r
i
m
Prim
- 朴素版:
O
(
n
2
)
O(n^2)
- 思路类似
D
i
j
k
s
t
r
a
Dijkstra
- 更新n次(选n个点),每次选取一个非s集合中距离集合最近的点,去更新不在集合s中的点到集合s的距离。
- 思路类似
- 堆优化版:
O
(
m
l
o
g
n
)
O(mlog n)
- 思路也是类似于
D
i
j
k
s
t
r
a
Dijkstra
- 注意点就是要用一个
c
n
t
cnt
c
n
t
cnt
- 思路也是类似于
- 朴素版:
K
r
u
s
k
a
l
Kruskal
- 时间复杂度:
O
(
m
l
o
g
m
)
O(mlogm)
- 基本思路:先用三元组把边存起来,然后按小到大排序,依次枚举每条边判断是否在一个集合中,不在一个集合中就加上这条边,并放到集合中,用并查集实现。
- 时间复杂度:
其他一些搜索算法的作用
多源
B
F
S
BFS
BFS
- 基本思想就是把所有的起点都先放进队列,然后再开始
B
F
S
BFS
- 基本思想就是把所有的起点都先放进队列,然后再开始
双端队列
- 主要就是解决权值有0有1的问题,权值为0的放入队列的左边,权值为1的放到队列的右边。与堆优化版
D
i
j
k
s
t
r
a
Dijkstra
B
F
S
BFS
- 主要就是解决权值有0有1的问题,权值为0的放入队列的左边,权值为1的放到队列的右边。与堆优化版
双向广搜
- 主要解决的就是搜索空间爆炸的问题。基本思想就是用两个队列一个从起点
B
F
S
BFS
B
F
S
BFS
- 主要解决的就是搜索空间爆炸的问题。基本思想就是用两个队列一个从起点
A*
- 基本思想是启发式搜索减少搜索空间,优化
B
F
S
BFS
k
k
B
F
S
BFS
- 上面那个问题是用
D
i
j
k
s
t
r
a
Dijkstra
A
s
t
a
r
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]
d
i
s
t
a
n
c
e
distance
A
s
t
a
r
Astar
w
[
i
]
w[i]
i
i
d
i
s
t
[
j
]
dist[j]
j
j
D
i
j
k
s
t
r
a
Dijkstra
k
k
d
i
s
t
a
n
c
e
distance
k
k
D
i
j
k
s
t
r
a
Dijkstra
x
x
D
i
j
k
s
t
r
a
Dijkstra
- 基本思想是启发式搜索减少搜索空间,优化