If the graph is unweighted any spanning tree will have same number of edges. That is why it is not called "minimum" - all spanning trees will be 'minimum' trees with number of edges equal to |V|-1.

If the graph is weighted then we are interested in finding a tree with a minimum total sum of the edge weights.

Algorithm to find a spanning tree (similar to finding the shortest path in unweighted graphs)

Data structures needed:

Problem: For a given weighted graph, find a spanning tree with the minimal sum of the weights.

The algorithm is similar to finding the shortest paths in a weighted graphs.
The difference is that we record in the table the length of the current edge, not the length of the path .

Data structures needed:

• A table T with number of rows = number of vertices, and three columns:
  T_i,1 = True if the vertex has been fixed in the tree, False otherwise. This is necessary because the graph is not directed and without this information we may enter a cycle.
  T_i,2 = the length of the edge from the chosen parent (stored in the third column of the table) to the vertex v_i,
  T_i,3 = parent of vertex v_i
• Adjacency lists
• A priority queue of vertices to be processed.
  The priority of each vertex is determined by the weight of edge that links the vertex to its parent. The priority may change if we change the parent.

1. Initialize first column to False, select a vertex s and store it in the priority queue
   with priority = 0, set T_s,2 = 0, T_s,3 = root
   (It does not matter which vertex is chosen, because all vertices have to be in the tree.)

2. While there are vertices in the queue:
1. DeleteMin a vertex v from the queue and set T_v,1 = True
2. For all adjacent vertices w:
• If T_w,1 = T do nothing
• If T_w,2 is empty:
• T_w,2 = weight of edge (v,w) (stored in the adjacency list)
• T_w,3 = v (this is the parent)
• append w in the queue with priority = weight of (v,w)
• If T_w,2 > weight of (v,w)
• Update T_w,2 = weight of edge (v,w)
• Update the priority of w (this is done by updating the priority of an element in the queue - decreaseKey operation. Complexity O(logV))
• Update T_w,3 = v

At the end of the algorithm, the tree would be represented in the table with its edges

{(T_i,3 , v_i ) | i = 1, 2, -|V|}

Complexity: O(| E |log(| V |))
All edges have to be examined, and in the worst case each edge might cause updating of the priority queue.

If adjacency matrix is used, the complexity would increase to O(|V|²)

Kruskal's algorithm works with tree forests and the set of edges.

Algorithm:

1. Initially we build |V| trees consisting of one vertex only - each vertex is a tree of its own.
   The edges are stored in a priority queue with priority - the weight.

2. While the number of distinct trees is greater than one:
DeleteMin an edge (u,v) from the priority queue.
1. If u and v belong to one and the same tree, do nothing.
2. If u and v belong to different trees, link the trees by the edge

The algorithm is implemented using operations on disjoint sets.
All the vertices are grouped into sets corresponding to the currently built trees.
Since each vertex appears in one tree only, the sets are disjoint.

Two set operations are used:

1. comparison:

Each vertex is associated with the disjoint set where it belongs.
To find out whether two vertices are in the same tree,
we need to find out if their disjoint sets are the same.

2. union:

When we link the trees, the combine the two disjoint sets to form one set
- corresponding to the new tree

For sparse trees Kruskal's algorithm is better - since it is guided by the edges.

For dense trees Prim's algorithm is better - the process is limited by the number of the vertices in the graph.