最小生成树__Kurskal算法

83 阅读 0 评论 55 点赞

我是靠谱客的博主懦弱蜜蜂，最近开发中收集的这篇文章主要介绍最小生成树__Kurskal算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

using System;
using System.Collections.Generic;
using System.Linq;

namespace 最小生成树__Kurskal算法
{
    class Program
    {
        public static readonly int M = 999999;//表示不可到达距离  
        static int[,] map = new int[,] {
                { 0, 23, M, M,M,28,36 },
                { 23, 0, 20, M,M,M,1 },
                { M,20,0,15,M,M,4 },
                { M,M,15,0,3,M,9 },
                { M,M,M,3,0,17,16},
                { 28,M,M,M,17,0,25 },
                { 36,1,4,9,16,25,0 }
            };//路径图  
        public class Edge
        {
            public int Start { get; set; }//边的起点
            public int End { get; set; }//边的终点
            public int Weight { get; set; }//长度

            public Edge(int s, int e, int w)
            {
                Start = s;
                End = e;
                Weight = w;
            }
        }
        public static  int N = (int)Math.Sqrt(map.Length);//获取地点数;   
        public static int[] Nodes = new int[N];
        public static List<Edge> Edges = new List<Edge>();
        public static List<Edge> edges = new List<Edge>();

        static void Main(string[] args)
        {
            for (int i = 0; i < N; i++)
            {
                Nodes[i] = i;
            }

            //转化每条边为Edge类型 并添加近列表
            for (int i = 0; i < N - 1; i++)
            {
                for (int j = i + 1; j < N; j++)
                {
                    if (map[i, j] != M)
                    {
                        Edge edge = new Edge(i, j, map[i, j]);
                        Edges.Add(edge);
                    }
                }
            }
            //对边按权重大小排序 升序
            var E =
                from v in Edges
                orderby v.Weight
                select v;

            //对每条边进行判定
            foreach (var edge in E)
            {
                if (Merge(edge.Start, edge.End))
                    edges.Add(edge);//将符合条件的边添加进边的集合 用于输出
            }


            //输出结果
            int sum = 0;
            foreach (var e in edges)
            {
                sum += e.Weight;
                Console.WriteLine("边的起点：" + (e.Start + 1) + "；边的终点：" + (e.End + 1) + "；边的权重：" + e.Weight);
            }

            Console.WriteLine("边的总权重：" + sum);

            Console.ReadKey();
        }
        /// <summary>
        /// 对边的起点进行判定 
        /// 若相等则返回False 表示这条边不符合最小生成树要求
        /// 若不想等 则将所有执行并集操作
        /// 即将所有与此边终点相等的边的值变成此边的起点值
        /// </summary>
        /// <param name="a">边的起点</param>
        /// <param name="b">边的终点</param>
        /// <returns></returns>
        static bool Merge(int a,int b)
        {
            int p = Nodes[a];
            int q = Nodes[b];
            if (p == q) return false;
            for(int i = 0; i < N; i++)
            {
                if (Nodes[i] == q)
                    Nodes[i] = p;
            }
            return true;
        }
    }

}