Пошук елементарних циклів у графі - програмування на c, c # і java

Розглянемо алгоритм пошуку всіх елементарних циклів у неорієнтованому графі. У цій статті буде наведено опис алгоритму і його реалізація на мові програмування C #.

Циклом в графі називається така кінцева ланцюг, яка починається і закінчується в одній вершині. Цикл позначається послідовністю вершин, які він містить, наприклад: (3-5-6-7-3).

До речі, про ланцюги, а саме про пошук елементарних ланцюгів в графі ми недавно писали.

Цикл називається елементарним. якщо всі вершини, що входять до нього, різні (за винятком початкової і кінцевої).

Давайте розглянемо приклад. Нехай дано такий граф:

Перерахуємо всі елементарні цикли в ньому: 2-3-4-2, 2-3-5-4-2, 3-2-4-3, 3-2-4-5-3, 3-4-5-3 , 4-3-2-4, 4-3-5-4, 4-2-3-5-4, 5-4-3-5, 5-4-2-3-5.

Припустимо граф задається, як G = (V, E). де V - безліч вершин графа, а E - безліч ребер цього графа. Вершини і ребра представимо об'єктами таких класів:

Розглянемо роботу алгоритму DFScycle. У початковий момент часу всі вершини графа пофарбовані в білий колір. Необхідно виконати наступне:

Перебираємо всі вершини, будь-яка з них може мати елементарний цикл. На кожній ітерації перефарбовувати все вершини в білий колір (позначимо його 1, а чорний колір будемо позначати 2). Додаємо в список вершин циклу cycle поточну вершину.

Тепер поговоримо про параметр unavailableEdge. Вершину, для якої шукаємо цикл, перефарбовувати в чорний колір не будемо, інакше програма не зможе в неї повернутися, оскільки ця вершина виявиться недоступною. Тому введемо змінну unavailableEdge, в яку будемо передавати номер останнього ребра, по якому здійснювався перехід між вершинами, відповідно це ребро на наступному кроці виявиться недоступним для переходу. Насправді це необхідно тільки на першому рівні рекурсії, щоб уникнути некоректної роботи алгоритму і виведення, наприклад, помилкового результату пошуку 1-2-1 при наявності такого графа:

Викличемо процедуру DFScycle (...).