0
$\begingroup$

Studying for a test in a computer science class and cannot figure out the answer to this question. Any help would be appreciated!

Cost of the MST

Although the picture shows a directed graph, please treat it as an undirected graph, ignoring all the edge orientations.

$\endgroup$

closed as unclear what you're asking by Yuval Filmus, David Richerby, Evil, Juho, Gilles Dec 7 '18 at 20:23

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Does "ignore the edge orientations" mean that graph is meant to be an undirected graph? $\endgroup$ – Apass.Jack Nov 17 '18 at 20:27
  • $\begingroup$ @Apass.Jack Yes. $\endgroup$ – Tommy North Nov 17 '18 at 20:33
  • $\begingroup$ Are you able to apply Prim's algorithm? Where did you get stuck? $\endgroup$ – Apass.Jack Nov 17 '18 at 20:41
  • $\begingroup$ @Apass.Jack No we have not covered Prim's algorithm yet. I am thinking the answer is 42, but I am not 100% positive that is why I wanted to get someone else's opinion. $\endgroup$ – Tommy North Nov 17 '18 at 20:54
  • 3
    $\begingroup$ Just run any MST algorithm you learned. You don't need us for that. $\endgroup$ – Yuval Filmus Nov 17 '18 at 20:58
0
$\begingroup$

A Yuval said, you can just go ahead with any algorithm. In fact, you should probably be able to find a solution by trial and error.

In case you are stuck for some time, move your mouse over to see a solution below.

We can use Prim's algorithm, which iteratively selects an edge of the least weight from the available edges as long as it does not introduce a cycle. We will select the edge of weight 1, two edges of weight 2, all edges of weight 3,4,5,6,7 respectively. We will skip the vertical edge of weight 8 since it introduces a cycle. We will select the horizontal edge of weight 8. Now all vertices have been included except the bottom left one. So we will select the edge of weight 12 to connect vertex. The total weight is 1 + 2 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 12 = 50. So the answer should be "none of the listed".

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.