学步园

 Prim算法

例如下面的无向连通图：

#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;			// 顶点A
	int m_nVertexIndexB;			// 顶点B
	int m_nWeight;					// A、B之间的权值
};

class MST_Prim
{
private:
	vector<vector<int>> m_nvGraph;    // 无向连通图
	vector<TreeNode> m_tnMSTree;      // 最小生成树
	int m_nNodeCount;				  // 顶点数
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_MAX
			int i=0;
			while(i<m_nNodeCount)
			{
				if(!bFlag[i])			// 只在与 bFlag[i]=true 的顶点相连的边中取权值最小的，否则跳出本次循环
				{
					i++;
					continue;
				}
				for(int s=0; s<m_nNodeCount; s++)
				{
					if(!bFlag[s] && m_nvGraph[i][s]<nMaxWeight)
					{
						nMaxWeight=m_nvGraph[i][s];
						nMaxIndexA=i;
						nMaxIndexB=s;
					}
				}
				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+1<<"->"
				<<(*ite).m_nVertexIndexB+1<<":"
				<<(*ite).m_nWeight<<endl;
		}
	}
};

int main()
{
	const int cnNodeCount=6;
	vector<vector<int>> graph(cnNodeCount);
	for(int 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;
}

说明：该程序的37行至58行，比较边相邻边的权值是采用直接比较的方法，如果建立一个最小堆，每次将一个结点的相邻边加入最小堆中，则算法的时间复杂度为ElgV。（V 顶点数，E 相邻边的总数）

时间复杂度的简单推导如下：每次循环都将从最小堆中取出权值最小的边，最小堆取最小值的时间复杂度为lgV，共取了V次，总的操作为VlgV；另外，所有边的权值都会在程序中加到最小堆中，最小堆插入元素的时间复杂度为lgV，总的操作为ElgV。二者相加，最后的时间复杂度为O(ElgV)。