实验13 prim算法和kruskal算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了实验13 prim算法和kruskal算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🔑一个神奇的哔哩哔哩讲解链接
🔑笔记补充——第十七章：贪婪算法（思想同，但应用上和伪代码略有差别）

A：prim算法

描述

使用prim算法实现最小生成树

格式

输入

第一行两个整数n,e。n ( $\leq n \leq 200000$ ) 代表图中点的个数，e ( $\leq m \leq 500000$ ) 代表边的个数。
接下来e行，每行代表一条边：

i j w 表示顶点i和顶点j之间有一条权重为w的边

输出

最小生成树所有边的权重和

整体思路描述

Prim算法：Prim算法是从顶点出发

将一个点先加入点集，遍历其所连着的边找到权值最小的边，选中该边
将该边的另一个顶点加入点集
再遍历这个新加入点的所有连着的边，和之前的一块比较，选出权值最小的且其另一个顶点还未加入点集的边
再将其另一个顶点加入点集,以此类推，直到选了顶点数-1条边。

比较复杂，以OJ示例为例做如下过程演算

实现代码

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

//-----------------10.1小根堆应用迁移start--------------------
//将一个一维数组的长度从oldLength变成newLength。（后续push操作会用到） 
template<class T>
void changeLengthID(T*& array, int oldLength, int newLength)
{
    T* newarray = new T[newLength];//函数首先分配一个新的、长度为newLength的数组   
    int number = (oldLength < newLength) ? oldLength : newLength; //取min {oldLength, newLength} 
    for (int i = 0; i < number; i++)
		newarray[i] = array[i];//然后把原数组的前min {oldLength, newLength} 个元素复制到新数组中
    delete[] array;//释放原数组所占用的空间                      
    array = newarray;//将新数组赋值到旧数组完成更改 
}

//小根堆定义及实现 
template<class T>
class minHeap
{
	public:
    	minHeap(int initialCapacity = 10)
		{//构造 
    		arrayLength = initialCapacity + 1;
    		heap = new T[arrayLength];
    		heapSize = 0;
		}
    	~minHeap() { delete[] heap; }//析构 
    	const T& top()
    	{//返回优先级最大的元素的引用 
    		return heap[1];
    	}
    	void pop();//删除
		void push(const T&theElement);//插入
    	void initialize(T*theHeap, int theSize);//初始化 
    	void output(ostream& out) const;//输出 
	private:
		T* heap;//一个类型为T的一维数组 
		int arrayLength;//数组heap的容量 
    	int heapSize;//堆的元素个数               
};

//小根堆的插入 
template<class T>
void minHeap<T>::push(const T& theElement)
{//把元素theElement加入堆
    
	//必要时增加数组长度 
	if (heapSize == arrayLength - 1)
    {//数组长度加倍 
        changeLengthID(heap, arrayLength, 2 * arrayLength);
        arrayLength *= 2;
    }
    
	//为元素theElement寻找插入位置 
	//小根堆要求老叶子比新叶子小 
    int currentNode = ++heapSize;//currentNode从新叶子向上移动，就从最底下开始 
    while (currentNode != 1 && heap[currentNode / 2] > theElement)
    {//这个时候老叶子比新叶子大，不能把元素放在这 
        heap[currentNode] = heap[currentNode / 2]; //把大的那个元素赋给currentNode，相当于把大的元素往下移 
        currentNode /= 2;//同时把currentNode（一个打算插入theElement的位置）移向双亲，就往上移                    
    }
    //循环结束，即找到合适的位置插入 
    heap[currentNode] = theElement;
}

//删除操作是针对堆顶元素而言的，即把末尾元素移动到堆顶，再自顶向下(重复构建堆的操作)，递归调整。
template<class T>
void minHeap<T>::pop()
{
	//删除堆顶元素
    heap[1].~T(); 
	//删除最后一个元素，然后重新建堆（这一步相当于把末尾元素拿出来） 
    T lastElement = heap[heapSize--];
	//开始给拿出来的末尾元素找合适的放入位置，从顶开始，自顶向下调整 
    int currentNode = 1,
        child = 2;//currentNode的孩子    
    while (child <= heapSize)
    {
    	//heap[child]应该是currentNode的更大的孩子（就是说它的值太大了，应该往后头放） 
        if (child < heapSize && heap[child] > heap[child + 1])
            child++;
		
		//可以把lastElement放在heap[currentNode]吗？ 
		//可以 
        if (lastElement <= heap[child])
            break; 
		//不可以（以下操作和上述push相关操作同理） 
        heap[currentNode] = heap[child];//把孩子child向上移动 
        currentNode = child;//向下移动一层寻找位置          
        child *= 2;
    }
    heap[currentNode] = lastElement;
}

//初始化一个非空小根堆 
template<class T>
void minHeap<T>::initialize(T* theHeap, int theSize)
{//在数组theHeap[1:theSize]中建小根堆（参考p304-305) 
    delete[] heap;
    heap = theHeap;
    heapSize = theSize;
	//堆化 
    for (int root = heapSize / 2; root >= 1; root--)
    {
        T rootElement = heap[root];
        int child = 2 * root; 
        while (child <= heapSize)
        {	
        	//heap[child]应该是兄弟中的较小者 
            if (child < heapSize && heap[child] > heap[child + 1])
                child++; 
			//可以把rootElement放在heap[child / 2]吗? 
			//可以（原理同上 
            if (rootElement <= heap[child])
                break;  
            //不可以 
            heap[child / 2] = heap[child]; 
            child *= 2;                   
        }
        heap[child / 2] = rootElement;
    }
}
//-------------------10.1小根堆应用迁移finish-------------------

//--------------------边结构体定义start-----------------------
struct edge//存放边
{
    long long to;//to是这个边指向的顶点 
    long long w;//w是这个边的权值 
};

struct Edge
{
 	long long w;
 	long long v;
    Edge(){}
    Edge(int w1,int v1)
	{
        w=w1;
		v=v1;
    }
    //符号重载
 	bool operator < (const Edge& b) const
 	{
  		return w < b.w;
 	}
    bool operator <= (const Edge& b) const
 	{
  		return w <= b.w;
 	}
    bool operator > (const Edge& b) const
 	{
  		return w > b.w;
 	}
};
vector<edge> edges[200005];//边的动态数组，用来存放边
bool vertex[200005];//标记是否选入 
//-------------------边结构体定义finish-----------------------

//----------------------Prim算法实现start--------------------
template<class T>
class Prim
{//定义Prim类
	public:
   		void initialize();//初始化
    	void prim();//prim算法
	private:
    	long long result=0;//权值和结果 
    	int n,e;//顶点和边数
};

template<class T>
void Prim<T>:: initialize()
{
    cin >> n >> e;//输入顶点和边数 
    for(int i = 0; i <= n; i++)
    	//顶点标记，全部初始化为true 
  		vertex[i] = true;
    for(int i = 1; i <= e; i++)
    {
    	//v1,v2是两个顶点，w是权值 
        long long v1, v2, w;
        cin >> v1 >> v2 >> w;
        //定义两个边(因为两个顶点两个方向有两条边) 
        edge e1,e2;
        //权值赋值 
        e1.w=w;
		e2.w=w;
		//顶点构造 
        e1.to=v2;
		e2.to=v1;
		//边集更新（起始点连着哪些边 
        edges[v1].push_back(e1);//在edges[v1]数组的后方插入边e1
        edges[v2].push_back(e2);//在edges[v2]数组的后方插入边e2
    }
}

template<class T>
void Prim<T>::prim()
{
	//默认先选入第一个顶点 
    long long s = edges[1].size();//第一个数组的长度
    minHeap<Edge> q;
    vertex[1] = false;//及时标记，表示已经选入 
    
    //列出选入节点的所有边，存入最小堆q 
	for(int i = 0; i < s; ++i)
    {
        long long v,w;
		v = edges[1][i].to;
		w = edges[1][i].w;
        Edge t(w,v);//临时结构体，用来存放
        q.push(t);
    }
    
    //找出上边挑出的边中权值最小的 
    for(int i = 1; i < n; i++)
    {
        long long min, to;
    	while(vertex[q.top().v] == false)
    	{//检验，如果当前最小堆最小元素所指向的将插入顶点已经是false（就是已经加入了） 
    		q.pop();//把相关数据pop掉 
		}
		//挑出最小权值，和它指向的顶点 
    	min = q.top().w;
    	to = q.top().v;
        q.pop();
        //更新结果
        result += min;
        vertex[to] = false;//更新顶点状态 
        s = edges[to].size();
        for(int j = 0; j < s; j++)
        {//遍历新加入的顶点的邻边 
            long long v = edges[to][j].to, w = edges[to][j].w;
            if(vertex[v])
            {//如果该点未被加入点集
                Edge t(w,v);
                q.push(t);
            }     
        }
    }
    cout<<result;
}
//---------------------Prim算法实现finish---------------------


int main()
{   
	Prim<int>P;
    P.initialize();
    P.prim();
    return 0;
}

B：kruskal算法

描述

使用kruskal算法实现最小生成树

格式

输入

第一行两个整数n,e。n ( $\leq n \leq 200000$ ) 代表图中点的个数，e ( $\leq m \leq 500000$ ) 代表边的个数。
接下来e行，每行代表一条边：

i j w 表示顶点i和顶点j之间有一条权重为w的边

输出

最小生成树所有边的权重和

整体思路描述

Kruskal算法：Kruskal算法是直接从边出发

按权值大小排列所有边，从小到大依次选（顶点数-1）条边
期间若是选中的边导致成环则丢弃，顺位往下
- 检查是否成环用到并查集路径压缩

快速排序基本思想

从数列中取出一个数作为基准数

分区

将比这个数大的数全放到它的右边

小于或等于它的数全放到它的左边

再对左右区间重复第二步，直到各区间只有一个数文章来源地址https://www.toymoban.com/news/detail-761121.html

实现代码

#include<iostream>
using namespace std;

struct node//节点
{ 
	long long weight;//权重
 	int from,to;//两顶点
};
node edge[5000000];//边数组

//----------------边按权重快速排序过程start--------------------- 
void Sort(node *array,int low,int high)//排序
{
	if(low > high) return;//排好了，不运行了
	int i,j;
	node index;
	index = array[low];//定义基准数 
	i = low;
	j = high;
 	while(i < j)
	{
  		while(i < j && array[j].weight >= index.weight)
  		{
  			//从右往左找比基准数小的
   			j--;
		}	
		if(j > i) 
		{
			//交换array[i]和array[j]，并把i右移一位 
			array[i++] = array[j];
		}
		while(i < j && array[i].weight < index.weight)
		{
			//从左往右找比基准数大的
			i++;
		}
		if(j > i) 
		{	
			//交换array[i]和array[j]，并把j左移一位
			array[j--] = array[i];
		}
	}
 	array[i] = index;//基准点归位
 	Sort(array,low,i-1);//递归调用快排比基准点小的元素
 	Sort(array,i+1,high);//递归调用快排比基准点大的元素
}
//---------------边按权重快速排序过程finish---------------------

//--------------父顶点查找压缩，用于检验是否成环start------------- 
int pre[2000000];//记录所有节点的父节点
int find(int x)
{//查找父顶点
 	int root = x;
 	while(root != pre[root])//该顶点有父顶点
 	{
 		root = pre[root];//更新root为该点x的父顶点
	}//一直更新到最上方的顶点
	 
 	while(x != root)
	{//压缩路径，可以理解为将很高的树压缩成很矮的树，使子节点都指向最上方的顶点
  		int temp = pre[x];
  		pre[x] = root;
  		x = temp;//用于让while停止
	}
 	return root;
}
void join(int x,int y)
{//x是y的父顶点，让x的父顶点成为y的父顶点的父顶点，从而实现压缩 
 	pre[find(y)]=find(x);
}
//-------------父顶点查找压缩，用于检验是否成环finish------------- 

int main()
{   
	long long result;
 	int n,e,k = 0;//k用来记录已连接边的数量
 	cin >> n >> e;//输入顶点数和边数 
 	for(int i = 1;i <= e;i++)
 	{   
	 	cin >> edge[i].from >> edge[i].to >> edge[i].weight;
  		int temp = 0;
  		if(edge[i].from > edge[i].to)
		{//无向图按照顶点由小到大的顺序存储，如果不符合，则交换一下 
   			temp = edge[i].from;
   			edge[i].from = edge[i].to;
   			edge[i].to = temp;
  		}
 	}
 	for(int i = 1;i <= n;i++) pre[i] = i;//初始化
 	Sort(edge,1,e);//排序
 	for(int i = 1;i <= e;i++)
 	{//遍历所有的边
  		if(k==n-1) break;//终止条件，选择的边数是顶点数-1 
  		if(find(edge[i].from) != find(edge[i].to))
  		{//排除成环情况 
   			join(edge[i].from,edge[i].to);//合并顶点
   			result += edge[i].weight;//累加权值 
   			k++;//已连接边数加1 
  		}
 	}
 	cout << result << endl;
 	return 0;
}