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

Цитата 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);
}