您当前的位置: 首页 > 编程

最小生成树算法(种Prim算法的笨办法)

发布时间：2011-07-01 07:27:31 文章来源：www.iduyao.cn 采编人员：星星草

最小生成树算法(类Prim算法的笨办法)

这个算法是我自己想的最笨最原始的算法，原理跟Prim类似，但不同的是这里不用处理最小优先级队列，当然算法的时间复杂度要高些，下面看代码：

1、类和树的定义可参考前面的博文。

2、算法类：

public class PrimAlg
    {
        public Tree MST_SimpleAlg(Graphic g,Node root)
        {
            Tree theMST = new Tree();
            //最小生成树节点
            Dictionary<string, Node> theMstNodes = new Dictionary<string, Node>();
            //剩下未纳入最小生成树的节点
            Dictionary<string, Node> theRemainNodes = new Dictionary<string, Node>();
            //图的边
            List<Edge> theEdges = new List<Edge>();
            //开始的时候最小生成树节点包含root一个节点.
            theMstNodes.Add(root.Symbol, root);
            //将图的边复制到临时边集中，目的是没选一个边，就可以删除该边，以减低时间复杂度。
            theEdges.AddRange(g.Edges);
            //开始的时候剩余点集是图中除根节点之外的所有点.
            foreach (var theNode in g.Nodes)
            {
                if (theNode.Symbol != root.Symbol)
                {
                    theRemainNodes.Add(theNode.Symbol, theNode);
                }
            }
            //将根节点放入结果最小生成树中.
            theMST.Nodes.Add(root);
            //只要有剩余点就循环处理
            while (theRemainNodes.Count() > 0)
            {
                //记录最小的边，该边一个节点在已生成的最小生成树节点中，
                //一个节点在未纳入最小生成树的节点中
                Edge theMinEdge = null;
                //最小边在最小生成树中的节点
                Node theMNode = null;
                //最小边在剩余节点中端点.
                Node theRNode = null;
                foreach (var theEdge in theEdges)
                {
                    if (theMstNodes.ContainsKey(theEdge.Node1.Symbol) &&
                        theRemainNodes.ContainsKey(theEdge.Node2.Symbol))
                    {
                        if (theMinEdge == null)
                        {
                            theMinEdge = theEdge;
                            theMNode = theEdge.Node1;
                            theRNode = theEdge.Node2;
                            continue;
                        }
                        if (theMinEdge.Weight > theEdge.Weight)
                        {
                            theMinEdge = theEdge;
                            theMNode = theEdge.Node1;
                            theRNode = theEdge.Node2;
                            continue;
                        }
                    }
                    if (theMstNodes.ContainsKey(theEdge.Node2.Symbol) &&
                         theRemainNodes.ContainsKey(theEdge.Node1.Symbol))
                    {
                        if (theMinEdge == null)
                        {
                            theMinEdge = theEdge;
                            theMNode = theEdge.Node2;
                            theRNode = theEdge.Node1;
                            continue;
                        }
                        if (theMinEdge.Weight > theEdge.Weight)
                        {
                            theMinEdge = theEdge;
                            theMNode = theEdge.Node2;
                            theRNode = theEdge.Node1;
                            continue;
                        }
                    }     
                }
                if (theMinEdge != null)
                {
                    theMST.Nodes.Add(theRNode);
                    theMST.Edges.Add(theMinEdge);
                    theMstNodes.Add(theRNode.Symbol,theRNode);
                    theRemainNodes.Remove(theRNode.Symbol);
                    theEdges.Remove(theMinEdge);
                }
            }
            return theMST;
        }
    }

这个算法的复杂度虽然比较高o(E2),但实现非常简单，不需要像Prim算法那样用到二叉堆之类的，容易理解和实现。

上一篇：O(N lgK) 时间内合龙K个有序链表
下一篇：Hibernate入门BLOG [4、Hibernate的CRUD简单总结]

友情提示：
信息收集于互联网，如果您发现错误或造成侵权，请及时通知本站更正或删除，具体联系方式见页面底部联系我们，谢谢。

其他相似内容：

套接字网络编程札记

套接字网络编程笔记套接字网络编程笔记 1.调用int send( __in SOCKET s, __in const char* buf, __in int len, __in int f...
并发编程中急需谨记的规则(翻)

并发编程中需要谨记的规则(翻) 并发编程中需要谨记的规则最小化临界区 Amdahl定律和Gustafson定律都将并行算法中的...
了解并发编程中的几种并发方式

理解并发编程中的几种并发方式理解并发编程中的几种并发方式时刻谨记并发设计当你设计代码利用多核优势的时候，重...
Dynamics CRM 2011 编程系列(28):应用SQL Server Profiler找表

Dynamics CRM 2011 编程系列(28):使用SQL Server Profiler找表很多时候我们并不能直接从Dynamics CRM系统中轻松的获取我们...
Dynamics CRM 2011 编程系列(27):应用触发器

Dynamics CRM 2011 编程系列(27):使用触发器在Dynamics CRM系统中使用触发器虽然不被官方建议，但却是解决一些疑难需求的有力...
项目总结

项目小结前几天接到一个小的任务。做几个小小的网页。很是晕呀，因为自己以前从未接触过这类的东西，偶尔也是看看看着别人做。自己...
Winform and WPF 其次遍双击快捷方式或应用程序打开原来的应用程序而不新建一个实例[进程通信 1]

Winform and WPF 第二遍双击快捷方式或应用程序打开原来的应用程序而不新建一个实例[进程通信 1] 今天工作忙完之余，总结一些Winfo...
Java 同步形式 (1) —— synchronized

Java 同步方式 (1) —— synchronized 前两篇博客 ArrayList 用法比较和 String 用法比较，介绍过程中都提及到了同步和线程安全的...
Objective-c 种接口（@interface）（类定义）

Objective-c 类接口（@interface）（类定义）在Objective-c中如何定义一个类呢？我们可以使用下面的格式进行表示： @interfac...
SPEEX重采样分析（1）

SPEEX重采样分析（一）简介算法速度快 SIMD（SSE）指令支持低内存高质量该算法是基于最原始的重采样算法： Smith, Julius O. Digi...

最小生成树算法(种Prim算法的笨办法)

其他相似内容：

热门推荐：