2014
01-03

# 贪心算法——最小生成树

## 二、Prim算法

1 -> 3 : 1

3 -> 6 : 4

6 -> 4: 2

3 -> 2 : 5

2 -> 5 : 3

/* 主题：贪心算法——最小生成树（Prim）
* 作者：chinazhangjie
* 邮箱：[email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */
* 开发语言： C++
* 开发环境： Virsual Studio 2005
* 时间: 2010.11.30
*/

#include <iostream>
#include <vector>
#include <limits>
using namespace std ;

struct TreeNode
{
public:
TreeNode (int nVertexIndexA = 0, int nVertexIndexB = 0, int nWeight = 0)
: m_nVertexIndexA (nVertexIndexA),
m_nVertexIndexB (nVertexIndexB),
m_nWeight (nWeight)
{ }
public:
int m_nVertexIndexA ;
int m_nVertexIndexB ;
int m_nWeight ;
} ;

class MST_Prim
{
public:
MST_Prim (const vector<vector<int> >& vnGraph)
{
m_nvGraph = vnGraph ;
m_nNodeCount = (int)m_nvGraph.size () ;
}
void DoPrim ()
{
// 是否被访问标志
vector<bool> bFlag (m_nNodeCount, false) ;
bFlag[0] = true ;

int nMaxIndexA ;
int nMaxIndexB ;
int j = 0 ;
while (j < m_nNodeCount - 1) {
int nMaxWeight = numeric_limits<int>::max () ;
// 找到当前最短路径
int i = 0 ;
while (i < m_nNodeCount) {
if (!bFlag[i]) {
++ i ;
continue ;
}
for (int j = 0; j < m_nNodeCount; ++ j) {
if (!bFlag[j] && nMaxWeight > m_nvGraph[i][j]) {
nMaxWeight = m_nvGraph[i][j] ;
nMaxIndexA = i ;
nMaxIndexB = j ;
}
}
++ i ;
}
bFlag[nMaxIndexB] = true ;
m_tnMSTree.push_back (TreeNode(nMaxIndexA, nMaxIndexB, nMaxWeight)) ;
++ j ;
}
// 输出结果
for (vector<TreeNode>::const_iterator ite = m_tnMSTree.begin() ;
ite != m_tnMSTree.end() ;
++ ite ) {
cout << (*ite).m_nVertexIndexA << "->"
<< (*ite).m_nVertexIndexB << " : "
<< (*ite).m_nWeight << endl ;
}
}
private:
vector<vector<int> > m_nvGraph ;    // 无向连通图
vector<TreeNode>    m_tnMSTree ;    // 最小生成树
int    m_nNodeCount ;
} ;

int main()
{
const int cnNodeCount = 6 ;
vector<vector<int> > graph (cnNodeCount) ;
for (size_t i = 0; i < graph.size() ; ++ i) {
graph[i].resize (cnNodeCount, numeric_limits<int>::max()) ;
}
graph[0][1]= 6 ;
graph[0][2] = 1 ;
graph[0][3] = 5 ;
graph[1][2] = 5 ;
graph[1][4] = 3 ;
graph[2][3] = 5 ;
graph[2][4] = 6 ;
graph[2][5] = 4 ;
graph[3][5] = 2 ;
graph[4][5] = 6 ;

graph[1][0]= 6 ;
graph[2][0] = 1 ;
graph[3][0] = 5 ;
graph[2][1] = 5 ;
graph[4][1] = 3 ;
graph[3][2] = 5 ;
graph[4][2] = 6 ;
graph[5][2] = 4 ;
graph[5][3] = 2 ;
graph[5][4] = 6 ;

MST_Prim mstp (graph) ;
mstp.DoPrim () ;
return 0 ;
}

## 三、Kruskal算法

1）首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小大排序。

（2）从第一条边开始，依边权递增的顺序检查每一条边。并按照下述方法连接两个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前两个不同的连通分支T1和T2的端点是，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看k+1条边。这个过程一个进行到只剩下一个连通分支时为止。

Kruskal算法的选边过程

1 -> 3 : 1

4 -> 6 : 2

2 -> 5 : 3

3 -> 4 : 4

2 -> 3 : 5

/* 主题：贪心算法之最小生成树(Kruskal算法)
* 作者：chinazhangjie
* 邮箱：[email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */
* 开发语言：C++
* 开发环境：Visual Studio 2005
* 时间：2010.12.01
*/

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std ;

struct TreeNode
{
public:
TreeNode (int nVertexIndexA = 0, int nVertexIndexB = 0, int nWeight = 0)
: m_nVertexIndexA (nVertexIndexA),
m_nVertexIndexB (nVertexIndexB),
m_nWeight (nWeight)
{ }
friend
bool operator < (const TreeNode& lth, const TreeNode& rth)
{
return lth.m_nWeight > rth.m_nWeight ;
}

public:
int m_nVertexIndexA ;
int m_nVertexIndexB ;
int m_nWeight ;
} ;

//  并查集
class UnionSet
{
public:
UnionSet (int nSetEleCount)
: m_nSetEleCount (nSetEleCount)
{
__init() ;
}
// 合并i，j。如果i，j同在集合中，返回false。否则返回true
bool Union (int i, int j)
{
int ifather = __find (i) ;
int jfather = __find (j) ;
if (ifather == jfather )
{
return false ;
// copy (m_nvFather.begin(), m_nvFather.end(), ostream_iterator<int> (cout, " "));
// cout << endl ;
}
else
{
m_nvFather[jfather] = ifather ;
// copy (m_nvFather.begin(), m_nvFather.end(), ostream_iterator<int> (cout, " "));
// cout << endl ;
return true ;
}

}

private:
// 初始化并查集
int __init()
{
m_nvFather.resize (m_nSetEleCount) ;
for (vector<int>::size_type i = 0 ;
i < m_nSetEleCount;
++ i )
{
m_nvFather[i] = static_cast<int>(i) ;
// cout << m_nvFather[i] << " " ;
}
// cout << endl ;
return 0 ;
}
// 查找index元素的父亲节点 并且压缩路径长度
int __find (int nIndex)
{
if (nIndex == m_nvFather[nIndex])
{
return nIndex;
}
return  m_nvFather[nIndex] = __find (m_nvFather[nIndex]);
}

private:
vector<int>                m_nvFather ;    // 父亲数组
vector<int>::size_type m_nSetEleCount ;    // 集合中结点个数
} ;

class MST_Kruskal
{
typedef priority_queue<TreeNode> MinHeap ;
public:
MST_Kruskal (const vector<vector<int> >& graph)
{
m_nNodeCount = static_cast<int>(graph.size ()) ;
__getMinHeap (graph) ;
}
void DoKruskal ()
{
UnionSet us (m_nNodeCount) ;
int k = 0 ;
while (m_minheap.size() != 0 && k < m_nNodeCount - 1)
{
TreeNode tn = m_minheap.top () ;
m_minheap.pop () ;
// 判断合理性
if (us.Union (tn.m_nVertexIndexA, tn.m_nVertexIndexB))
{
m_tnMSTree.push_back (tn) ;
++ k ;
}
}
// 输出结果
for (size_t i = 0; i < m_tnMSTree.size() ; ++ i)
{
cout << m_tnMSTree[i].m_nVertexIndexA << "->"
<< m_tnMSTree[i].m_nVertexIndexB << " : "
<< m_tnMSTree[i].m_nWeight
<< endl ;
}
}

private:
void __getMinHeap (const vector<vector<int> >& graph)
{
for (int i = 0; i < m_nNodeCount; ++ i)
{
for (int j = 0; j < m_nNodeCount; ++ j)
{
if (graph[i][j] != numeric_limits<int>::max())
{
m_minheap.push (TreeNode(i, j, graph[i][j])) ;
}
}
}
}
private:
vector<TreeNode>    m_tnMSTree ;
int                    m_nNodeCount ;
MinHeap                m_minheap ;
} ;

int main ()
{
const int cnNodeCount = 6 ;
vector<vector<int> > graph (cnNodeCount) ;
for (size_t i = 0; i < graph.size() ; ++ i)
{
graph[i].resize (cnNodeCount, numeric_limits<int>::max()) ;
}
graph[0][1]= 6 ;
graph[0][2] = 1 ;
graph[0][3] = 3 ;
graph[1][2] = 5 ;
graph[1][4] = 3 ;
graph[2][3] = 5 ;
graph[2][4] = 6 ;
graph[2][5] = 4 ;
graph[3][5] = 2 ;
graph[4][5] = 6 ;

graph[1][0]= 6 ;
graph[2][0] = 1 ;
graph[3][0] = 3 ;
graph[2][1] = 5 ;
graph[4][1] = 3 ;
graph[3][2] = 5 ;
graph[4][2] = 6 ;
graph[5][2] = 4 ;
graph[5][3] = 2 ;
graph[5][4] = 6 ;

MST_Kruskal mst (graph);
mst.DoKruskal () ;
}

1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

2. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？

3. 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法