贪心算法 - 最小生成树问题

一个无向带权图G=(V,E)，其中n个顶点Vertex，以及连接各个顶点之间的边Edge，可能有些顶点之间没有边，每条边上的权值都是非负值。

生成树：

G的一个子图，包含了所有的Vertex，和部分的Edge。

最小生成树：

所有的生成树中，各条Edge上的权值总和最小的一个。

例子：设计通信网络时，各个城市之间铺设线路，最经济的方案。

最小生成树性质：

G=(V,E)，

S是V的真子集，

如果u在S中，v在V-S中，且(u,v)是图的一条边，称之为特殊边，且(u,v)是所有特殊边中最短的，

那么，(u,v)这条边一定在最小生成树中。

Prim算法：

任意指定一个顶点作为起始点，放在S中。

每一步将最短的特殊边放入S中，需要n-1步，即可把所有的其他的点放入S中。算法结束。

对于这个图，Prim算法的过程为：

Kruskal算法：

不停地循环，每一次都寻找两个顶点，这两个顶点不在同一个真子集里，且边上的权值最小。

把找到的这两个顶点联合起来。

初始时，每个顶点各自属于自己的子集合，共n个子集合。

每一步操作，都会将两个子集合融合成一个，进而减少一个子集合。

结束时，所有的顶点都在同一个子集合里，这个子集合就是最小生成树。

例子：

算法过程为：

这两种方法的实现代码如下：
最小生成树头文件CMinStree.h

//最小生成树算法
#include<vector>
#define NN 6
using namespace std;

struct MinStreeEdge
{
    int _pos1; //节点1
    int _pos2; //节点2
    int _value; //两节点间的权重
    bool operator<(const MinStreeEdge& v2)
    {
        return this->_value<v2._value;
    }
    MinStreeEdge& operator=(const MinStreeEdge& v2)
    {
        this->_pos1=v2._pos1;
        this->_pos2=v2._pos2;
        this->_value=v2._value;
        return *this;
    }
};
class CMinStree
{
public:
    CMinStree();
    ~CMinStree();
public:
    void Prim(int map[][NN],int N); //基于prim算法的最小树问题
    void kruskal(int map[][NN]); //基于kruskal算法的最小树问题
private:
    vector<MinStreeEdge> m_treeEdges;
};

最小生成树文件CMinStree.cpp:

#include"stdaxf.h"
#include"CMinStree.h"
#include"CMinHeap.h"

CMinStree::CMinStree()
{
    //测试数据
        int E[6][6] = { { -1, 6, 1, 5, -1, -1 }, { 6, -1, 5, -1, 3, -1 },
                { 1, 5, -1, 5, 6, 4 }, { 5, -1, 5, -1, -1, 2 },
                { -1, 3, 6, -1, -1, 6 }, { -1, -1, 4, 2, 6, -1 } };
    //Prim(E,6);
    //kruskal(E);

}
CMinStree::~CMinStree()
{
}
void CMinStree::kruskal(int map[][NN]) //基于kruskal算法的最小树问题
{
    CMinHeap<MinStreeEdge> MinQueue(NN*(NN-1)/2); //CMinHeap是最小队列
    //初始化最小队列
    for(int i=0;i<NN;i++)
        for(int j=i+1;j<NN;j++)
        {
            if(map[i][j]!=-1) //两节点不可到达，用-1表示
            {
                //将可到达的边加入到最小队列中
                MinStreeEdge tempEdge;
                tempEdge._pos1=i;
                tempEdge._pos2=j;
                tempEdge._value=map[i][j];
                MinQueue.insert(tempEdge);
            }
        }
        int visited[NN]; //初始化子集，用数值带下标识子集
        for(int k=0;k<NN;k++)
            visited[k]=k;
        int count=NN-1; //生成最小树一共多少个边
        while(count--)
        {
            MinStreeEdge vistedEdge=MinQueue.ExtractMin();
            if(visited[vistedEdge._pos1]==visited[vistedEdge._pos2]) continue; //判断是不是在同一子集上

            //将上述两个子集融合到一个子集中
            int num=visited[vistedEdge._pos2];
            for(int i=0;i<NN;i++)
            {
                if(visited[i]==num)
                    visited[i]=visited[vistedEdge._pos1];
            }

            //记录下选择的边
            m_treeEdges.push_back(vistedEdge);
        }


}
void CMinStree::Prim(int map[][NN],int N)
{
    int* dis=(int*)calloc(N,sizeof(int)); //已经形成的最小树到其他各个节点的最短距离
    bool* visited=(bool*)calloc(N,sizeof(bool)); //记录各个节点是否已经被采纳了

    int initpos=0; //设定初始节点
    for(int j=0;j<N;j++)
    {
        dis[j]=map[initpos][j];
    }
    visited[initpos]=true;

    for(int i=0;i<N-1;i++) //每一次循环找到一条边，一共进行N-1次
    {
        int min_distan=100000; //初始化最小边的权重

        MinStreeEdge tempEdge;
        tempEdge._pos1=initpos;

        //下面for循环，计算出此时最小边和节点
        for(int j=1;j<N;j++)
        {
            if(!visited[j]&&(min_distan>dis[j])&&(dis[j]!=-1))
            {
                min_distan=dis[j];
                initpos=j; //更新节点
            }
        }

        //更新相应参数
        tempEdge._pos2=initpos;
        tempEdge._value=min_distan;
        m_treeEdges.push_back(tempEdge); //加载到容器

        visited[initpos]=true;
        for(j=0;j<N;j++)
        {
            if(!visited[j]&&((map[initpos][j]<dis[j])||(dis[j]==-1))&&(map[initpos][j]!=-1))
                dis[j]=map[initpos][j];
        }
    }
    free(dis);
    free(visited);
}

此实现借助了最小堆，来实现每次选取权值最小的边。

最小堆的代码实现：

//基于堆的最小队列
//@anthor hustfxj
//data 2013/11/6

#ifndef CLASS_CMINHEAP
#define CLASS_CMINHEAP

//#include"stdaxf.h"
template <class T>
class CMinHeap
{
public:
    explicit CMinHeap(int n);
    ~CMinHeap();

    bool insert(const T& Addedata);
    T ExtractMin();
private:
    int parentIndex(int child) const;
    int getlchild(int parent) const;
    int getrchild(int parent) const;
    void swap(int k1,int k2);

private:
    T* m_HeapData;
    int memoriedSize;
    int size;
};
#endif


template <class T>
CMinHeap<T>::CMinHeap(int n)
{
    m_HeapData=new T[n];
    memoriedSize=n;
    size=0;
}
template <class T>
CMinHeap<T>::~CMinHeap()
{
    delete [] m_HeapData;
}

template <class T>
bool CMinHeap<T>::insert(const T& Addedata)
{
    if(size>=memoriedSize)
        return false;
    int child=size,p;
    m_HeapData[size]=Addedata;
    size++;

    p=parentIndex(child);
    while(m_HeapData[child]<m_HeapData[p]&&p>=0)
    {
        swap(p,child);
     child=p;
        p=parentIndex(child);
    }
    return true;
}
template <class T>
T CMinHeap<T>::ExtractMin()
{
    if(size==0)
        exit(1); //队列中以及没有元素了
    T val=m_HeapData[0];
    m_HeapData[0]=m_HeapData[size-1];
    size--;
    int begin=0;

    while(begin<size)
    {
        int lchild=getlchild(begin);
        int rchild=getrchild(begin);
        int pos=begin;
        if(lchild<size&&m_HeapData[lchild]<m_HeapData[pos])
            pos=lchild;
        if(rchild<size&&m_HeapData[rchild]<m_HeapData[pos])
            pos=rchild;
        if(pos==begin)
            break;
        swap(pos,begin);
        begin=pos;
    }
    return val;
}
template <class T>
void CMinHeap<T>::swap(int k1,int k2)
{
    if(k1==k2)
        return;
    T temp=m_HeapData[k1];
    m_HeapData[k1]=m_HeapData[k2];
    m_HeapData[k2]=temp;
}
template <class T>
int CMinHeap<T>::parentIndex(int child) const
{
    return child%2==0?child/2-1:child/2;
}
template <class T>
int CMinHeap<T>::getlchild(int parent) const
{
    return (parent+1)*2-1;
}
template <class T>
int CMinHeap<T>::getrchild(int parent) const
{
   return (parent+1)*2;
}