使用"深度优先搜索"查找到特定节点的唯一路由数

我有一个顶点为123456的有向图。使用深度优先搜索，如果我想从1-4(例如)中找到唯一路线的数量，我该怎么做？这是我目前的DFS。

private final Map<Character, Node> mNodes;
private final List<Edge> mEdges;
private List<Node> mVisited = new ArrayList<>();
int weight;
int numberOfPaths;
public DepthFirstSearch(Graph graph){
mNodes = graph.getNodes();
mEdges = new ArrayList<>(graph.getEdges());
for(Node node : mNodes.values()){
node.setVisited(false);
}
}
public void depthFirstSearch(Node source){
source.setVisited(true);
List<Edge> neighbours = source.getNeighbouringEdges(mEdges);
for(Edge edge : neighbours){
System.out.println(edge.getFrom().getName()+"-"+edge.getTo().getName());
if(!edge.getTo().isVisited()){
mVisited.add(edge.getTo());
weight += edge.getWeight();
depthFirstSearch(edge.getTo());
}
}
}

由于不允许循环，因此实际上有一个DAG(有向无环图)。

以下是与此主题相关的一些问题：

DAG中两个节点之间的路径数
拓扑排序法求到t的路径数

基本上，我们的想法是获得DAG的拓扑排序，然后从目标节点向后迭代到源节点，计算该节点的路径数。

由于数组没有循环，并且节点是拓扑排序的，因此当您访问一个节点时，可以从该节点访问的所有节点都显示在排序的后面，并且已经被访问过。因此，从一个节点到目标的路径数是与其相邻的节点数的总和

型号：

class Graph
{
private List<Node> nodes;
private List<Edge> edges;
public Graph() {
nodes = new ArrayList<>();
edges = new ArrayList<>();
}
public List<Node> getNodes() { return nodes; }    
public List<Edge> getEdges() { return edges; }
public void addNode(Node node) { nodes.add(node); }    
public void addEdge(Edge edge) {
edges.add(edge);        
edge.getFrom().addEdge(edge);
edge.getTo().addEdge(edge);
}
}
class Node
{
private List<Edge> outgoings, incomings;
public Node() {
outgoings = new ArrayList<>();
incomings = new ArrayList<>();
}
public List<Edge> getOutgoings() { return outgoings; }    
public List<Edge> getIncomings() { return incomings; }
public void addEdge(Edge edge) {
if (edge.getFrom() == this) outgoings.add(edge);
if (edge.getTo() == this) incomings.add(edge);
}
}
class Edge
{
private Node from, to;
public Edge(Node from, Node to) {
this.from = from;
this.to = to;
}
public Node getFrom() { return from; }    
public Node getTo() { return to; }
}

算法：

static int countPaths(Graph graph, Node source, Node target)
{
List<Node> nodes = topologicalSort(graph);
int[] counts = new int[nodes.size()];
int srcIndex = nodes.indexOf(source);
int tgtIndex = nodes.indexOf(target);
counts[tgtIndex] = 1;
for (int i = tgtIndex; i >= srcIndex; i--) {
for (Edge edge : nodes.get(i).getOutgoings())
counts[i] += counts[nodes.indexOf(edge.getTo())];
}
return counts[srcIndex];
}
static List<Node> topologicalSort(Graph g)
{
List<Node> result = new ArrayList<>();
Set<Node> visited = new HashSet<>();
Set<Node> expanded = new HashSet<>();
for (Node node: g.getNodes())
explore(node, g, result, visited, expanded);
return result;
}
static void explore(Node node, Graph g, List<Node> ordering, Set<Node> visited, Set<Node> expanded) {
if (visited.contains(node)) {            
if (expanded.contains(node)) return;
throw new IllegalArgumentException("Graph contains a cycle.");
}
visited.add(node);
for (Edge edge: node.getIncomings())
explore(edge.getFrom(), g, ordering, visited, expanded);
ordering.add(node);
expanded.add(node);
}

用法：

Graph g = new Graph();
Node a = new Node();
Node b = new Node();
Node c = new Node();
Node d = new Node();
Node e = new Node();
Edge ab = new Edge(a, b);
Edge bc = new Edge(b, c);
Edge cd = new Edge(c, d);
Edge ad = new Edge(a, d);
Edge ae = new Edge(a, e);
Edge ed = new Edge(e, d);
Edge be = new Edge(b, e);
Edge ec = new Edge(e, c);
g.addNode(a);
g.addNode(b);
g.addNode(c);
g.addNode(d);
g.addNode(e);
g.addEdge(ab);
g.addEdge(bc);
g.addEdge(cd);
g.addEdge(ad);
g.addEdge(ae);
g.addEdge(ed);
g.addEdge(be);
g.addEdge(ec);
int count = countPaths(g, a, d); 
//count: 6
// Paths:
//1. A->B->C->D
//2. A->D
//3. A->E->D
//4. A->B->E->C->D
//5. A->B->E->D
//6. A->E->C->D

但是，如果你想使用BFS，你可以尝试进行回溯重置访问的节点：

static int countPaths(Graph graph, Node source, Node target)
{
Set<Node> visiteds = new HashSet<>();
return BFS(source, target, visiteds);
}
static int BFS(Node current, Node target, Set<Node> visiteds) {
if (current == target) return 1;
else
{
int count = 0;
visiteds.add(current);
for (Edge edge : current.getOutgoings())
if (!visiteds.contains(edge.getTo()))
count += BFS(edge.getTo(), target, visiteds);
visiteds.remove(current);
return count;
}
}

然而，为了提高性能，您可以实现某种记忆：

static int countPaths(Graph graph, Node source, Node target)
{
Set<Node> visiteds = new HashSet<>();
Map<Node, Integer> memoize = new HashMap<>();
for (Node node : graph.getNodes())
memoize.put(node, -1);
memoize.put(target, 1);
return BFS(source, visiteds, memoize);
}
static int BFS(Node current, Set<Node> visiteds, Map<Node, Integer> memoize) {
if (memoize.get(current) != -1) return memoize.get(current);
else
{
int count = 0;
visiteds.add(current);
for (Edge edge : current.getOutgoings())
if (!visiteds.contains(edge.getTo()))
count += BFS(edge.getTo(), visiteds, memoize);
visiteds.remove(current);
memoize.put(current, count);
return count;
}
}

(假设有向无环图)

你所需要做的就是运行你的DFS，并计算每一个发现的通往目标节点的路由。

代码中的错误是setVisited()和isVisited()状态是全局的。这意味着，无论何时遇到节点C，都会将其标记为已访问，并且在整个DFS运行过程中都会保持标记状态，即使对于实际上尚未访问的路径也是如此。

DFS运行示例(给定简单图A -> B、B -> C、A -> C)：

(步骤1-路径A)访问A，标记A访问
(步骤1.1--路径A -> B)访问B，标记B访问
(步骤1.1.1——路径A -> B -> C)访问C，标记C访问
(步骤1.2——路径A -> C)此处跳过此路由，因为C从步骤1.1.1标记为已访问(这是错误的)

您需要通过以下方式正确跟踪访问的节点：

请相信调用者，输入图确实是非循环的，并且根本不跟踪访问的节点(因为在非循环图中不可能两次访问单个节点)。您的程序可能会因为错误的输入而进入无限递归
使用更简单/更便宜的循环检测。您可以跟踪递归的深度，当递归深度超过图中节点的总数时，会引发异常
访问后立即重置节点访问状态(这是@Arturo Menchaca在他的精彩回答中建议的)
为正在处理的每条路线保留一个单独的访问状态

在列表中跟踪访问节点的示例java代码(通过这种方式，您可以打印发现的路由)：

package test.java.so;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class So37503760 {
public static class Graph {
private final Map<Character, Node> nodes = new TreeMap<Character, Node>();
public Node addNode(char c) {
Node existingNode = nodes.get(c);
if(existingNode!=null) {
return existingNode;
}
Node newNode = new Node(c);
nodes.put(c, newNode);
return newNode;
}
public void addEdge(char f, char t) {
addNode(f).addChild(addNode(t));
}
public Node getNode(char name) {
Node ret = nodes.get(name);
if(ret==null) {
throw new RuntimeException("No such node " + name);
}
return ret;
}
}
public static class Node {
private final char name;
private final ArrayList<Node> children = new ArrayList<Node>();
public Node(char c) {
this.name=c;
}
public void addChild(Node childNode) {
children.add(childNode);
}
public ArrayList<Node> getChildren() {
return children;
}
public char getName() {
return name;
}
}
public static void main(String[] args) {
Graph graph = new Graph();
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'C');
graph.addEdge('C', 'D');
graph.addEdge('C', 'E');
graph.addEdge('D', 'E');
int numberOfPaths = depthFirstSearch(graph, 'A', 'E');
System.out.println("Found " + numberOfPaths + " paths");
}
public static int depthFirstSearch(Graph graph, char startNode, char destinationNode){
return depthFirstSearch(graph, graph.getNode(startNode), graph.getNode(destinationNode), new ArrayList<Node>());
}
public static int depthFirstSearch(Graph graph, Node startNode, Node destinationNode, List<Node> currentPath){
if(currentPath.contains(startNode)) {
currentPath.add(startNode);
throw new RuntimeException("Cycle detected: " + pathToString(currentPath));
}
currentPath.add(startNode);
try {
//          System.out.println("Progress: " + pathToString(currentPath));
if(startNode==destinationNode) {
System.out.println("Found path: " + pathToString(currentPath));
return 1;
}
int ret=0;
for(Node nextNode : startNode.getChildren()){
ret += depthFirstSearch(graph, nextNode, destinationNode, currentPath);
}
return ret;
} finally {
currentPath.remove(currentPath.size()-1);
}
}
private static String pathToString(List<Node> path) {
StringBuilder b = new StringBuilder();
boolean printArrow=false;
for(Node n : path) {
if(printArrow) {
b.append(" -> ");
}
b.append(n.getName());
printArrow=true;
}
return b.toString();
}
}

它实际上取决于图的边。如果你的所有顶点都相互连接，这将非常简单，因为你每次都会得到相同数量的路径(1->4，1->2->4，1->3->4，…，1->6->5->3->2->4(以1到4的路径为例)。给定任何n->m路径(给定你不想要循环的事实)，它看起来都非常相似，每次都会有相同数量的道路。然而，如果有任何顶点没有连接到其他顶点，那就会变得有趣。你可能想使用一个修改过的Djikstra算法，然后为你提供不同的答案(我猜你在寻找)，以获得许多独特的路径。

相关内容

最新更新

热门标签：