Undirected graph minimum spanning tree problem description

The minimum spanning tree of an undirected graph G is the tree consisting of the edges of all vertices of the graph that link G, with the lowest total value. A minimum spanning tree exists if and only if the graph is connected. For simplicity, the following algorithms assume that graphs are connected. There are two typical algorithms of undirected graph minimum spanning tree, Prim and Kruskal, which are respectively introduced below.

Prim algorithm

Core idea of algorithm

Add the associated vertices to the tree step by step in a greedy strategy.

Algorithm is introduced

Each stage of the algorithm is accomplished by:

  1. Choose an edge (u, v) such that the value of (u, v) is the smallest of all the edges where u is on the tree but v is not. And add the corresponding vertex V to the tree.
  2. Continue until all vertices are in the tree.

The illustration example

The core code

Public void prim(Vertex start){// Declare that all vertices are not in the treefor(Vertex v:graph){
		v.isInTree=false; v.dist=Integer.MAX_VALUE; } start.dist = 0; PriorityQueue<Vertex> PriorityQueue = new PriorityQueue<Vertex>(); priorityQueue.add(start);while(! priorityQueue.isEmpty()){ Vertex v=priorityQueue.poll();if(v! =null){if(! V.isintree){// The vertex is not in the tree //1true;
			if(v.adj! =null&&! v.adj.isEmpty()){for(AdjVertex Adjw: v.ajj){// Update the shortest vertex in the adjacency table with a change in distance and add the vertex to the priority queueif(adjw.cvw<adjw.w.dist){
					    adjw.w.setDist(adjw.cvw);
					    adjw.w.setPath(v);
					    priorityQueue.add(adjw.w);
						}
					}
				}
			}
		}
	}
}
Copy the code

Kruskal algorithm

Core idea of algorithm

With the greedy strategy, the alternative edge is continuously selected according to the minimum weight, and the edge is selected when the selected edge does not produce a circle.

Algorithm is introduced

Analysis of the

Kruskal is similar to treating a forest. There exist when the initial | V | single node tree, each add an edge to merge two trees, when only a tree at the termination of the algorithm.

Data structure selection

  1. As a result of this analysis, Kruskal needs a data structure that supports find (finding the current tree to which the node belongs) and Union (merging two trees). A good data structure that supports find/ Union operations today is the disjoint set.
  2. Choose the least weighted edge each time. Build the heap with the weight of an edge, deletemin each time.

Algorithm is the core

At any time in the algorithm, two vertices belong to the same set if and only if they are connected in the current generation forest.

The illustration example

The core code

public List<Edge> kruskal() { List<Edge> result = new ArrayList<Edge>(); int vertexSize = graph.values().size(); int acceptedEdge = 0; DisjSets = new DisjSets(vertexSize); PriorityQueue<Edge> PriorityQueue = new PriorityQueue<Edge>(getEdges());while(acceptedEdge < vertexSize - 1&&! priorityQueue.isEmpty()) { Edge e = priorityQueue.poll(); int disv = disjSets.find(e.vnum); int disw = disjSets.find(e.wnum);if(disv ! // acceptedEdge++; disjSets.union(disv, disw); result.add(e); }}return result;
}
Copy the code

Full code address

github

Prim

Kruskal

Yards cloud

Prim

Kruskal