กราฟเพื่อนบ้านที่ใกล้ที่สุด ( NNG ) เป็นกราฟแบบมีทิศทางที่กำหนดสำหรับเซตของจุดในปริภูมิเมตริกเช่นระยะทางแบบยุคลิดในระนาบ NNG มีจุดยอดสำหรับแต่ละจุด และมีขอบแบบมีทิศทางจากpไปยังqเมื่อใดก็ตามที่qเป็นเพื่อนบ้านที่ใกล้ที่สุดของpซึ่งเป็นจุดที่มีระยะห่างจากpน้อยที่สุดในบรรดาจุดทั้งหมดที่กำหนด ยกเว้นpเอง^{[ 1 ]}

ในการใช้งานกราฟเหล่านี้หลายๆ ครั้ง ทิศทางของขอบจะถูกละเลย และ NNG จะถูกกำหนดแทนด้วยกราฟแบบไม่มีทิศทางอย่างไรก็ตาม ความสัมพันธ์เพื่อนบ้านที่ใกล้ที่สุดไม่ใช่ความสัมพันธ์แบบสมมาตร กล่าว คือpจากนิยามไม่จำเป็นต้องเป็นเพื่อนบ้านที่ใกล้ที่สุดสำหรับq ในการอภิปรายเชิงทฤษฎีของอัลกอริทึม มักจะมีการสมมติ ตำแหน่งทั่วไปบางอย่างกล่าวคือ เพื่อนบ้านที่ใกล้ที่สุด (k-ใกล้ที่สุด) นั้นมีเพียงหนึ่งเดียวสำหรับแต่ละวัตถุ ในการใช้งานอัลกอริทึม จำเป็นต้องคำนึงถึงว่านี่ไม่ใช่กรณีเสมอไป สำหรับสถานการณ์ที่จำเป็นต้องทำให้เพื่อนบ้านที่ใกล้ที่สุดสำหรับแต่ละวัตถุมีเพียงหนึ่งเดียว เซตPอาจมีการกำหนดดัชนี และในกรณีที่มีค่าเท่ากัน วัตถุที่มีดัชนีมากที่สุดอาจถูกนำมาเป็นเพื่อนบ้านที่ใกล้ที่สุด^{[ 2 ]}

กราฟเพื่อนบ้านที่ใกล้ที่สุดk ตัว ( k -NNG ) คือกราฟที่จุดยอดpและq สองจุด เชื่อมต่อกันด้วยขอบ หากระยะห่างระหว่างpและ qอยู่ในกลุ่ม ระยะห่างที่เล็กที่สุด kอันดับแรกจากpไปยังวัตถุอื่น ๆ จากP NNG เป็นกรณีพิเศษของk -NNG กล่าวคือเป็น 1-NNG k -NNG เป็นไปตามทฤษฎีบทตัวแยก : สามารถแบ่งออกเป็นสองกราฟย่อยที่มีจุดยอดไม่เกินn ( d + 1)/( d + 2)จุดต่อกราฟย่อย โดยการลบจุด O( k ^{1/ d} n ^{1 − 1/} d) จุด [3] k ^- NNG ^{สามารถประมาณได้} โดยใช้อัลกอริทึมที่มีประสิทธิภาพด้วย recall 90% ซึ่งเร็วกว่าการค้นหาแบบ brute-forceถึงหนึ่งลำดับ^{[ 4 ]}

Another variation is the farthest neighbor graph (FNG), in which each point is connected by an edge to the farthest point from it, instead of the nearest point.

NNGs for points in the plane as well as in multidimensional spaces find applications, e.g., in data compression, motion planning, and facilities location. In statistical analysis, the nearest-neighbor chain algorithm based on following paths in this graph can be used to find hierarchical clusterings quickly. Nearest neighbor graphs are also a subject of computational geometry.

The method can be used to induce a graph on nodes with unknown connectivity.

For a set of points on a line, the nearest neighbor of a point is its left or right (or both) neighbor, if they are sorted along the line. Therefore, the NNG is a path or a forest of several paths and may be constructed in O(n log n) time by sorting. This estimate is asymptotically optimal for certain models of computation, because the constructed NNG gives the answer to the element uniqueness problem: it is sufficient to check whether the NNG has a zero-length edge.^[5]

Unless stated otherwise, it is assumed that the NNGs are digraphs with uniquely defined nearest neighbors as described in the introduction.

1. Along any directed path in an NNG the edge lengths are non-increasing.^[2]
2. Only cycles of length 2 are possible in an NNG and each weakly connected component of an NNG with at least 2 vertices has exactly one 2-cycle.^[2]
3. For the points in the plane the NNG is a planar graph with vertex degrees at most 6. If points are in general position, the degree is at most 5.^[2]
4. The NNG (treated as an undirected graph with multiple nearest neighbors allowed) of a set of points in the plane or any higher dimension is a subgraph of the Delaunay triangulation, the Gabriel graph, and the Semi-Yao graph.^[6] If the points are in general position or if the single nearest neighbor condition is imposed, the NNG is a forest, a subgraph of the Euclidean minimum spanning tree.