C#算法搜索两个顶点之间的所有路径

Question

最近接到一个任务，要在 C# 中实现带权重的有向图。

我已经完成了 3/4，但我必须使用测试数据和基于该数据的 return 答案。

我有图表工作，我能够使用深度优先搜索添加 2 个节点之间的成本以及 return2 个节点之间的所有路径。

让我百思不得其解的是，其中一题如下：求从节点"C"到"C"的成本小于30的路由数

给出的示例答案是

CDC, 
CBEC, 
CEBCDC, 
CDEBC, 
CEBCEBC, 
CEBCEBCEBC  **7 in total**
These are the input graph details 
"A to B: 5",
"B to C: 4", 
"C to D: 8", 
"D to C: 8", 
"D to E: 6",
"A to D: 5" 
"C to E: 2", 
"E to B: 3", 
"A to E: 7"

我可以得到

CDC,
CEBC,
CDEBC

使用深度优先搜索，但我不知道其他 4 个来自哪里，也不知道为什么您会考虑一条您已经返回目标节点并继续前进的路线。

我是不是用错了算法？这是我正在尝试的：

public void depthSearch(GraphDeclare<string> graph, LinkedList<DirectedGraphNode<string>> Visited)
    {
        string endNode = "C";
        LinkedList<DirectedGraphNode<string>> nodes = getNeighboursAdjecentNodes(graph, Visited.Last());
        //examine the adjecent nodes
        foreach (DirectedGraphNode<string> node in nodes)
        {

            Boolean contains = Visited.Any(x => x.Value == node.Value);

            if (contains == true)
            {
                // Console.WriteLine("Hello");
                // printPath(Visited);
                continue;
            }
            if (node.Value == endNode)
            {
                Visited.AddLast(node);
                printPath(Visited);
                Visited.RemoveLast();
                break;
            }
        }

        foreach (DirectedGraphNode<string> node in nodes)
        {

            Boolean contain = Visited.Any(x => x.Value == node.Value);

            if (contain == true || node.Value == endNode)
            {
                continue;
            }
            Visited.AddLast(node);
            depthSearch(graph, Visited);
            Visited.RemoveLast();
        }

    }

    private void printPath(LinkedList<DirectedGraphNode<string>> visited)
    {
        StringBuilder cb = new StringBuilder();
        foreach (DirectedGraphNode<string> node in visited)
        {
            cb.AppendLine(node.Value + " ");

        }
        Console.WriteLine(cb.ToString());
    }


    private LinkedList<DirectedGraphNode<string>> getNeighboursAdjecentNodes(GraphDeclare<string> graph, DirectedGraphNode<string> n)
    {
        LinkedList<DirectedGraphNode<string>> neighbours = new LinkedList<DirectedGraphNode<string>>();

        foreach (DirectedGraphNode<string> edge in graph.nodeSet)
        {

            if (edge.Value.Equals(n.Value))
            {
                foreach (DirectedGraphNode<string> neighbour in edge.NeighbourNodes)
                {
                    neighbours.AddLast(neighbour);
                }

            }
        }

        return neighbours;
    }

Answer 1

您可以修改 DFS 以继续使用所有节点，即使它们已经被访问过，并且当总距离超过 30 时您应该停止算法。您还应该在每次到达 "C".

Answer 2

DFS算法获取两个节点之间所有路径的步骤：

维护访问过的节点列表，我是用访问过的节点列表
继续在路径中添加节点

在路径中找到结束节点后，将该路径添加到集合中，在代码中，它是在构建路径方法中完成的

        public List<List<RiverNode>> FindAllPathsBetweenTwoNodes(Node startNode, Node endNode, List<string> vistedNodes, List<Node> localpaths)
                {
                    try
                    {
                        //Mark Current Node As Visited
                        vistedNodes.Add(startNode.Name);
                        if (localpaths.Count == 0)
                        {
                            localpaths.Add(startNode);
                        }

                        if (startNode.Name.Equals(endNode.Name))
                        {
                            BuildPath(localpaths);
                        }

                        foreach (var node in startNode.GetNeighbours())
                        {
                            if (!vistedNodes.Contains(node.Name))
                            {
                                localpaths.Add(node);
                                FindAllPathsBetweenTwoNodes(node, endNode, vistedNodes, localpaths);
                                localpaths.Remove(node);
                            }
                        }
                        vistedNodes.Remove(startNode.Name);
                        return allPaths;
                    }
                    catch (Exception ex)
                    {
                        throw;
                    }
                }



                // <summary>
                /// Build Path
                /// </summary>
                /// <param name="localpath"></param>
                private void BuildPath(List<RiverNode> localpath)
                {
                    var localbuilPath = new List<RiverNode>();
                    foreach (var item in localpath)
                    {
                        localbuilPath.Add(item);
                    }
                    allPaths.Add(localbuilPath);
                }

C#算法搜索两个顶点之间的所有路径

C# algorithm search for all paths between two vertices

c#

algorithm

graph

nodes

depth-first-search