在图中查找从开始节点到结束节点的所有路径

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

从1到6有7条路线。

现在我使用图搜索算法，我只能找到一个。而且我也找不到指定最终目的地的那一个。我的意思是我只能遍历图。

我所做的是创建图的邻接矩阵，然后进行深度优先搜索。

首先，我定义了一个类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();

请指出我算法的缺陷。

根据评论，这里有一个解决方案，我想要C#代码。然而，它还没有完成。缺少CCD_ 3方法。

Answer 1

问题是，一旦触摸节点，就会将其标记为已访问，并且只在算法结束时取消设置标志。这意味着一个节点永远不会出现在不同的路径中，并且搜索很快就会结束。我建议您不要将此信息存储在节点本身中，而是检查节点是否已经是当前路径中节点堆栈的一部分。我认为这就是你想要做的：你想要防止一个节点在一个路径中出现两次（避免循环），而不是在搜索过程中一个节点只添加到任何路径一次。

此外，我看不出DFS函数是如何返回任何内容的。它只在节点被选中时输出节点，但从不检查是否到达目标节点。

如果不再使用isVisited标志，还必须更改选择新节点的方式。我为您的DFS推荐一个递归解决方案。编写一个以当前路径（Stack）为参数的函数，然后它确定不是堆栈一部分的所有相邻节点，然后通过递归地为每个这样的节点调用自己来迭代它们（将相应的节点添加到堆栈中）。