3
$\begingroup$

I just wrote a program that runs the Travelling Salesman Problem using the Nearest Neighbor Algorithm. Afterwards, I started looking into Minimum Spanning Trees (MST).

From my understanding:

The Nearest Neighbor Algorithm traverses a graph starting at one vertex, and then it travels to the next vertex following the edge with the shortest distance (lightest weight) between them.

An MST is a subgraph of the original graph whose vertices are all connected. The total of the edge weights in the subgraph should be as small as possible. You can use Kruskal's algorithm to find MSTs.

As I was looking at the paths taken when implementing the Nearest Neighbor Algorithm, I noticed that it could possibly sometimes return a MST.

Is the Nearest Neighbor Algorithm a valid algorithm to find a Minimum Spanning Tree?

It seems like it should be. It's terribly similar to Kruskal's algorithm (from what I have read so far). However, I never see it listed as a possible option for finding MSTs.

Thanks for any help in advance.

Edit for clarity:

The Nearest Neighbor Algorithm is described here. From what I read, it works like so:

startVertex = vertex V
for (egdes : totalEdges){
    find the edge with the smallest weight connected to vertex V that has    not been visited
}
nextVertex = vertex on the other end of the edge with the smallest weight
move to nextVertex

Here is an example:
Each vertex is visited and, looking at the red lines, you get an MST for that graph.

enter image description here
If you do that, you get an MST. My question is, is that a valid way of getting an MST? It seems like it is since it's so much like Kruskal's or Prim's algorithm.

$\endgroup$
  • 1
    $\begingroup$ Can you clarify your proposed algorithm, say using pseudocode? $\endgroup$ – Yuval Filmus Mar 27 '16 at 20:02
  • $\begingroup$ @YuvalFilmus I tried to clarify the algorithm I'm using. I hope it helps. $\endgroup$ – JustBlossom Mar 27 '16 at 22:54
  • 2
    $\begingroup$ Your example shows that you actually don't get an MST: if you replace BC with CD then you get a spanning tree with lower weight. However, Prim's algorithm, which is somewhat similar to what you propose, does work. $\endgroup$ – Yuval Filmus Mar 27 '16 at 22:56
4
$\begingroup$

Your algorithm starts at some vertex and then always move to the closest vertex that's not been visited so far. That's not guaranteed to find the minimum spanning tree, as the example in your question shows.

First, in a general graph, the algorithm might get stuck: you might end up at a vertex where you've already visited all the neighbours. For example, if you start your algorithm at $D$, it will go to $B$, then $C$ and then it's stuck because it's already visited both of $D$'s neighbours. The set-up of Hamiltonian cycle avoids this possibility by having an edge between every pair of vertices.

Second, even if your graph contains every possible edge, the algorithm can only produce a path, so it won't produce the minimum spanning tree in any graph where the M.S.T. isn't a path. For example, take vertices $\{1, \dots, n\}$ with $w(1,i)=1$ for all $i$ and $w(i,j)=2$ for all $i,j\geq 2$. The M.S.T. is all the edges from $1$, and this has weight $n-1$. But your algorithm will find some path that uses only one or two of the weight-$1$ edges, so will have weight $2n-3$ or $2n-4$.

$\endgroup$
0
$\begingroup$

Your algorithm (if I understand it correctly) is known as Prim's algorithm, another algorithm that finds a minimum spanning tree.

$\endgroup$
  • $\begingroup$ I don't think that's the algorithm being described. Prim adds the cheapest edge from the tree that's been built so far to a vertex not in that tree. The algorithm described in the question seems to me to just produce a path: it maintains a "current vertex" and, at each step, moves to the unvisited vertex closest to the current vertex. $\endgroup$ – David Richerby Mar 27 '16 at 19:55
  • 1
    $\begingroup$ Yes, the algorithm isn't so clear. I asked for a clarification. $\endgroup$ – Yuval Filmus Mar 27 '16 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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