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

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

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); } } } 

Answer 1

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

一旦跟踪每条路线的路径，获取路径的长度和总重量将或多或少地自行完成。

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

 public void FindAllPaths(Node startNode, Node endNode) { queue.Enqueue(new QueueItem(startNode, new List())); while (queue.Count > 0) { var currentItem = queue.Dequeue(); foreach (var edge in currentItem.Node.Edges) { if (!currentItem.Visited.Contains(edge)) { List visited = new List(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 Visited { get; private set; } public QueueItem(Node node, List 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)); 

Answer 2

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

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

 IEnumerable FindAllPaths(Node from, Node to) { Queue>> nodes = new Queue>>(); nodes.Enqueue(new Tuple>(from, new List())); List paths = new List(); 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>(edge.Target, new List(current.Item2))); } } return paths; } 

Answer 3

如果你去ABCE那么C将被标记为已访问，但由于C也是路径ADCE的一部分，你将无法找到后者。 因此，深度优先方法似乎更合适，因为它允许您一次在一条路径上工作。 完成路径后，可以清除“访问”标志并继续使用其他路径。 我正在尝试使用伪代码来解决方案：

 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 您可以使用start节点调用FindPath

 FindPath(A);