We store in the queue
each vertex only once (O(|V|)).

In step 2b. we examine the outgoing edges for a given vertex,
thus the sum of all examined edges in the **while** loop will be equal to
the the number of all edges -
(O(|E|)).

**
**

**Minimum spanning tree in weighted graphs - Prim's algorithm**
**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.

Algorithm:

- 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.)
- While there are vertices in the queue:
**DeleteMin** a vertex **v** from the queue and
set **T**_{v,1} = True
- 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|^{2})

**
**

**Minimum spanning tree in weighted graphs - Kruskal's algorithm
**
Kruskal's algorithm works with tree forests and the
set of edges.

**Algorithm:**

- 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.
- While the number of distinct trees is greater than one:
**DeleteMin** an edge **(u,v)** from
the priority queue.
- If
**u** and **v**
belong to one and the same tree, do nothing.
- If
**u** and **v**
belong to different trees, link the trees by the edge

Implementation

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:

- 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.

- union:
When we link the trees, the combine the two disjoint
sets to form one set

- corresponding to the new tree

Disregarding the lower term O(|V|) we get O(|E|(log(|V|) + log(|E|)).

At the worst case |E| = O(|V|^{2}). Hence log(|E|) = O(log(|V|^{2})) =
O(2log(|V|)) = O(log(|V|).

Thus we get complexity O(|E|log(|V|)).

On the other hand, |V| = O(|E|), hence we can reduce the complexity
expression to O(|E|log(|E|)).