212
правок
Изменения
→Псевдокод
== Псевдокод ==
Функция <tex>findHamiltonianCycle</tex> получает на вход очередь вершин граф и находит гамильтонов цикл в графенем.
{| width = 100%
|-
|
'''function''' <tex>\mathtt{findHamiltonianCycle}(G):</tex> <tex>\mathtt{Queue}</tex> <tex>\mathtt{queue}</tex> '''for''' <tex> v \in V</tex>: <font color = "green">// Добавляем все вершины графа в очередь</font> <tex>\mathtt{queue.pushBack}(v):</tex>
'''for''' k = 0...n*(n - 1)
'''if''' <tex>(queue.\mathtt{queue.at}(0), queue.\mathtt{queue.at}(1)) \notin E</tex> <font color = "green">// Проверяем существования ребра между первой и второй вершинами очереди</font> <tex>\mathtt{i } = 2</tex> '''while''' <tex>(queue.\mathtt{queue.at}(0), queue.\mathtt{queue.at}(i)) \notin E</tex> '''or''' <tex>(\mathtt{queue.at}(1), \mathtt{queue.at}(i + 1)) \notin E</tex> <tex>\mathtt{i}</tex>++ <font color = "green">// Ищем индекс удовлетворяющую условию вершины</font> <tex>queue.\mathtt{queue.swapSubQueue}(2, i)</tex> <font color = "green">// Разворачиваем часть перестановки от 2-й до найденной позиции включительно</font> <tex>queue.\mathtt{queue.pushBack}(queue.\mathtt{queue.top}())</tex> <tex>queue.\mathtt{queue.pop}()</tex>
|}
