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

Question

我有一个顶点为 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());

        }
    }

}

Answer 1

由于不允许循环，您实际上有一个DAG ( directed acyclid graph )。

这些是与此主题相关的一些问题:

• Number of paths between two nodes in a DAG
• Topological sort to find the number of paths to t

基本上，这个想法是得到一个 topological sort 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;
    }
}    

但是，为了提高性能，您可以实现某种 memoization :

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