Graph Theory, with algorithms like kruskal and something more

Question

The new government of the archipelago of Sealand has decided to join six islands by bridges to connect them directly. The cost of building a bridge depends on the distance between the islands. This table shows the distances between islands:

    B   C   D   E   F
A   5   6   4   3   7
B   −   2   4   8   5
C   −   −   4   8   8
D   −   −   −   2   5
E   −   −   −   −   4

The government wants to build a bridge system so that the total cost of the work is minimal.

a) Using graph theory, finding bridges to be constructed so that the total cost of the work is minimal.

b) Suppose the capital is on the island B and can only build a bridge between two islands if any of these previously communicates with the capital (machinery has to be transported through the bridges). In what order should build bridges?

I solved a) With Kruskal, so I have bridges from AE, DE, BC, BD, EF with 15 total cost . But I don't know how to solve b). Could you help me

Answer 1

For part b, you only need to order the edges away from $B$ (as far as I can see). $BD$ must be built before $DE$, for example.

Answer 2

After part (a) you have a spanning tree; within that spanning tree there is a unique path from any node to any other node. (There is at most one path from node X to node Y because it's a tree; there is at least one path from node X to node Y because it's a connected graph). For each node other than B, the unique path from B provides an ordering in which the bridges can be built.

If you're looking for the name of an algorithm which enumerates the edges in a suitable order, either depth-first search or breadth-first search would do, along with any number of less generally useful search strategies.