各种图算法
以下这几个算法,是当时学习算法的时候总结的。今天整理过去纸质资料的时候发现的。这里面的内容,很多都已经看不懂了。
现在整理了一下,不为别的,只为了告诉自己:你曾经搞过怎么变态的一些算法分析,还有什么比这个更难的么?
特别说明的是,这里面的算法我没有具体用代码实现过,当时是为了分析时间复杂度和空间复杂度而整理的伪代码。特别是Dijkstra算法,可能都不是完整的,遗憾归遗憾,现在实在是没有心思整理完整的算法描述了……
#Prim算法(普利姆)
##定义
从图的顶点集合V中任意选择一个单顶点,作为序列中的初始子树,每次迭代时,选择不在树中的最近的顶点加入到树中。
算法描述
1 | Prim(G) |
Kruscal算法(克鲁斯卡尔)
定义
算法开始时,按照权重的非递减顺序对图中的边进行排序,然后从一个空子图开始扫描这个有序列表,并试图把列表中的下一条边加到当前的子图中,如果产生回路,则跳过。
算法描述
1 | Kruscal(G) |
Floyd算法(弗洛伊德)
定义
- k=0, dij[0] = wij
- k≥1, dij[k] = min{dij[k-1], dik[k-1]+dkj[k-1]}
把当前距离矩阵D[k-1]中的第i行第j列元素替换为第i行第k列元素和第k行第j列元素的和,当且仅当后者的和小于它的当前值
算法描述
1 | Floyd(w[1..n, 1..n]) |
Dijkstra算法(迪杰斯特拉)
定义
顶点标记 v(f, d):
- d:目前求出从起点到该顶点键间最短路径长度
- f:这条路径上倒数第二个顶点的名字
算法只需找到具有最小的d值得边缘顶点就可以,确定加入u’后:把u’从边缘集合移到树集合,对于余下的每一个边缘u,如果通过w(u’, u)的边与u’相连,当du’ + w(u’, u) < du时,更新u的标记为(u’, du+w(u’, u))。
算法描述
1 | Dijkstra(G, S) |
Like
Issue Page
Loading comments...
Login with GitHub