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

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.

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.

• Can you clarify your proposed algorithm, say using pseudocode? Mar 27, 2016 at 20:02
• @YuvalFilmus I tried to clarify the algorithm I'm using. I hope it helps. Mar 27, 2016 at 22:54
• 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. Mar 27, 2016 at 22:56

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$.