我试图找到所有可能的路径,但我很难跟踪我访问过的路径。这是到目前为止的代码:
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));
关于c# - 找到从一个节点到另一个节点的所有可能路径?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26206682/