Brains


Algorithm、Machine Learning、Search、cloud computing
on Algorithm, 图的基础算法

图的常用算法

纸上得来终觉浅,绝知此事要躬行。打算把图的常用算法梳理一遍,加深一下记忆和理解。 简介 前面写了一遍关于图的存储结构和遍历算法的文章,这一篇打算回顾一下图的一些常用算法,包括最小生成树、最短路径算法。这些算法很基础,在生活中经常用到,打算自己动手实现一下,加深理解~~ 最小生成树 生成树的概念:r若图是连通的无向图或强连通的有向图,则从任何一个顶点出发调用一次BFS或者DFS便可访问图中所有的顶点,这种情况下,图中所有顶点加上遍历过程中经历的边构成的子图成为原图的生成树。对于不连通和不是强连通的有向图,这样得到的是生成森林。 最小生成树:对于加权图,权值最小的生成树成为最小生成树。可以用kruskal(克鲁斯卡尔)算法或prim(普里姆)算法求出,这两种算法依据的思想是贪心思想。 prim(普利姆)算法 第一步:选择一个初始顶点V1,设置一个访问数组visit[]和最小距离数组distance[]。最小距离数组保存当前已访问顶点的生成树中到每个顶点最小的距离。 第二步:根据初始顶点V1,初始化visit和distance数组。 第三步:选择distance中权重最小的那个顶点,以此顶点为起始点更新distance数组,直至所有顶点都已访问。 未优化的prim算法时间复杂度为O(N^2),其C语言描述如下,: /* 输入分别为:
Read More