Question

Express the algorithm devised in Exercise \(22\) in pseudo code.

Short answer

Procedure adjusted Kruskal(G: weighted connected undirected graph with n vertices; \(S\): set of some edges in \({\bf{G}}\))

\({\bf{T: = }}\)empty graph

\({\bf{T: = }}T \cup S\)

procedure adjusted Kruskal \({\bf{G}}\) : weighted connected undirected graph with \({\bf{n}}\) vertices; \(S\): set

\({\bf{T: = }}\)empty graph

\({\bf{T: = }}T \cup S\)

For\({\bf{i: = 1}}\) to \({\bf{n - m - 1}}\)

(When the edge is added to \({\bf{T}}\)).

\({\bf{r: = }}T \cup \{ e\} \)

return \({\bf{T}}\)

for \({\bf{i: = 1}}\) to \({\bf{n - m - 1}}\)

\({\bf{e: = }}\)edge in \({\bf{G}}\) of minimum weight not forming a simple circuit in \({\bf{T}}\)

(When the edge is added to \({\bf{T}}\)).

\({\bf{T: = }}T \cup \{ e\} \)

return \({\bf{T}}\)

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.

Using the Kruskal’s algorithm

One calls the procedure "adjusted Kruskal" and the input is a weighted connected undirected graph with \({\bf{n}}\) vertices and a specified set of edges. procedure adjusted Kruskal (\({\bf{G}}\): weighted connected undirected graph with \({\bf{n}}\) vertices;

\(S\): set of some edges in \({\bf{G}}\)) We initially \({\bf{T}}\) to be an empty graph and then add all edges in \(S\) to \({\bf{T}}\). Let \({\bf{m}}\) represents the number of edges in \(S\). \({\bf{T: = }}\) empty graph \({\bf{T: = }}T \cup S{\bf{m: = }}\) Number of edges in \(S\) A tree with \({\bf{n}}\) vertices contain \({\bf{n - }}1\) edges. Since \({\bf{T}}\) already contains \({\bf{m}}\) edges, we need to add \({\bf{n - }}1{\bf{ - m}}\) or \({\bf{n - m - 1}}\) edges. In each step, we search for the edge \(e\) with the smallest weight among all edges in \({\bf{G}}\) and this edge cannot form a simple circuit in \({\bf{T}}\) (when added to \({\bf{T}}\)). When the edge \(e\) is found, we add it to the tree \({\bf{T}}\). for \({\bf{i: = 1}}\) to \({\bf{n - m - 1}}\;\;\;{\bf{e: = }}\) edge in \({\bf{G}}\) of minimum weight not forming a simple circuit in \({\bf{T}}\) (when the edge is added to \({\bf{T}}\)). \({\bf{T: = }}T \cup \{ e\} \) Finally, when we the tree contains \({\bf{n - }}1\)edges, one has found the spanning tree with minimal weight containing all edges in \(S\). Thus,one then returns the tree \({\bf{T}}\), return \({\bf{T}}\).