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).
C++ Program: Nearest Neighbour Algorithm
#include <iostream>
using namespace std;
int main() {
int row, col, srcRow;
// Labels for the 5 vertices in the graph
char vertexLabel[5] = {'A', 'B', 'C', 'D', 'E'};
// Adjacency matrix: adjMatrix[i][j] = distance from vertex i to vertex j
// Use 0 for same vertex, 99 for no direct connection
int adjMatrix[5][5];
// ----------------------------------------------------------------
// Input: read the adjacency (distance) matrix row by row
// ----------------------------------------------------------------
cout << "\nEnter Adjacency Matrix (5x5):\n";
for (row = 0; row < 5; row++) {
cout << "Distances for vertex " << (row + 1) << " (" << vertexLabel[row] << "): ";
for (col = 0; col < 5; col++) {
cin >> adjMatrix[row][col];
}
}
// ----------------------------------------------------------------
// Input: read the threshold distance
// ----------------------------------------------------------------
int threshold;
cout << "\nEnter threshold distance: ";
cin >> threshold;
// ----------------------------------------------------------------
// Input: read the source vertex (A-E)
// ----------------------------------------------------------------
char sourceVertex;
cout << "Enter source vertex (A-E): ";
cin >> sourceVertex;
// Convert the character to the corresponding row index (0-4)
if (sourceVertex == 'a' || sourceVertex == 'A') srcRow = 0;
else if (sourceVertex == 'b' || sourceVertex == 'B') srcRow = 1;
else if (sourceVertex == 'c' || sourceVertex == 'C') srcRow = 2;
else if (sourceVertex == 'd' || sourceVertex == 'D') srcRow = 3;
else if (sourceVertex == 'e' || sourceVertex == 'E') srcRow = 4;
else { cout << "Invalid vertex.\n"; return 1; }
// ----------------------------------------------------------------
// Print all direct connections from the source vertex
// (edges where distance > 0 and distance <= threshold)
// ----------------------------------------------------------------
cout << "\nDirect connections from " << sourceVertex << " within threshold:\n";
for (col = 0; col < 5; col++) {
if (adjMatrix[srcRow][col] <= threshold && adjMatrix[srcRow][col] != 0) {
cout << sourceVertex << " -- " << vertexLabel[col]
<< " (distance = " << adjMatrix[srcRow][col] << ")n";
}
}
// ----------------------------------------------------------------
// Build K1: vertices within threshold (distance <= threshold)
// Include distance == 0 to represent the source vertex itself
// ----------------------------------------------------------------
cout << "\nK1 (close neighbourhood, distance <= " << threshold << "): {";
for (col = 0; col < 5; col++) {
if (adjMatrix[srcRow][col] <= threshold) { // includes self (distance 0)
cout << vertexLabel[col] << " ";
}
}
cout << "}";
// ----------------------------------------------------------------
// Build K2: vertices beyond threshold (distance > threshold)
// ----------------------------------------------------------------
cout << "\nK2 (far neighbourhood, distance > " << threshold << "): {";
for (col = 0; col < 5; col++) {
if (adjMatrix[srcRow][col] > threshold) {
cout << vertexLabel[col] << " ";
}
}
cout << "}\n";
return 0;
}
How the Code Works — Step by Step
Step 1 — Read the Adjacency Matrix
The program reads a 5×5 adjacency matrix where each cell adjMatrix[i][j] holds the edge weight (distance) from vertex i to vertex j. A value of 0 on the diagonal means a vertex has zero distance to itself. A value of 99 (or any large number) is the conventional way to represent the absence of a direct edge.
Step 2 — Read Threshold and Source Vertex
The threshold is an integer distance value. Any vertex reachable within this distance belongs to the close neighbourhood K1. The user also enters a source vertex (A through E), which is then mapped to the corresponding matrix row index (0–4) stored in srcRow.
Step 3 — Print Direct Connections
The program iterates over the source vertex’s row in the matrix. For every vertex where the distance is non-zero and at most the threshold, it prints a connection line showing both the destination vertex and the distance.
Step 4 — Build K1 and K2
K1 contains all vertices (including the source itself, at distance 0) where adjMatrix[srcRow][col] <= threshold. K2 contains all vertices where adjMatrix[srcRow][col] > threshold, meaning they are either very far away or not directly connected (distance 99).
Program Output
Enter Adjacency Matrix (5x5):
Distances for vertex 1 (A): 0 1 2 99 99
Distances for vertex 2 (B): 1 0 99 3 2
Distances for vertex 3 (C): 2 99 0 1 99
Distances for vertex 4 (D): 99 3 1 0 4
Distances for vertex 5 (E): 99 2 99 4 0
Enter threshold distance: 3
Enter source vertex (A-E): A
Direct connections from A within threshold:
A -- B (distance = 1)
A -- C (distance = 2)
K1 (close neighbourhood, distance <= 3): {A B C }
K2 (far neighbourhood, distance > 3): {D E }
Output Explanation
Starting from vertex A with a threshold of 3:
- A → A: distance = 0 — source itself, included in K1.
- A → B: distance = 1 ≤ 3 — within threshold, goes into K1. Also printed as a direct connection.
- A → C: distance = 2 ≤ 3 — within threshold, goes into K1. Also printed as a direct connection.
- A → D: distance = 99 > 3 — far away / not directly connected, goes into K2.
- A → E: distance = 99 > 3 — far away / not directly connected, goes into K2.
The result is K1 = {A, B, C} (close neighbourhood) and K2 = {D, E} (far neighbourhood). This tells us that from vertex A, only B and C are reachable within 3 units of distance.
Sample Graph (Visual Reference)
The adjacency matrix used in the sample input represents the following undirected weighted graph:
Key Concepts Recap
| Concept | Details in This Program |
|---|---|
| Graph representation | 5×5 adjacency (distance) matrix |
| Input | Source vertex + threshold distance |
| K1 (close neighbourhood) | Vertices with distance ≤ threshold |
| K2 (far neighbourhood) | Vertices with distance > threshold |
| No-connection sentinel | 99 (represents infinity / no direct edge) |
Conclusion
The Nearest Neighbour algorithm provides an efficient way to partition a graph’s vertices into a close and far neighbourhood relative to any chosen source node. This implementation demonstrates how an adjacency matrix is used to represent weighted graphs, and how a simple threshold comparison is sufficient to perform neighbourhood-based classification. It forms a conceptual bridge to more advanced algorithms like KNN and K-Means.
Also explore the related DWM programs: