1>What is the difffernce between minimum spanning tree and nearest neighbor forest?
Nearest neighbour forests occur specifically in the context of Euclidean/geometric graphs.
Consider a Euclidean space where each point is a node (vertex). Let us assume that no two inter-point distances are the same in this space. (At this point, I am not sure if this assumption is valid or necessary.)
We now build a nearest neighbour graph by drawing a directed edge from every node to the node that is nearest to it in terms of Euclidean distance. This can be a disconnected graph.
Now replace all directed edges with undirected ones (and also replace resulting multi-edges with single edges). Intuitively, what you get now is a nearest neighbour forest.
I guess it can be argued that each nearest neighbour tree in this forest is the minimum spanning tree for the component/subspace that it covers (because it has been built based on spatial proximity).
(Am not sure of this. Need to take a break and come back to it later.)
Print