最小生成树（Kruskal,Prim算法）

1.Kruskal
  每次找出权值最小的边，用并查集判断构成这两个边的顶点是不是有一个根（即构成回路），若不是则加入这条边，直到加入N-1条。

bool Kruskal(GraphLink& minSpanTree)
    {
        // 1.把顶点、顶点数量放入最小生成树
        minSpanTree._linkTable = new LinkVertex<V, W>[_vertexSize];
        minSpanTree._vertexSize = _vertexSize;
        for (int i = 0; i < _vertexSize; ++i)
        {
            minSpanTree._linkTable[i]._vertex = _linkTable[i]._vertex;
        }
        // 2.将所有的边放到一个最小堆
        Heap<LinkEdge<V,W>*, CompareLinkEdge<V,W>> minHeap;
        for (int i = 0; i < _vertexSize; ++i)
        {
            LinkEdge<V, W>* begin = _linkTable[i]._head;
            while (begin)
            {
                // 无向图的边需要进行过滤
                if (begin->_srcIndex < begin->_dstIndex)
                {
                    minHeap.Push(begin);
                }

                begin = begin->_next;
            }
        }

        // 3.使用并查集和最小堆构建最小生成树
        UnionFindSet UFSet(_vertexSize);
        int count = _vertexSize;
        while (--count)
        {
            if (minHeap.Empty())
            {
                return false;
            }

            LinkEdge<V,W>* edge = minHeap.Top();
            minHeap.Pop();
            int src = UFSet.Find(edge->_srcIndex);
            int dst = UFSet.Find(edge->_dstIndex);

            if(src != dst)//若两个不是一个根，即没有构成回路
            {
                UFSet.Union(src, dst);//合成一个根
                minSpanTree._AddEdge(edge->_srcIndex, edge->_dstIndex, edge->_weight);
            }
        }

        return true;
    }

2.Prim

bool Prim(GraphLink& minSpanTree)
    {
        // 1.初始化最小生成树
        minSpanTree._linkTable = new LinkVertex<V, W>[_vertexSize];
        minSpanTree._vertexSize = _vertexSize;
        for (int i = 0; i < _vertexSize; ++i)
        {
            minSpanTree._linkTable[i]._vertex = _linkTable[i]._vertex;
        }

        bool* visitedSet = new bool[_vertexSize];
        memset(visitedSet, false, sizeof(bool)*_vertexSize);

        int src = 0;
        visitedSet[src] = true;
        Heap<LinkEdge<V,W>*, CompareLinkEdge<V,W>> minHeap;

        int count = 1;
        do
        {
            // 2.取出一个顶点所有未访问过的临接边放到一个最小堆里面
            LinkEdge<V, W>* edge = _GetFirstEdge(src);
            while(edge)
            {
                if (visitedSet[edge->_dstIndex] == false)
                {
                    minHeap.Push(edge);
                }

                edge = _GetNextEdge(src, edge->_dstIndex);
            }

            // 2.选出堆中最小的边加入生成树
            while(!minHeap.Empty() && count < _vertexSize)
            {
                edge = minHeap.Top();
                minHeap.Pop();
                if (visitedSet[edge->_dstIndex] == false)
                {
                    minSpanTree._AddEdge(edge->_srcIndex, edge->_dstIndex,edge->_weight);
                    visitedSet[edge->_dstIndex] = true;
                    src = edge->_dstIndex;
                    ++count;

                    break;
                }
            }
        }while (count < _vertexSize);

        return true;
    }

    W _GetWeight(int src, int dst, const W& maxValue)
    {
        if (src == dst)
            return maxValue;

        LinkEdge<V,W>* edge = _linkTable[src]._head;
        while (edge)
        {
            if (edge->_dstIndex == dst)
            {
                return edge->_weight;
            }

            edge = edge->_next;
        }

        return maxValue;
    }