Найти все пути от начального узла до конечного узла в графе

Question

Вот мой вопрос.

Я пытаюсь решить эту проблему.

Учитывая начальную точку и конечную точку, найдите все пути от начала углу до конца. Включите только маршруты, которые не проходят через любой угол более одного раза.

Например: 1 - начальный узел, 6 - конечная точка. У меня есть данные как

1 2 
1 3 
3 4 
3 5 
4 6 
5 6 
2 3 
2 4 

Пар целых положительных чисел, разделенных связями, которые связаны. Таким образом, выход должен быть.

1 2 3 4 6 
1 2 3 5 6 
1 2 4 3 5 6 
1 2 4 6 
1 3 2 4 6 
1 3 4 6 
1 3 5 6 

Есть 7 маршрутов от 1 до 6.

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

Что я сделал, так это то, что я создал матрицу смежности графа, а затем выполнил первый поиск глубины.

Сначала я определил класс Node.

public class Node 
{ 
    public string NodeId; 
    public bool IsVisited; 
    public Node(string nodeId) 
    { 
     NodeId = nodeId; 
    } 
} 

Тогда Graph класс,

public class Graph 
{ 
    private Node[] _nodes; 
    private int[][] _adjacencyMatrix; 
    public int _numberOfTotalNodes; 
    public Graph(int[][] adjacencyMatrix, int numberOfTotalNodes) 
    { 
     _adjacencyMatrix = adjacencyMatrix; 
     _numberOfTotalNodes = numberOfTotalNodes; 
     _nodes = new Node[_numberOfTotalNodes]; 
     for (int i = 0; i < _numberOfTotalNodes; i++) 
     { 
      _nodes[i] = new Node((i + 1).ToString()); 
     } 
    } 

    public void DepthFirstSearch() 
    { 
     Stack s = new Stack(); 
     _nodes[0].IsVisited = true; 
     DisplayNodeId(0); 
     s.Push(0); 
     int v; 
     while (s.Count > 0) 
     { 
      v = GetAdjUnvisitedNode((int)s.Peek()); 
      if (v == -1 || _nodes[v].IsVisited) 
      { 
       s.Pop(); 
      } 
      else 
      { 
       _nodes[v].IsVisited = true; 
       DisplayNodeId(v); 
       s.Push(v); 
      } 
     } 
     for (int u = 0; u < _numberOfTotalNodes; u++) 
     { 
      _nodes[u].IsVisited = false; 
     } 
    } 

    public void DisplayNodeId(int nodePosition) 
    { 
     Console.Write(_nodes[nodePosition].NodeId + " "); 
    } 

    public int GetAdjUnvisitedNode(int v) 
    { 
     for (int j = 0; j < _numberOfTotalNodes; j++) 
     { 
      if (_adjacencyMatrix[v][j] == 1 && _nodes[j].IsVisited == false) 
      { 
       return j; 
      } 
     } 
     return -1; 
    } 
} 

Чтобы позвонить, просто используйте код.

var graph = new Graph(adjacenyMatrix, adjacenyMatrix.GetLength(0)); 
graph.DepthFirstSearch(); 

Просьба указать на недостатки моего алгоритма.

Основание на комментарии, есть solution там, я хотел бы код C#. Однако он не завершен. В нем отсутствует метод AdjacentNodes(T current).

Answer 1

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

Кроме того, я не вижу, как функция DFS возвращает что-либо. Он просто выводит узлы, когда они выбраны, но вы никогда не проверяете, достигли ли вы целевого узла.

Вы также должны изменить способ выбора новых узлов, если вы больше не используете флаг isVisited. Я рекомендую рекурсивное решение для вашей DFS. Напишите функцию, которая принимает текущий путь (Stack) в качестве параметра, затем определяет все соседние узлы, не являющиеся частью стека, и затем выполняет итерацию по ним, вызывая себя рекурсивно для каждого такого узла (с соответствующим узлом, добавленным в стек) ,