Изменения

Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре

56 байт убрано, 16:20, 6 декабря 2013

→‎Псевдокод

|-

|

Queue queue; // создаем очередь

for i = 0 to n - 1 //

queue.pushback(v[i]) // добавляем в очередь все вершины графа

for k = 0 to n - 1 // пока не проделано нужное количество итераций

if !exist(queue.at(0), queue.at(1)) // проверяем существования ребра между первой и второй вершинами очереди

queue.swapSubQueue(2, find_vertex()) // если, не существует, то меняем порядок вершин в очереди, со второй до

// найденной, удовлетворяющей нас позиции

~~for i = 1 to n // перебираем все вершины перестановки <tex>P</tex>~~

~~if <tex> v_i v_{i+1} \notin \mathbb{E} </tex> // если нет ребра между <tex>v_i v_{i+1} </tex>~~

~~for <tex>v_j \in \mathbb{V} \setminus \{v_i, v_{i + 1}\}</tex> // перебираем все остальные вершины~~

~~if <tex>v_i v_j \in \mathbb{E}\</tex> && <tex> v_{i+1} v_{j+1} \in \mathbb{E}</tex> // если есть ребра <tex>v_i v_j,\ v_{i+1} v_{j+1} </tex>~~

~~reverse_subsequence(<tex>P, i+1, j</tex>) // разворачиваем часть перестановки <tex>P</tex> от i+1 позиции до j~~

~~break // переходим к следующей итерации внешнего for~~

|width = "310px" |

|}

71

правка