Powtarzalny algorytm najbliższego sąsiada (ang. repetitive nearest neighbour algorithm, w skrócie RNN) – algorytm służący do rozwiązywania problemu komiwojażera korzystający z algorytmu najbliższego sąsiada.

Algorytm polega na wielokrotnym wykonaniu algorytmu najbliższego sąsiada w taki sposób, aby każdy wierzchołek raz był wierzchołkiem początkowym. Następnie algorytm zwraca najlepsze spośród otrzymanych rozwiązań.

Dla grafu pełnego algorytm ma złożoność O(n³), gdzie n jest liczbą wierzchołków. W trakcie wykonywania algorytmu RNN n razy zostanie wykonany algorytm najbliższego sąsiada, który ma złożoność czasową O(n²).

Algorytm RNN nie daje gwarancji znalezienia rozwiązania optymalnego. W odróżnieniu od algorytmu najbliższego sąsiada daje jednak gwarancję, że zwróci rozwiązanie co najmniej tak dobre, jak n/2-1 innych rozwiązań (dowód i więcej informacji na ten temat znajduje się w pracy podanej w bibliografii).

Algorytmy zachłanne (ang. greedy algorithms) – algorytmy podejmujące w każdym kroku taką decyzję, która w danej chwili wydaje się najkorzystniejsza. Inaczej mówiąc, algorytmy zachłanne dokonują zawsze wyborów lokalnie optymalnych licząc, że doprowadzi to do znalezienia rozwiązania globalnie optymalnego. W ogólnym przypadku algorytmy zachłanne nie zawsze znajdują rozwiązanie optymalne. Są one zatem podzbiorem algorytmów heurystycznych. Jednocześnie są to algorytmy deterministyczne – nie ma w nich losowości.

Bardzo prostym przykładem algorytmu zachłannego może być szukanie najwyższego punktu na określonym obszarze poprzez przesuwanie się zawsze w kierunku największego nachylenia (nigdy się nie cofając ani nie rozpatrując kilku wariantów drogi). Jak widać, w ten sposób prawdopodobnie dojdziemy do wierzchołka położonego najbliżej od punktu początkowego, który niekoniecznie będzie najwyższym.

Minimalne drzewo rozpinające (ang. minimum spanning tree, w skrócie MST), inaczej drzewo rozpinające o minimalnej wadze – drzewo łączące wszystkie wierzchołki pewnego grafu spójnego mające najmniejszą możliwą sumę wag krawędzi.

Jeśli graf ma v wierzchołków, to jego drzewo rozpinające zawsze będzie miało v-1 krawędzi. Jeśli ten graf ma e krawędzi, aby utworzyć drzewo rozpinające, trzeba usunąć z grafu e-v+1 krawędzi. Liczba ta jest określana jako liczba cyklomatryczna.