Таким чином, задача пошуку маршруту може розглядатися як задача вибору чергової крапки (міста) і пошуку частини маршруту, що залишилося, тобто має місце рекурсія.
Граф можна представити двовимірним масивом, що назвемо mар (карта). Значення елемента масиву map[i,j] — це відстань між містами і і j, якщо міста з'єднані дорогою, чи нуль, якщо міста не з'єднані прямої дорогою. Для приведеного графа масив mар можна зобразити у виді таблиці в такий спосіб:
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
|
2 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
3 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
|
4 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
|
5 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
6 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
|
7 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
Вміст клітинки таблиці на перетинанні рядка й і стовпця j відповідає значенню map[і,j].
Крім масиву map нам будуть потрібні масив road (дорога) і масив inci (від include — включати). У road ми будемо записувати номера пройдених міст. У момент досягнення кінцевої вершини він буде містити номера всіх пройдених вершин, тобто опис маршруту.
У incl[і] будемо записувати true, якщо вершина з номером і включена в маршрут. Робиться це для того, щоб не включати в маршрут уже пройдену вершину (не ходити по колу).