学校：上海交通大学软件工程 学历：硕士 行业：从事流媒体移动开发 QQ: 412595942 邮箱：yiikai1987910@gmail.com
发布时间：2015-02-25 16:28:17
在之前，我曾经写过一边关于最小生出树的算法--prime，今天是另一个算法kruskal，这两个算法的复杂度是一样的。主要和prime在代码实现上的区别在于，kruskal算法是把焦点集中在了边上， 而prime算法是在节点上，一个是对优先队列中的点进行操作，一个是对于优先队列中的边进行操作。详细的算法细节大家可以go.........【阅读全文】
发布时间：2015-02-25 13:21:19
并查集的原理可以google 很多，比较简单。这里主要记录下自己的实现。 一个典型的应用是在kruskal算法中 直接上代码： 点击(此处)折叠或打开#define MAXN 7int ID[MAXN] = { 0 };int r.........【阅读全文】
发布时间：2015-02-19 08:57:55
最小生成树是对于有权连通图求权重合最小的联通子图问题的算法，注意连通图是不能带环的。像这类问题在算法题中很常见，像求几个城市间网路搭建成本消耗问题就可以运用prim最小生成树来解决。 最小生成树和Dijkstra算法的思想比较类似， 只是Dijkstra主要关注每个节点的优先级， 而prim关注于相.........【阅读全文】
发布时间：2015-02-18 23:35:31
Dijkstra算法是求单源最短路径好方法，但是只能处理没有负边的图的问题，有一条边为负的就会导致最终的结果不正确 时间复杂度可以达到O(|E|log|v|)， 所以一般求单源最短路径问题都可以用这个算法 伪代码： priority_queue que; que.push(startV);&nbs.........【阅读全文】
发布时间：2015-02-18 10:20:55
bellmanford算法是通用的单源最短路径求解算法，相比Dijkstra，复杂度稍差 ， 但是可以处理含有负边的图路径问题，所以比较适合通用的图。 这里给出对于该算法的伪代码： all V: d(v) = INF; for(i = 0; i< |V| ; i++) for(j = 0; j<|E|;j++)&.........【阅读全文】
