Обход неориентированного невзвешенного графа

Всем хай! Сходу к делу!
Дан неориентированный граф, обладающий одной компонентой связности (т е из любой вершины можно попасть в любую другую без разрыва пути) (см.рис.). Дана стартовая вершина. В моем примере, это вершина №1.
Нужно осуществить Depth-first search, но не простой! Нужно получить все возможные варианты обхода.
На своем примере я насчитал 10 таких обходов. Красным цветом помечен "минимальный" обход, который я легко могу получить. Возникли проблемы с получением всех путей/обходов.
Какие вспомогательные структуры данных помогут в этом: ну, типа стек, очередь, дек, ЛОС и т.п.
Да, чуть не забыл, граф задается матрицей смежности, состоящей из 0 и 1. Петли в графе запрещены.

Можно пытаться рекурсивно "спускаться" по ребрам вглубь графа, добавляя новую вершину в какую-то структуру, когда кол-во элементов, например, в стеке равно кол-ву вершин, то принтить на экран текущий обход, но потом нужно "прыгнуть" на какой-то уровень рекурсии и формировать новый обход. Но тут возникли проблемы разного рода, которые быстро побороть не получилось.

Как же получить все возможные обходы в глубину?

Прикреплённая картинка

Прикреплённая картинка

Не совсем понятен критерий отбора путей. Если нужны все возможные обходы в глубину с разным порядком посещения вершин, то должны быть еще два варианта: 1532746 и 1562743 (вообще, хвост 274 ни на что не влияет, его можно обрубить до 2). Какова точная формулировка?

Цитата AVA12 @ 11.11.17, 21:00

1532746 и 1562743

почему 1532746??!
Идем из 1 в 5, потом из 5 в 3 и продолжаем идти ВГЛУБЬ, если есть такая возможность, т е из 3 в 6, а вот ПОТОМ уже во 2-ю!
Ведь так ДФС работает или я чего-то недогоняю....

Что-то я не понимаю, с чем возникли сложности... используйте стандартный алгоритм обхода в глубину, просто на каждом шаге перед выбором дополнительно избавляйтесь от рёбер, ведущих от текущего узла к уже посещённым. На алгоритм это никак не повлияет. Единственное - это сильно усложнит алгоритм, если использовать нерекурсивную версию, а в случае рекурсивной потребует передачи вниз по рекурсии копии очищенного графа и сохранения на текущем уровне неочищеной копии, если есть хотя бы одно удаляемое ребро.

Сообщение отредактировано: Akina - 11.11.17, 21:10

Цитата Akina @ 11.11.17, 21:08

ведущих от текущего узла к уже посещённым

это понятно. Можно завести статус у вершины посещена/непосещена или добавлять посещенные вершины в стек/очередь и проверять "новую" вершину входит в стек/очередь или смотреть статус - тут вроде понятно!

Цитата Akina @ 11.11.17, 21:08

использовать нерекурсивную версию

солидарен, т к без рекурсии будет тяжко...очень имхо, поэтому рассматриваем ТОЛЬКО рекурсивный вариант

Цитата Akina @ 11.11.17, 21:08

потребует передачи вниз по рекурсии копии очищенного графа и сохранения на текущем уровне неочищеной копии, если есть хотя бы одно удаляемое ребро

тут пока не все ясно, буду разбираться и, я правильно понимаю, что если будет БОЛЬШЕ 1-й компоненты связности, то такой принцип не сработает? я просто пока разбираю на 1-й компоненте связности, а потом хотелось бы чтобы работало на любом кол-ве компонент связности...

Цитата AVA12 @ 11.11.17, 21:00

вообще, хвост 274 ни на что не влияет, его можно обрубить до 2

ну, это только в этом примере такая топология

Цитата FasterHarder @ 11.11.17, 21:25

я правильно понимаю, что если будет БОЛЬШЕ 1-й компоненты связности, то такой принцип не сработает?

С чего бы? Он универсален, т.к. определяется задачей.

Akina я правильно понимаю, что окончание рекурсии будет момент, когда у стартовой вершины будут удалены все ребра, т е не будет возможности куда либо пойти?

Есссно. На этот критерий модификация не влияет. Только не удалены, а обойдены.

Сообщение отредактировано: Akina - 11.11.17, 21:31

Цитата Akina @ 11.11.17, 21:08

это сильно усложнит алгоритм, если использовать нерекурсивную версию

Проще не избавляться от рёбер, а помечать посещённые вершины (каждое добавленное ребро добавляет также вершину, в которую оно пройдено) и пропускать рёбра, повторно ведущие в них. Тогда нерекурсивный алгоритм становится даже проще рекурсивного (по крайней мере требует меньше памяти).

От классической задачи обхода в глубину задача отличается тем, что приходится сохранять рёбра, по которым мы возвращаемся, чтобы продолжить поиск в другом направлении. При обычном обходе в глубину они забываются сразу.

Цитата Akina @ 11.11.17, 21:08

каждом шаге перед выбором дополнительно избавляйтесь от рёбер

т е ты говорил, что ребро не удаляется, а помечается как обойденное. Это нужно делать через матрицу смежности, да?
В нужной ячейке матрицы смежности менять 1 на 0?

Цитата Akina @ 11.11.17, 21:08

случае рекурсивной потребует передачи вниз по рекурсии копии очищенного графа и сохранения на текущем уровне неочищеной копии, если есть хотя бы одно удаляемое ребро.

хотел еще вот этот вариант обсудить
т е ввели стартовую вершину и вызываем рекурсивную функцию Получить_Все_ДФС.
Какие параметры она будет иметь?
1) матрица смежности для неочищенной копии
2) матрица смежности для очищенного графа
3) номер вершины, от которой происходит движение "вглубь" графа
---------------------------------------------------------
т е всего три параметра, причем все они передаются НЕ по ссылке, а по значению, чтобы на каждом уровне рекурсии сохранялось состояние своей копии матрицы смежности (кстати в С, С++ массивы только передаются по ссылке и приходится их оборачивать в структуру, что добиться передачи по значению)? Точно не потребуется иметь стек/очередь какую-нибудь для запоминания чего-либо)

Цитата amk @ 12.11.17, 06:17

т классической задачи обхода в глубину задача отличается тем, что приходится сохранять рёбра, по которым мы возвращаемся, чтобы продолжить поиск в другом направлении. При обычном обходе в глубину они забываются сразу.

да, amk, ты очень точно диагностировал проблему, которая возникла, т к рекурсия при обходе ДФС имеет разрывы (прыгает с уровня на уровень), в отличие, например, от какого-нибудь дерева, где можно спускаться последовательно, начиная от корня...

Сообщение отредактировано: FasterHarder - 12.11.17, 09:35

Цитата FasterHarder @ 12.11.17, 09:30

причем все они передаются НЕ по ссылке, а по значению, чтобы на каждом уровне рекурсии сохранялось состояние своей копии матрицы смежности

Именно. Ну то есть для экономии памяти можно делать это только когда было чего удалять, но нужность этого действа зависит от диаметра графа. Кстати, а какой он типичный? десятки, сотни, тысячи?

Цитата Akina @ 12.11.17, 09:40

Именно. Ну то есть для экономии памяти можно делать это только когда было чего удалять, но нужность этого действа зависит от диаметра графа. Кстати, а какой он типичный? десятки, сотни, тысячи?

вообще проблемы с памятью как бы нет, т е при решении этой задачки на это вообще можно НЕ обращать внимания.
рассматриваются не big graph, а графы с максимальным кол-вом вершин 10 штук. Но при этом могут быть связные графы (каждая вершина связана с каждой другой)
наверное, можно как-то используя комбинаторику посчитать максимально возможное кол-во обходов ДФС на связном графе с 10-ю вершинами, хотя я не знаю точно, как это сделать, может K = (n - 1)!/2, n = 10
но на память повторю, внимание можно не обращать как бы...

P.S. мне представляется большей проблемой, когда у графа будет больше 1-й компоненты связности...хотя тоже не уверен

Добавлено 12.11.17, 09:50
Akina, что насчет описанных параметров?
я попробую написать псевдокод и показать, т к на данный момент многое непонятно остается и не вывезу решение дальше сам...

Цитата FasterHarder @ 12.11.17, 09:49

что насчет описанных параметров?

Перебор у тебя насчёт параметров. Передавать надо только текущее состояние графа и текущую вершину. Всё. Более того, граф можно хранить глобально, а передавать текущий полный путь - думаю, на каждом шаге на основе текущего пути строить список посещённых узлов будет не дороже, чем передавать его в готовом виде.

Цитата Akina @ 12.11.17, 10:32

граф можно хранить глобально

так, т е есть матрица смежности глобальной области видимости, поэтому толкать ее в ф-цию нет необходимости. Тут понятно.

Цитата Akina @ 12.11.17, 10:32

передавать текущий полный путь

вот тут не все ясно! для этого пути потребуется какая-то структура данных. Наверное, это будет очередь, которая запоминает номера вершин при обходе текущего ДФС. Я прав?

во-первых, как понять, что текущий ДФС сформирован и его пора выводить на экран? Кол-во элементов очереди должно стать равно кол-ву вершин исходного графа? Если да, то это понятно, как сделать и так я даже пытался уже делать, но не мог вернуться на нужный уровень рекурсии.

во-вторых, когда очередь распечатана, то нужно вернуться на развилочную вершину, чтобы пойти по-другому пути ДФС, но как ее найти, ведь она не последняя в очереди, как правило, а может быть где-то в середине, и пока до нее доберешься, то все промежуточные копии рекурсии будут закрыты/забыты (об этом коротко упомянул amk)

В общем это, я пока не догоняю основную идею такого перебора, хотя сам принцип построения ДФС вроде понимаю нормально...

Цитата FasterHarder @ 12.11.17, 11:03

для этого пути потребуется какая-то структура данных.

Какая структура? зачем? или массив посещённых вершин, или вообще UNC в стрингах.

Цитата FasterHarder @ 12.11.17, 11:03

как понять, что текущий ДФС сформирован и его пора выводить на экран?

Да элементарно - количество узлов в пути равно количеству узлов графа.

Цитата FasterHarder @ 12.11.17, 11:03

когда очередь распечатана, то нужно вернуться на развилочную вершину, чтобы пойти по-другому пути ДФС, но как ее найти

Да просто возврат из рекурсии. А там на каждом уровне уже организован for each по доступным вершинам, он сам разберётся, обрабатывать следующую вершину, или они кончились, и надо возвращаться.
Т.е.

SUB recurse(currentpath, currentpoint)
IF LENGTH(currentpath) = COUNT(points) THEN
    PRINT currentpath
ELSE
    FOR EACH point IN (достижимые из currentpoint вершины, отсутствующие в currentpath)
        CALL recurse(currentpath + point, point)
    NEXT
END IF
END SUB

Сообщение отредактировано: Akina - 12.11.17, 11:13

Цитата Akina @ 12.11.17, 11:09

Т.е.

этот код мне понятен и закодировал его на C# (скажу больше, у меня было нечто подобное, только для хранения пути использовал очередь)

namespace ConsoleApplication1
{
    class Program
    {
        public const int N = 7;     // количество вершин в исходном графе
        public static int[,] ms = new int[N, N]     // матрица смежности графа
                                        {
                                            {0, 0, 1, 0, 1, 1, 0},
                                            {0, 0, 0, 0, 1, 0, 1},
                                            {1, 0, 0, 0, 1, 1, 0},
                                            {0, 0, 0, 0, 0, 0, 1},
                                            {1, 1, 1, 0, 0, 1, 0},
                                            {1, 0, 1, 0, 1, 0, 0},
                                            {0, 1, 0, 1, 0, 0, 0}
                                        };
        public static void AllDFS(int current, ref string path) // получение всех ДФС рекурсивно
        {
            if (path.Length == N)   // если текущий путь ДФС готов, то выводим его
                Console.WriteLine(path);
            else
            {
                for(int j = 0; j < N; j++)  // просматриваем всех соседей текущей вершины
                    if (ms[current - 1, j] == 1)    // сосед обнаружен
                    {
                        char ch = (char)(j + 1 + 48);   // перевод номер вершины в символ, чтобы засунуть в строковый путь ДФС
                        if (path.Contains(ch) == false) // если эта смежная вершина еще не попала в путь, то
                        {
                            path += (j + 1).ToString(); // добавляем ее к пути
                            AllDFS(j + 1, ref path);    // рекурсивный вызов, но в качестве текущей вершины уже выступает сосед
                        }
                    }
            }
        }
 
        static void Main(string[] args)
        {
            int start = 1;  // исходная вершина для получения всех ДФС
            string path = null; // отвечает за путь ДФС
            path += start.ToString();  
            AllDFS(start, ref path);    // получение всех возможныхх ДФС
            Console.ReadKey();
        }
    }
}

Akina, а вот сейчас у меня к тебе огромный вопрос, т к именно в этом моменте возникает главная проблема!

Цитата Akina @ 12.11.17, 11:09

SUB recurse(currentpath, currentpoint)

тут у тебя псевдокод на бэйсике и непонятно, как передается currentpath по ссылке или по значению!
Вот смотри, допустим, если передача ПО ЗНАЧЕНИЮ, тогда будем иметь состояние этого пути в каждой версии рекурсии:
0 уровень: 1
1 уровень: 13
2 уровень: 135
3 уровень: 1352
4 уровень: 13527
5 уровень: 135274 и идти от вершины №4 некуда, поэтому эта версия рекурсии закроется и вернемся на 4-й уровень рекурсии и вершина №4 потеряна из пути. Затем закроется 4 уровень - потеряется 7 вершина и т.д.
Т е передавать по значению этот путь НЕЛЬЗЯ, верно?

Допустим, передача по ССЫЛКЕ, тогда получим:
0 уровень: 1
1 уровень: 13
2 уровень: 135
3 уровень: 1352
4 уровень: 13527
5 уровень: 135274 и идти от вершины №4 некуда, поэтому эта версия рекурсии закроется и вернемся на 4-й уровень рекурсии. Поскольку передача была по ссылке, то на уровне №4 currentpath = 135274. В конце концов добавится последняя вершина под №6 и первый правильный путь ДФС будет выведен на экран!
Но возникла дикая проблема, т к путь нужно очищать (перестраивать хвост пути), а к этому моменту рекурсивные версии закрылись и на них не выйти повторно и непонятно, что делать.

Вот именно эта проблема возникла у меня изначально, именно из-за нее создал этот пост.

Или я не прав фундаментально здесь?

Цитата FasterHarder @ 12.11.17, 13:52

тут у тебя псевдокод на бэйсике и непонятно, как передается currentpath по ссылке или по значению!

Конечно, по значению. Иначе некуда будет возвращаться - для каждого уровня рекурсии должна существовать своя переменная path со своим значением...

Цитата Akina @ 12.11.17, 13:55

Конечно, по значению. Иначе некуда будет возвращаться - для каждого уровня рекурсии должна существовать своя переменная path со своим значением...

я же описал проблему, которая возникает в этом случае

Цитата FasterHarder @ 12.11.17, 13:52

Вот смотри, допустим, если передача ПО ЗНАЧЕНИЮ, тогда будем иметь состояние этого пути в каждой версии рекурсии:
0 уровень: 1
1 уровень: 13
2 уровень: 135
3 уровень: 1352
4 уровень: 13527
5 уровень: 135274 и идти от вершины №4 некуда, поэтому эта версия рекурсии закроется и вернемся на 4-й уровень рекурсии и вершина №4 потеряна из пути. Затем закроется 4 уровень - потеряется 7 вершина и т.д.
Т е передавать по значению этот путь НЕЛЬЗЯ, верно?

и тогда НЕВОЗМОЖНО построить путь, если вершины нельзя в процессе ДФС соединить последовательно

поясни, плиз этот момент, т к это узкое горлышко моего понимания всей задачи!

На самом деле, как я уже писал, можно обойтись без копирования графа. Для этого надо вести "журнал" перемещений по графу, в который записывать изменения в нём. Так же не надо выбрасывать из него рёбра, достаточно иметь список входящих в текущее дерево вершин.

На шаге "поиска в глубину" в журнал пишется текущая вершина, ребро, по которому делается переход, вершина в которую произведён переход.
Вершина, в которой мы оказались в результате перехода отмечается, как находящаяся в дереве.
Если из текущей вершины нельзя сделать переход в ещё не отмеченную вершину, то производится возврат по переходам до вершины, из которой такой переход сделать можно.
Если в результате возврата, мы оказались в исходной вершине и не смогли сделать переход, значит построение очередного дерева завершено - можно выписать номера рёбер.

Далее начинается чистка журнала, операции журнала последовательно (с последней) отменяются, с вершин, помеченных на соответствующем шаге снимается пометка, и делается попытка сделать шаг по другому ребру. Если такой шаг сделать не удаётся чистится следующая запись и т.д. Как только сделать другой шаг удаётся, это будет новый вариант поиска в глубину.

Если при чиске мы доходим до начальной записи и не можем сделать альтернативный шаг, значит больше обходов не существует.

Цитата FasterHarder @ 12.11.17, 13:52

будем иметь состояние этого пути в каждой версии рекурсии

Ты забываешь, что на каждом уровне рекурсии организуется перебор достижимых вершин:

Цитата FasterHarder @ 12.11.17, 13:52

0 уровень: 1
1 уровень: 13
2 уровень: 135
3 уровень: 1352
4 уровень: 13527
5 уровень: 135274

А на самом деле так:
0 уровень: 1, текущая 1, достижимые вершины 3,5,6
1 уровень: 1/13, текущая 3, достижимые вершины 1 (посещена),5,6
2 уровень: 1/13/35, текущая 5, достижимые вершины 1 (посещена), 2, 3 (посещена),6
3 уровень: 1/13/35/52, текущая 2, достижимые вершины 5 (посещена), 7
4 уровень: 1/13/35/52/27, текущая 7, достижимые вершины 2 (посещена), 4
5 уровень: 1/13/35/52/27/74 текущая 4, достижимые вершины 7 (посещена), достижимых непосещённых нет, возврат и поиск непосещённой вершины
6 уровень: 1/13/35/52/27/74, текущая 7, достижимые вершины 2 (посещена), 4 (посещена), достижимых непосещённых нет, возврат и поиск непосещённой вершины
6 уровень: 1/13/35/52/27/74, текущая 2, достижимые вершины 5 (посещена), 7 (посещена), достижимых непосещённых нет, возврат и поиск непосещённой вершины
6 уровень: 1/13/35/52/27/74, текущая 5, достижимые вершины 1 (посещена), 2 (посещена), 3 (посещена), 6
6 уровень: 1/13/35/52/27/74/56, текущая 6, длина пути == количество вершин == 7, печать пути
...
2 уровень: 1/13/35, текущая 5, достижимые вершины 1 (посещена), 2 (посещена), 3 (посещена),6
...

Mwa-ha-ha. Я почти сломал мозг, но, похоже, нашел решение (во всяком случае, граф из первого сообщения обрабатывается правильно). Причем без рекурсии (если не учитывать имитацию в виде стека).

Для хранения текущего состояния используется (помимо сгенерированного пути) стек точек ветвления и флаг "есть решение". Элемент стека содержит длину сгенерированного пути, позицию точки ветвления в этом пути и номер последней выбранной смежной вершины.

1. При заходе в вершину проверяем, все ли вершины уже посещены. Если да, то выставляем флаг "есть решение", выводим путь, восстанавливаем из стека точку ветвления.

2. Ищем смежные вершины, отсутствующие в пути и еще не выбранные. Если такие вершины есть, то обходим их по порядку: сбрасываем флаг "есть решение", кладем в стек текущую точку ветвления, добавляем выбранную вершину к пути и заходим в нее.

3. Если идти (больше) некуда, то:
а) если стек пуст, то мы нашли все возможные пути, завершаем работу;
б) если флаг "есть решение" сброшен (остались непосещенные вершины), то возвращаемся в предыдущую вершину пути, сам сгенерированный путь при этом не меняется;
в) если флаг "есть решение" выставлен, то восстанавливаем из стека точку ветвления.

В виде кода будет примерно так:

<html>
<body>
<script>
 
var vertices = 7
var firstVertex = 1
var incidence = {
  1: {3: 1, 5: 1, 6: 1},
  2: {5: 1, 7: 1},
  3: {1: 1, 5: 1, 6: 1},
  4: {7: 1},
  5: {1: 1, 2: 1, 3: 1, 6: 1},
  6: {1: 1, 3: 1, 5: 1},
  7: {2: 1, 4: 1}
}
 
function walk(vertices, incidence, firstVertex) {
  var inPath = new Array(vertices)
  inPath[firstVertex] = true
  var path = [firstVertex]
  var stack = [] // [{pathLen, forkPos, takenVertex}]
  var forkPos = 0
  var takenVertex = 0
  var gotSolution = false
 
  var pushStack = function () {
    stack.push({pathLen: path.length, forkPos: forkPos, takenVertex: takenVertex})
    forkPos = path.length
    path.push(takenVertex)
    inPath[takenVertex] = true
    takenVertex = 0
  }
 
  var popStack = function () {
    var item = stack.pop()
    takenVertex = item.takenVertex + 1
    forkPos = item.forkPos
    while (path.length > item.pathLen) {
      var i = path.pop()
      inPath[i] = false
    }
  }
 
  while (true) {
    if (path.length >= vertices) {
      gotSolution = true
      document.writeln(path.join() + '<br>')
      popStack()
      continue
    }
 
    var neighbours = incidence[path[forkPos]]
    while ((!neighbours[takenVertex] || inPath[takenVertex]) && takenVertex <= vertices) {
      takenVertex++
    }
 
    if (takenVertex <= vertices) {
      pushStack()
      gotSolution = false
      continue
    }
 
    if (!stack.length) return
 
    if (gotSolution) {
      popStack()
    } else {
      forkPos--
      takenVertex = 1
    }
  }
}
 
walk(vertices, incidence, firstVertex)
 
</script>
</body>
</html>

Цитата Akina @ 12.11.17, 18:39

4 уровень: 1/13/35/52/27, текущая 7, достижимые вершины 2 (посещена), 4
5 уровень: 1/13/35/52/27/74 текущая 4, достижимые вершины 7 (посещена), достижимых непосещённых нет, возврат и поиск непосещённой вершины

вот, давай посмотрим на уровень №5, активная вершина №4 и идти от нее НЕКУДА и происходит ВОЗВРАТ, т е мы должны перейти на уровень №4, а не уровень №6 (ведь рекурсия начинает обратное движение, схлапывание). А чему равно значение path на уровне №4? Правильно, вот оно:

Цитата Akina @ 12.11.17, 18:39

4 уровень: 1/13/35/52/27

и ЧЕТВЕРКА ведь теряется! И до нее уже НЕ добраться в текущем обходе ДФС.

или я не прав абсолютно?

Добавлено 12.11.17, 19:53
я даже в отладчике посидел и там четко видно, что при обратном ходе path теряет хвост, что вообще не позволяет добиться состояние формирования полного ДФС, когда есть разрыв рекурсионный при обходе...

Сообщение отредактировано: FasterHarder - 12.11.17, 19:53

Цитата FasterHarder @ 12.11.17, 19:51

при обратном ходе path теряет хвост, что вообще не позволяет добиться состояние формирования полного ДФС, когда есть разрыв рекурсионный при обходе...

У тебя формируется разрывный путь. Поэтому на каждом витке рекурсии тебе надо рассматривать все непосещённые вершины, доступные из хотя бы одной из посещённых, а не просто все доступные из текущей. И соответственно то, что кончились узлы, доступные из текущей вершины, ещё не повод завершить уровень рекурсии.

Akina, я, кажется понял и немного доделал программку и уже печатает частично правильно, НО, есть уточнения:
1. когда ты ссылаешься на текущую вершину, ведь она имеет статус посещенной? Как я понимаю, да
2. А зачем вообще передавать в рекурсию текущую вершину, если она записывается В КОНЕЦ пути. Ведь, если требуется перебрать всех непосещенных соседей для посещенных вершин, то ведь достаточно просмотреть все вершины от конца к началу, которые хранятся в пути и автоматически будет обработана и текущая, которая стоит в конце пути

псевдокод:

void Все_ДФС(string path)
{
   если длина path равна кол-ву вершин графа, то
       вывести путь
   иначе
       просмотреть все вершины в переменной path от конца к началу
           просмотреть всех возможных непосещенных соседей текущей вершины
               если сосед не входит в путь, то
               {
                   добавить соседа в конец пути
                   вызов Все_ДФС(path)
               }
}

уже почти все понятно и почти все работает...ключевое слово почти...

Добавлено 13.11.17, 09:14
и, кстати, дубликатные пути распечатываются иногда, но это так, к слову...

Цитата FasterHarder @ 13.11.17, 09:11

А зачем вообще передавать в рекурсию текущую вершину, если она записывается В КОНЕЦ пути.

Ну не передавай.

Цитата FasterHarder @ 13.11.17, 09:11

дубликатные пути распечатываются иногда

Трассировка в помощь.

Цитата FasterHarder @ 11.11.17, 20:17

Нужно получить все возможные варианты обхода.

Как-то подобный вопрос уже поднимался, и я его решал. Код остался.
Вот программка, которая печатает все пути в графе.
Посмотри, возможно что-то из нее пригодится:

#include <iostream>
#include <vector>
#include <map>
 
typedef std::vector<uint> PathType;
typedef std::map<uint,bool> VisType;
typedef std::map<uint,std::vector<uint>> RelType;
 
void PrintPath(uint I, PathType P, VisType V, RelType &R) {
  if (V.find(I) != V.end()) return;
  P.push_back(I); V[I]=true;
  for(const auto& x: P) std::cout << ":" << x; std::cout << std::endl;
  for(const auto& i: R[I]) PrintPath(i,P,V,R);
}
 
int main() {
  VisType Vis;
  PathType Path;
  RelType Rel = {
    {0,{1,5,6}},
    {1,{0,2,6}},
    {2,{1,3,6}},
    {3,{2,4,6}},
    {4,{3,5,6}},
    {5,{0,4,6}},
    {6,{0,1,2,3,4,5}}
  };
  for(auto const& i:Rel) PrintPath(i.first,Path,Vis,Rel);
}