skip to Main Content
The smarter way
to do assignments.

Please note that this is just a preview of a school assignment posted on our website by one of our clients. If you need assistance with this question too, please click on the Order button at the bottom of the page to get started.

1. Kruskal’s algorithm will run on a disconnected graph without any problem. Just that the minimum spanning tree will be for the connected portion of graph. The disconnected vertices will not be included in the output. This is because, Kruskal’s algorithm is based on edges of the graph.The loop iterates over the sorted edges. This means that it is considering those portions of the graph that are connected through the edges and generates minimum spanning tree (MST) for the connected portion of the graph. The disconnected vertices are never considered and hence not included at all in output.
2. Let us consider the 1st implementation of Prim’s algorithm. Prim’s algorithm will go into infinite loop and can not generate MST for disconnected graphs. Look at the loop condition , it terminates when the number of vertices in the MST is the same as the number of vertices in the graph. This condition can not be achieved if the graph is disconnected . For example let’s take some vertex u already in B and a disconnected vertex v in graph . Now we can not find an minimum length edge from u (any vertex in B) to v. So v can not be included in the set B. So B will never be equal to N and the loop goes into infinite loop. Therefore Prim’s algorithm can not work on disconnected graphs as it works by considering each of the graph’ s vertices unlike Kruskal’s algorithm, which considers edges (the connected parts of graph)

GET HELP WITH THIS ASSIGNMENT TODAY

Clicking on this button will take you to our custom assignment page. Here you can fill out all the additional details for this particular paper (grading rubric, academic style, number of sources etc), after which your paper will get assigned to a course-specific writer. If you have any issues/concerns, please don’t hesitate to contact our live support team or email us right away.

How It Works        |        About Us       |       Contact Us

© 2018 | Intelli Essays Homework Service®

Back To Top