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

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(定向acyclid图).

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

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