The Nearest Neighbour Algorithm is one of the foundational concepts in Data Warehousing and Mining (DWM). It is used to analyse a graph or dataset and classify its nodes into two groups based on a given threshold distance. A node is placed in the close neighbourhood (K1) if it is within the threshold, and in the far neighbourhood (K2) if it exceeds it.
In this post we walk through a well-commented C++ implementation that reads an adjacency matrix of 5 vertices, accepts a starting vertex and a distance threshold, and partitions all connected vertices into the two neighbourhood sets K1 and K2.
What is the Nearest Neighbour Algorithm?
Given a graph represented as an adjacency matrix where adjMatrix[i][j] stores the distance (edge weight) between vertex i and vertex j, the algorithm works as follows for a chosen source vertex s:
Read the distance from s to every other vertex from the adjacency matrix row corresponding to s.
For each vertex v: if the distance is greater than 0 (there is an edge) and less than or equal to the threshold, add v to K1.
If the distance exceeds the threshold, add v to K2.
Also print all direct connections along with their distances.
A value of 0 on the diagonal represents the distance from a vertex to itself (no self-loops). A large value like 99 is typically used to represent no direct connection (infinity).