查找从一个节点到另一个节点的所有可能路径

本文关键字：节点 另一个 路径 有可能 一个 查找 | 更新日期: 2023-09-27 18:25:34

我试图找到所有可能的路径，但我很难跟踪我访问过的路径。这是迄今为止的代码：

public void FindAllPaths(Node startNode, Node endNode)
    {
        queue.Enqueue(startNode);
        while (queue.Count > 0)
        {
            var currentNode = queue.Dequeue();
            foreach (var edge in currentNode.Edges)
            {
                if (edge.Visisted)
                    continue;
                edge.Visisted = true;
                queue.Enqueue(edge.TargetNode);
            }
        }
    }

查找从一个节点到另一个节点的所有可能路径

您必须跟踪每条路线访问的路径，而不是全局访问。对于广度优先的方法，每条路线都需要一个访问路径列表。对于深度优先的方法，您可以保留已访问路径的列表，也可以将其保持为全局，但在回溯时不访问路径。

一旦你跟踪了每条路线的路径，获得路径的长度和总重量或多或少就会自行完成。

使用当前的算法，您可以将具有节点和访问路径列表的项目排入队列：

public void FindAllPaths(Node startNode, Node endNode) {
  queue.Enqueue(new QueueItem(startNode, new List<Edge>()));
  while (queue.Count > 0) {
    var currentItem = queue.Dequeue();
    foreach (var edge in currentItem.Node.Edges) {
      if (!currentItem.Visited.Contains(edge)) {
        List<Edge> visited = new List<Edge>(currentItem.Visited);
        visited.Add(edge);
        if (edge.TargetNode == endNode) {
          // visited.Count is the path length
          // visited.Sum(e => e.Weight) is the total weight
        } else {
          queue.Enqueue(new QueueItem(edge.TargetNode, visited));
        }
      }
    }
  }
}

QueueItem类只是：

public class QueueItem {
  public Node Node { get; private set; }
  public List<Edge> Visited { get; private set; }
  public QueueItem(Node node, List<Edge> visited) {
    Node = node;
    Visited = visited;
  }
}

我这样设置路径：

Node a = new Node("A");
Node b = new Node("B");
Node c = new Node("C");
Node d = new Node("D");
Node e = new Node("E");
a.Edges.Add(new Edge(5, b));
a.Edges.Add(new Edge(7, e));
a.Edges.Add(new Edge(5, d));
b.Edges.Add(new Edge(4, c));
c.Edges.Add(new Edge(2, e));
c.Edges.Add(new Edge(8, d));
d.Edges.Add(new Edge(8, c));
d.Edges.Add(new Edge(6, e));
e.Edges.Add(new Edge(3, b));

如果你去A-B-C-E，那么C将被标记为已访问，但由于C也是路径A-D-C-E的一部分，你以后将找不到。因此，深度优先的方法似乎更合适，因为它允许您一次在一条路径上工作。完成一个路径后，可以清除Visited标志，然后继续使用另一个路径。我正试图在伪代码中找到一个解决方案：

declare path as list of node;
procedure FindPath(node)
    for each edge in node.Edges
        if not edge.Visited then 
            edge.Visited = true
            path.Append(edge.TargetNode)
            if edge.TargetNode = goal then
                Print(path)
            else
                FindPath(edge.TargetNode)
            end
            path.Remove(edge.TargetNode)
            edge.Visited = false
        end
    end
end

其中，goal是示例中的节点E。您可以使用起始节点调用FindPath

FindPath(A);

如前所述，在每条边上维护Visited属性将不起作用，因为给定的边可能存在于多个不同的路径中。例如，对于A->D->E路径和A->B->C->D->E路径，都将遍历D/E边。

您需要维护添加到队列中的每个节点的当前路径：

IEnumerable<Path> FindAllPaths(Node from, Node to)
{
    Queue<Tuple<Node, List<Node>>> nodes = new Queue<Tuple<Node, List<Node>>>();
    nodes.Enqueue(new Tuple<Node, List<Node>>(from, new List<Node>()));
    List<Path> paths = new List<Path>();
    while(nodes.Any())
    {
        var current = nodes.Dequeue();
        Node currentNode = current.Item1;
        if (current.Item2.Contains(currentNode))
        {
            continue;
        }
        current.Item2.Add(currentNode);
        if (currentNode == to)
        {
            paths.Add(new Path(current.Item2));
            continue;
        }
        foreach(var edge in current.Item1.Edges)
        {
            nodes.Enqueue(new Tuple<Node, List<Node>>(edge.Target, new List<Node>(current.Item2)));
        }
    }
    return paths;
}
相关文章：