We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
As a hint to anyone stuck on a difficult test, I would recommend a couple of things:
1. consider what properties of the graph would make you would choose Kruskal's over Prim's algorithm for MST.
2. If the greedy solution does not give the MST, then is the graph really undirected? And if the graph is not undirected, how would you solve the more generalized MST algorithm:
while tree does not form a spanning tree,
find an edge that is safe for the tree and add it to the tree.
Can you modify Prim's for the later?
I would post more details, but the platform asks us not to post solutions...
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Kruskal (MST): Really Special Subtree
You are viewing a single comment's thread. Return to all comments →
As a hint to anyone stuck on a difficult test, I would recommend a couple of things: 1. consider what properties of the graph would make you would choose Kruskal's over Prim's algorithm for MST. 2. If the greedy solution does not give the MST, then is the graph really undirected? And if the graph is not undirected, how would you solve the more generalized MST algorithm: while tree does not form a spanning tree, find an edge that is safe for the tree and add it to the tree.
Can you modify Prim's for the later?
I would post more details, but the platform asks us not to post solutions...