Question

Describe an algorithm for finding a spanning tree with minimal weight containing a specified set of edges in a connected weighted undirected simple graph.

Short answer

Use Kruskal's algorithm with initially using empty graph with the specified set of edges (instead of the empty set) and end the algorithm when n-1 edges were determined.

Step-by-step solution

Definition

A graph is connected if there exists a path between every pair of vertices.

Kruskal's algorithm:

Start from a graph \({\bf{T}}\) that contains only the vertices and no edges. Repeatedly select the edge in the given graph\({\bf{G}}\) with the smallest weight (that doesn't cause a circuit) and add it to the graph \({\bf{T}}\). Once the graph is connected, we have found a minimum spanning tree.

Step 2:Using the Kruskal’s algorithm

We have a been given a connected weighted undirected simple graph \({\bf{G}}\) with a specified set of edges \({\bf{E}}\).

In Kruskal's algorithm, we initially stated with an empty graph \({\bf{T}}\). We will adjust this by starting with the empty graph \({\bf{T}}\) and the edges in \({\bf{E}}\) added to \({\bf{T}}\).

The rest of Kruskal's algorithm will work the same, that is we repeatedly add edges with the smallest weight that do not cause a circuit until we obtain \({\bf{n - 1}}\) edges.