深さの最初の探索を使用してノードへの一意のルートの数を見つける

Question

私は、頂点ABCDEを持つ有向グラフを持っています。深みのある最初の検索を使用して、A-Cからのユニークなルートの数を見つけることができるようにしたい場合は、どうすればよいでしょうか？ここに私の現在の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である（すなわち、グラフにはサイクルが存在しない）、あなたはdynamic programmingを使用し、線形時間であなたの問題を解決することができます。

以下の些細なクレームは、グラフにvにuからのパスの数を特徴付ける：次にuからvへのパスの数がそれ以外の場合は1、uからvへのパスの数である

u=v場合wからvまでのパスの総数は、(u,w)がグラフのエッジになるようにします。

このクレームは、次の擬似コードによって与えられる単純な再帰アルゴリズムを意味しています。擬似コードは動的プログラミングを使用せず、素朴な再帰を使用することに注意してください。線形時間で問題を解決する必要がある場合は、memoizationを使用する必要があります。グラフは、パスの数は無限である可能性のサイクルが含まれている場合

public int countPaths(Graph graph, Node u, Node v) { 
    nodes = graph.getNodes(); 
    edges = new ArrayList<>(graph.getEdges()); 
    if (u.equals(v)) return 1; 
    int count = 0; 
    List<Edge> neighbours = u.getNeighbouringEdges(edges); 
    for(Edge edge : neighbours){ 
     w = edge.getTo(); 
     count += countPaths(graph, w, v); 
    } 
    return count; 
}