Today, when I was doing Los Valley, I found that my mastery of the algorithm in this area still needs to be improved. Let’s introduce the minimum spanning tree algorithm first.

Minimum spanning tree

The minimum Spanning Tree is a structure with n vertices and N minus 1 edges that connects a connected graph with the minimum weight. The minimum spanning tree can be found using either Prim or Kruskal. In addition, it can be generated using BFS and DFS, called BFS spanning tree and DFS spanning tree respectively. Ex. :

Prim algorithm

Here is the use of adjacent-matrix storage, personally think Prim and the most short circuit dijkstra is very similar, method: ① First establish a tree with only one node, this node can be any one of the original picture.

(2) Use an edge to expand the tree, requiring that one vertex of this edge is in the tree and the other vertex is not in the tree, and the weight of this edge is required to be the minimum.

③ Repeat step ② until all vertices are in the tree. As shown in figure:

#include<stdio.h>
#define MAX 100
#define MAXCOST 100000

int graph[MAX][MAX];

void prim(int graph[][MAX], int n)
{
    int lowcost[MAX];Lowcost [I]: indicates the minimum weight of the edge ending with I. When lowcost[I]=0, it means that MST is added at point I
    int mst[MAX];// indicates the starting point of lowcost[I]. When MST [I]=0, indicates that MST is added to the starting point I
    int i, j, min, minid, sum = 0;
    for (i = 2; i <= n; i++)
    {
        lowcost[i] = graph[1][i];// Lowcost specifies the length of the path to which vertex 1 is reachable
        mst[i] = 1;// Initialization starts at 1 bit
    }
    mst[1] = 0;
    for (i = 2; i <= n; i++)
    {
        min = MAXCOST;
        minid = 0;
        for (j = 2; j <= n; j++)
        {
            if(lowcost[j] < min && lowcost[j] ! =0)
            {
                min = lowcost[j];// Find the path length with the shortest weight
                minid = j; // Find the smallest ID}}printf("V%d-V%d=%d\n",mst[minid],minid,min);
        sum += min;/ / sum
        lowcost[minid] = 0;// Set the shortest path to 0
        for (j = 2; j <= n; j++)
        {
            if (graph[minid][j] < lowcost[j])// Update the path to the vertex directly from this point{ lowcost[j] = graph[minid][j]; mst[j] = minid; }}}printf("Sum of minimum weights =%d\n",sum);
}
int main(a)
{
    int i, j, k, m, n;
    int x, y, cost;
    scanf("%d%d",&m,&n);//m= number of vertices, n= number of edges

    for (i = 1; i <= m; i++)// Initialize the graph
    {
        for (j = 1; j <= m; j++) { graph[i][j] = MAXCOST; }}for (k = 1; k <= n; k++)
    {
    scanf("%d%d%d",&i,&j,&cost);
        graph[i][j] = cost;
        graph[j][i] = cost;
    }

    prim(graph, m);
    return 0;
}

Copy the code

Kruskal algorithm

Kruskal’s algorithm is an algorithm that can get a minimum spanning tree in O(mlogm) time. It’s largely based on the idea of greed:

(1) Order the edges in order of edge weight from smallest to largest, and build a graph T without edges.

② Select an edge with the smallest weight that has not been selected.

(3) If the two vertices of this edge are not the same connected block in T, then add it to the graph T, the same will skip.

④ Repeat ② and ③ until the graph T is connected. You just need to maintain the connectivity, you don’t need to actually build the graph T, you can use and look up sets to maintain it.Here we operate with an adjacency list (not a linked list) :

#include <stdio.h>
#define MAXE 100
#define MAXV 100
typedef struct{
	int vex1;                     // The starting vertex of the edge
	int vex2;                      // The terminating vertex of the edge
	int weight;                    // The edge weight
}Edge;
void kruskal(Edge E[],int n,int e)
{
	int i,j,m1,m2,sn1,sn2,k,sum=0;
	int vset[n+1];
	// Borrow an auxiliary array vset[I] to determine if an edge is added to the minimum spanning tree set
	Each vertex is regarded as a connected component and initialized by looking up the set number
	for(i=1; i<=n; i++)// Initialize the auxiliary array
		vset[i]=i;
	k=1;// represents the KTH edge of the current constructed minimum spanning tree, with an initial value of 1
  	j=0;// the subscript of the edge in E, the initial value is 0
   while(k<e)// Continue the loop if the number of edges generated is less than e
   {
       m1=E[j].vex1;
       m2=E[j].vex2;// Take two adjacent points of an edge
       sn1=vset[m1];
       sn2=vset[m2];
	       // Get the set number of each vertex
	    if(sn1! =sn2)// Two vertices belong to different sets. This edge is an edge of the minimum spanning tree
	    {// Prevent the occurrence of closed loop
			printf("V%d-V%d=%d\n",m1,m2,E[j].weight);
			sum+=E[j].weight;
			k++;                // The number of generated edges is increased
			if(k>=n)
				break;
			for(i=1; i<=n; i++)// Both sets are numbered uniformly
				if (vset[i]==sn2)  // Change set number sn2 to SN1
					vset[i]=sn1;
	    }
     j++;                  // Scan the next edge
   }
    printf("Sum of minimum weights =%d\n",sum);
}
// The following is quicktype
int fun(Edge arr[],int low,int high)
 {
 	int key;
 	Edge lowx;
 	lowx=arr[low];
 	key=arr[low].weight;
 	while(low<high)
 	{
 		while(low<high && arr[high].weight>=key)
 			high--;
 		if(low<high)
 			arr[low++]=arr[high];

 		while(low<high && arr[low].weight<=key)
 			low++;
 		if(low<high)
 			arr[high--]=arr[low];
	 }
	 arr[low]=lowx;
	 return low;
  }
void quick_sort(Edge arr[],int start,int end)
{
	int pos;
	if(start<end)
	{
	pos=fun(arr,start,end);
	quick_sort(arr,start,pos- 1);
	quick_sort(arr,pos+1,end); }}int main(a)
{
	Edge E[MAXE];
	int nume,numn;
    //freopen("1.txt","r",stdin); // File input
	printf("Input top number and edge number :\n");
	scanf("%d%d",&numn,&nume);
	for(int i=0; i<nume; i++)scanf("%d%d%d",&E[i].vex1,&E[i].vex2,&E[i].weight);
	quick_sort(E,0,nume- 1);
	kruskal(E,numn,nume);
}
Copy the code