普里姆算法最小生成树

What to Learn?

学什么？

How to construct minimum spanning tree using Prim's Minimum Spanning Tree algorithm and its C++ implementation?

如何使用Prim的最小生成树算法及其C ++实现构造最小生成树？

Minimum Spanning Tree is a tree with all the vertices of the graph and who has a minimum weight.

最小生成树是具有图形的所有顶点且权重最小的树。

In the figure there is a graph with 9 vertexes.

图中有一个具有9个顶点的图形。

If we construct a minimum spanning tree then it would be like,

如果我们构造一个最小生成树，那么它将是，

Algorithm:

算法：

To implement the Prim's Minimum Spanning Tree algorithm, we have an array of all the vertices with their corresponding distance.

为了实现Prim的最小生成树算法 ，我们有一个所有顶点及其对应距离的数组。

1. Initially, all the vertices have a distance infinity except the starting vertex which has distance zero.

   最初，除起始顶点的距离为零外，所有顶点的距离都为无穷大。

2. We check the all the unvisited reachable vertices from the starting vertex and update all the distance with weighted edge distance from that vertex.

   我们从起始顶点检查所有未访问的可达顶点，并使用从该顶点开始的加权边距更新所有距离。

3. Choose the minimum unvisited distance and choose the corresponding vertex.

   选择最小未访问距离，然后选择相应的顶点。

4. Repeat step 2 and 3 until all the vertices are visited.

   重复步骤2和3，直到所有顶点都被访问为止。

Example with explanation:

带有说明的示例：

The above algorithm is described using an example (graph above),

以上算法是通过示例(上图)进行描述的，

We first start with vertex 0 and the array is initially.

我们首先从顶点0开始，数组最初是。

Then look for unvisited reachable vertices with minimum distance. From vertex 0 unvisited vertices are 1 and 2 and 1 has a minimum weighted edge then it attached with vertex 0.

然后，以最小的距离查找未访问的可达顶点。 从顶点0开始，未访问的顶点为1和2，并且1的加权边最小，然后与顶点0相连。

And the array is:

数组是：

Then from vertex 1 unvisited reachable vertices are 2, 7 and from vertex 0 unvisited reachable vertex is 7 and both have same distance so choose any one from them.

然后从顶点1看不到的可达顶点为2、7，从顶点0看不到的可达顶点为7，并且两者的距离相同，因此请从中选择任意一个。

And the array is,

数组是

And finally, the spanning tree will be this...

最后， 生成树就是这个……

C++ implementation:

C ++实现：

#include 
    
     using namespace std;//Make a pair between vertex x and vertex y //who's weighted edge is z void addedge(list< pair
     
       > *ls,int x,int y,int z){
   	ls[x].push_back(make_pair(y,z));		ls[y].push_back(make_pair(x,z));	return;} //Find the minimum value of weighted edges from unvisited //vertices and return the vertexint mini(bool *visit,int num,int arr[][9]){
   	int temp=INT_MAX;	int store;	for(int i=0;i
      
        >*ls,list< pair
       
         >*min_span,int num,int x){
   	int arr[2][9];	//create a matrix with the same number of 	//vertices the graph have	for(int i=0;i
        
          >::iterator it;		for(it=ls[temp].begin();it!=ls[temp].end();it++){
   			//when not visited and distance is greater 			//then cuuent distance 			if(!visit[it->first] && arr[1][it->first]>it->second){
   				arr[1][it->first]=it->second;			}		}		//find the minimum weighted edge attached vertex		x=mini(visit,num,arr);		count++;	}	cout<<"Index with their distance"<
         
           > *ls,int num){ list
          
           
             >::iterator it; for(int i=0;i<9;i++){ cout<
            <<"-->"; for(it=ls[i].begin();it!=ls[i].end();it++){ cout<
             
              first<<" ("<
              
               second<<")"<<"-->"; } cout<
               
                 > ls[num]; list
                
                 
                   > min_span[1]; addedge(ls,0,1,4); addedge(ls,0,7,8); addedge(ls,1,7,11); addedge(ls,1,2,8); addedge(ls,7,6,1); addedge(ls,7,8,7); addedge(ls,2,3,7); addedge(ls,2,5,4); addedge(ls,2,8,2); addedge(ls,8,6,6); addedge(ls,6,5,2); addedge(ls,5,4,10); addedge(ls,5,3,14); addedge(ls,3,4,9); cout<<"Print of adjacency matrix:"<
                  
                    >::iterator it; for(it=min_span[0].begin();it!=min_span[0].end();it++){ cout<
                   
                    first<<" ("<
                    
                     second<<")"<<"-->"; } return 0;}
                    
                   
                  
                 
                
               
              
             
           
          
         
        
       
      
     
    

Output

输出量

Enter the no. of vertices :9Print of adjacency matrix:0-->1 (4)-->7 (8) 1-->0 (4)-->7 (11)-->2 (8) 2-->1 (8)-->3 (7)-->5 (4)-->8 (2)3-->2 (7)-->5 (14)-->4 (9)4-->5 (10)-->3 (9)5-->2 (4)-->6 (2)-->4 (10)-->3 (14)6-->7 (1)-->8 (6)-->5 (2)7-->0 (8)-->1 (11)-->6 (1)-->8 (7)8-->7 (7)-->2 (2)-->6 (6)Index with their distance0 01 42 83 74 95 46 27 18 2Path of the spanning tree0 (0)-->1 (4)-->2 (8)-->8 (2)-->5 (4)-->6 (2)-->7 (1)-->3 (7)-->4 (9)

翻译自:

普里姆算法最小生成树