Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Листинг 5.36. Гамильтонов цикл 
string SetPath() 
{ 
string result = ""; 
for (int j = 1; j < Nodes.Length; j++) 
result += Convert.ToString(Lib.arr[j]) + " 
"; 
return result; 
} 
void Gamilt(int k,
19 / 23

---

181 
System.Windows.Forms.ListBox.ObjectCollection 
Items) 
{ 
int y = Lib.arr[k - 1]; 
int LL = 0; 
if (Nodes[y].Edge != null) 
{ 
LL = Nodes[y].Edge.Length; 
for (int i = 0; i < LL; i++) 
{ 
int u = Nodes[y].Edge[i].numNode; 
if (k == Nodes.Length + 1) 
Items.Add(SetPath());
// 
вывести путь 
else 
if (!Nodes[u].visit) 
{ 
Lib.arr[k] = u; 
Nodes[u].visit = true;
// 
отметить посещенный 
Gamilt(k + 1, Items); 
Nodes[u].visit = false; 
// 
отметить посещенный 
} 
} 
} 
} 
public void
Gamilton(System.Windows.Forms.ListBox.ObjectCollecti
on Items) 
{ 
ClearVisit(); 
20 / 23

---

182 
int N = Nodes.Length; int v0 = 0; 
Lib.arr[1] = v0; 
VisitTrue(v0); // 
отметить посещенный 
Gamilt(2, Items); 
} 
Необходимо отметить, что информация о проходимом пути накаплива-
ется в массиве arr[]. При неуспешном выходе из рекурсивной процедуры 
Gamilt
() переустанавливается значение поля visit = false. 
Как и любой алгоритм с возвратом, данный алгоритм имеет экспонен-
циальную скорость роста. 
Пример. Рассмотрим граф, у которого одна вершина изолирована, а 
ребра, связывающие остальные (N 
− 1) вершину, образуют полный граф. 
Функция Gamilt() никогда не найдет гамильтонова цикла, но она исследует 
все (N 
− 2)! путей, начинающихся в выбранной начальной вершине, каждый 
из которых использует (N 
− 1) рекурсивных вызовов. Следовательно, общее 
число рекурсивных вызовов равно (N 
− 1)!. 
На рисунке 5.14 представлен список гамильтоновых циклов для графа, 
содержащего 7 узлов. 
Рис. 5.14. Гамильтонов цикл