查找从一个节点到另一个节点的所有可能路径？
查找从一个节点到另一个节点的所有可能路径？
提问于 2014-10-06 04:03:24
我试图找到所有可能的路径，但我很难跟踪我访问过的路径。以下是到目前为止的代码：
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);
}
}
}回答 3
Stack Overflow用户
发布于 2014-10-06 04:16:46
您必须跟踪每个路由的访问路径，而不是全局路径。对于广度优先的方法，每个路由都需要一个访问路径列表。对于深度优先的方法，您可以保留已访问路径的列表，或者将其保留为全局路径，但在回溯时取消访问路径。
一旦您跟踪每条路由的路径，获取路径的长度和总权重将或多或少地自行完成。
使用您当前的算法，您可以将具有节点和访问路径列表的项排入队列：
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));Stack Overflow用户
发布于 2014-10-06 04:56:10
如果你走A-B-C-E，那么C将被标记为已访问，但由于C也是路径A-D-C-E的一部分，你将无法找到后者。因此，深度优先的方法似乎更合适，因为它允许您一次只处理一条路径。在完成路径之后，您可以清除Visited flag并继续另一条路径。我正在尝试用伪代码获取一个解决方案：
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);Stack Overflow用户
发布于 2014-10-06 04:48:51
如前所述，在每条边上维护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;
} 页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/26206682
复制相关文章
相似问题