Kruskal (MST): Really Special Subtree

  • + 0 comments

    What is wrong with mys solution - ? public static int kruskals(int gNodes, List gFrom, List gTo, List gWeight) { var edges = new List>(); for (int i = 0; i < gFrom.Count; i++) { edges.Add(new Tuple(gFrom[i], gTo[i], gWeight[i])); }

    edges = edges
        .OrderBy(e => e.Item3)
        .ThenBy(e => e.Item1)
        .ToList();
    
    var visitedNodes = new HashSet<int>();
    var mstEdges = new List<Tuple<int, int, int>>();
    for (int i = 0; i < edges.Count; i++)
    {
        if (!visitedNodes.Contains(edges[i].Item2))
        {
            mstEdges.Add(edges[i]);
            visitedNodes.Add(edges[i].Item2);
        }
        if (mstEdges.Count == gNodes - 1)
            break;
    }
    
    var totalWeight = mstEdges.Sum(e => e.Item3);
    return totalWeight;
    

    }