关于图的算法及其复杂度和适用场景分析
最小生成树
$prim$算法(普里姆算法)
- 时间复杂度$O(N^2)$
- 适用场景:
稠密图
- 又叫
加点法
模版例题: HDU-1102
1 |
|
$Kruskal$算法(克鲁斯卡尔算法)
- 时间复杂度$O(elog_2e)$
- 适用场景:
稀疏图
- 又叫
加边法
,所以对边操作特别方便(如让求最小生成树最大或最小边的裸题)
例题:POJ - 1251
1 |
|
最短路径
$Dijkstra$算法(迪杰斯特拉算法)
- 时间复杂度:不用堆优化$O(N^2)$,堆优化以后$O(Nlog_2N)$
$Floyd$算法(弗洛伊德算法)
- 时间复杂度:$O(N^3)$
需要注意的小知识点
图的
逆邻接表
存储只适用于有向
图邻接表
不便于求入度
,逆邻接表
不便于求出度
,而十字链表
便于求入度和出度
。图的
BFS
生成树的树高$\le$DFS
生成树的树高(如只有一个点的图和形成一个环的图)$MST \bigl( Minimum Spanning Tree \bigr)$性质:假设$N=(V,E)$是一个联通网,$U$是顶点集$V$的一个非空子集(可以从图的定义理解:$G=(V,E)$中$V$就是顶点的有穷非空子集,在图中不可以为空,而树是可以为空的。),若$(u,v)$是一条具有最小权值(代价)的边,其中$u\subseteq U, v\subseteq V-U$,则必存在一颗包含$(u,v)$的最小生成树。
一些名词解释
- 稀疏图:有很少边或弧(如 $e<nlog_2n$ ( $n$ :点数, $e$ :边数))的图称为稀疏图