韩共同 / 科技服务 / Kruskal 最小生成树算法

分享

   

Kruskal 最小生成树算法

2015-02-03  韩共同
using System;
using System.Collections.Generic;
using System.Linq;
namespace GraphAlgorithmTesting
{
  class Program
  {
    static void Main(string[] args)
    {
      Graph g = new Graph(9);
      g.AddEdge(0, 1, 4);
      g.AddEdge(0, 7, 8);
      g.AddEdge(1, 2, 8);
      g.AddEdge(1, 7, 11);
      g.AddEdge(2, 3, 7);
      g.AddEdge(2, 5, 4);
      g.AddEdge(8, 2, 2);
      g.AddEdge(3, 4, 9);
      g.AddEdge(3, 5, 14);
      g.AddEdge(5, 4, 10);
      g.AddEdge(6, 5, 2);
      g.AddEdge(8, 6, 6);
      g.AddEdge(7, 6, 1);
      g.AddEdge(7, 8, 7);
      Console.WriteLine();
      Console.WriteLine("Graph Vertex Count : {0}", g.VertexCount);
      Console.WriteLine("Graph Edge Count : {0}", g.EdgeCount);
      Console.WriteLine();
      Console.WriteLine("Is there cycle in graph: {0}", g.HasCycle());
      Console.WriteLine();
      Edge[] mst = g.Kruskal();
      Console.WriteLine("MST Edges:");
      foreach (var edge in mst)
      {
        Console.WriteLine("\t{0}", edge);
      }
      Console.ReadKey();
    }
    class Edge
    {
      public Edge(int begin, int end, int weight)
      {
        this.Begin = begin;
        this.End = end;
        this.Weight = weight;
      }
      public int Begin { get; private set; }
      public int End { get; private set; }
      public int Weight { get; private set; }
      public override string ToString()
      {
        return string.Format(
          "Begin[{0}], End[{1}], Weight[{2}]",
          Begin, End, Weight);
      }
    }
    class Subset
    {
      public int Parent { get; set; }
      public int Rank { get; set; }
    }
    class Graph
    {
      private Dictionary<int, List<Edge>> _adjacentEdges
        = new Dictionary<int, List<Edge>>();
      public Graph(int vertexCount)
      {
        this.VertexCount = vertexCount;
      }
      public int VertexCount { get; private set; }
      public IEnumerable<int> Vertices { get { return _adjacentEdges.Keys; } }
      public IEnumerable<Edge> Edges
      {
        get { return _adjacentEdges.Values.SelectMany(e => e); }
      }
      public int EdgeCount { get { return this.Edges.Count(); } }
      public void AddEdge(int begin, int end, int weight)
      {
        if (!_adjacentEdges.ContainsKey(begin))
        {
          var edges = new List<Edge>();
          _adjacentEdges.Add(begin, edges);
        }
        _adjacentEdges[begin].Add(new Edge(begin, end, weight));
      }
      private int Find(Subset[] subsets, int i)
      {
        // find root and make root as parent of i (path compression)
        if (subsets[i].Parent != i)
          subsets[i].Parent = Find(subsets, subsets[i].Parent);
        return subsets[i].Parent;
      }
      private void Union(Subset[] subsets, int x, int y)
      {
        int xroot = Find(subsets, x);
        int yroot = Find(subsets, y);
        // Attach smaller rank tree under root of high rank tree
        // (Union by Rank)
        if (subsets[xroot].Rank < subsets[yroot].Rank)
          subsets[xroot].Parent = yroot;
        else if (subsets[xroot].Rank > subsets[yroot].Rank)
          subsets[yroot].Parent = xroot;
        // If ranks are same, then make one as root and increment
        // its rank by one
        else
        {
          subsets[yroot].Parent = xroot;
          subsets[xroot].Rank++;
        }
      }
      public bool HasCycle()
      {
        Subset[] subsets = new Subset[VertexCount];
        for (int i = 0; i < subsets.Length; i++)
        {
          subsets[i] = new Subset();
          subsets[i].Parent = i;
          subsets[i].Rank = 0;
        }
        // Iterate through all edges of graph, find subset of both
        // vertices of every edge, if both subsets are same,
        // then there is cycle in graph.
        foreach (var edge in this.Edges)
        {
          int x = Find(subsets, edge.Begin);
          int y = Find(subsets, edge.End);
          if (x == y)
          {
            return true;
          }
          Union(subsets, x, y);
        }
        return false;
      }
      public Edge[] Kruskal()
      {
        // This will store the resultant MST
        Edge[] mst = new Edge[VertexCount - 1];
        // Step 1: Sort all the edges in non-decreasing order of their weight
        // If we are not allowed to change the given graph, we can create a copy of
        // array of edges
        var sortedEdges = this.Edges.OrderBy(t => t.Weight);
        var enumerator = sortedEdges.GetEnumerator();
        // Allocate memory for creating V ssubsets
        // Create V subsets with single elements
        Subset[] subsets = new Subset[VertexCount];
        for (int i = 0; i < subsets.Length; i++)
        {
          subsets[i] = new Subset();
          subsets[i].Parent = i;
          subsets[i].Rank = 0;
        }
        // Number of edges to be taken is equal to V-1
        int e = 0;
        while (e < VertexCount - 1)
        {
          // Step 2: Pick the smallest edge. And increment the index
          // for next iteration
          Edge nextEdge;
          if (enumerator.MoveNext())
          {
            nextEdge = enumerator.Current;
            int x = Find(subsets, nextEdge.Begin);
            int y = Find(subsets, nextEdge.End);
            // If including this edge does't cause cycle, include it
            // in result and increment the index of result for next edge
            if (x != y)
            {
              mst[e++] = nextEdge;
              Union(subsets, x, y);
            }
            else
            {
              // Else discard the nextEdge
            }
          }
        }
        return mst;
      }
    }
  }
}

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。

    0条评论

    发表

    请遵守用户 评论公约

    类似文章
    喜欢该文的人也喜欢 更多

    ×
    ×

    ¥.00

    微信或支付宝扫码支付:

    开通即同意《个图VIP服务协议》

    全部>>