質問

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.

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top