Minimum Spanning Trees, Prim's Algorithm, and Bridge Upgrades: Part 8 of Ann's Visit to G'Raph

The minimum spanning tree of an undirected graph is the smallest set of edges such that all of the nodes are connected (if possible). Similarly, in a weighted graph, the minimum cost spanning tree is the set of edges with the minimum total weight such that they connect all of the nodes.

Ann went straight to city hall, where she hoped to find more information about the mysterious wizard. Florence and Edgar decided to join her. Or, more accurately, they decided to demonstrate how fast they could navigate G'Raph on their scooters. At least they left their map with Ann.

Ann found the mayor in his office, staring intently at a map of the G'Raph.

"Mayor, I have an important question for you," started Ann.

The mayor did not acknowledge her. He continued to stare at the map, mumbling to himself. Ann started to panic. Had the wizard been here?

After a moment, the mayor finally turned. "Edgar, this will never do. You need to redo it," he snapped.

"What?" asked Edgar. "That is exactly what you requested: the minimum weight spanning tree."

"The what?" asked the mayor with a confused look.

"Umm… I have an important question here," tried Ann, but nobody was paying attention.

"It is the set of bridges to upgrade," Florence explained to the mayor.

The mayor stood silently, not making the connection.



Florence continued. "You asked for the cheapest set of bridges to upgrade such that you could travel between any two islands by only crossing stone bridges. Since the price is determined by the length of the bridges, we found the shortest set of bridges."

"Why would you need to connect all the islands with stone bridges?" asked Ann, forgetting her original question for the moment.

"Nobody wants to be stuck at the dry cleaners after a dragon attack," offered Florence without additional explanation.

"We need a stone bridge between city hall and the library," said the mayor.

"That would add another 3 meters," countered Edgar. "It is cheaper to connect the inn and the dry cleaners." He pointed to the relevant bridges on the map to illustrate.

The mayor started to argue, but Ann cut him off.

"Interesting," interrupted Ann. "You found the set of bridges to replace that will connect all the islands together, while minimizing length. Did it take you long?"

"No," answered Florence. "I used Prim's algorithm.”

“Prim’s algorithm?” asked Ann.

“It is relatively simple algorithm,” said Florence. “You start with a random node, and add it to a new set of connected nodes. In this case, I 'randomly' chose the library.”

"Then you keep adding the closest node that is not already in the set. Here we first add the inn..."

"Then the brewery..."

"All very fascinating," interrupted the mayor. "But the library and city hall should have a new stone bridge between them."

"Edgar and Florence are correct," said Ann. "The lowest cost spanning tree does not have a new bridge there."

"But... I walk that way every day," said the mayor. "I am tired of the wobbly old bridge. We need something new."

Edgar, Florence, and Ann all looked at each other in silence. Edgar took a deep breath to start another algorithmic argument, but thought better of it. It was obvious that an algorithmic argument would not sway the mayor. Edgar decided to submit both prices and let the mayor choose.

Ann remembered why she had gone to the mayor's office in the first place.

"Mister Mayor, I think there is a wizard casting a spell on the scholars of G'Raph,” Ann blurted out. “I think the city and all of its scholars are in danger."

Behind Ann, Edgar and Florence gasped in unison.

To be continued in Part 9: The Game of Hamiltonian Paths.

---------------------------

Follow Ann's visit to G'Raph from the beginning with Part 1: The City of G'Raph.

Also check out the new illustrations in Bullies, Bubble Sort, and Soccer Tickets and Linked Lists, Kindergarten, and Ocean Voyages.