Unique Path Graph I

Description:

Find number of total unique paths from Source to Goal.

Example:

/*
   1 ------> 4
 /  \         \
0 -> 2 -> 5 -> 6 -> 7 -> 8
 \            /
  3--------->
*/

Idea:

Directed graph, 三种方法都可以。 Backtrack有些慢，DP的方法很有效。拓展的时候，可以用parent count来记录这个node可不可以往下走。

Code:

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <utility>
#include <memory>
#include <cmath>

using namespace std;

// A structure to represent a node in adjacency list
struct AdjEdge{
    AdjEdge(int d): dest(d), next(nullptr) {}
    int dest;
    AdjEdge * next;
};

struct AdjVert{
    AdjVert(): p_count(0), next(nullptr) {}
    int p_count;
    AdjEdge * next;
};

// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
class Graph{
public:
    Graph() = delete;
    Graph(int n): V(n), edges(n) {}

    void addEdge(int src, int dest){
        // src to dest Edge
        AdjEdge * ptr = new AdjEdge(dest);
        ptr->next=edges[src].next;
        edges[src].next=ptr;
        edges[dest].p_count++;
    }    

    const int V;
    vector<AdjVert> edges;
};


// Method 1, Backtrack

void DFS(const Graph & graph, int curr, int goal, int & count){
    if(curr==goal){
        count++;
        return;
    }

    for(AdjEdge * ptr=graph.edges[curr].next; ptr!=nullptr; ptr=ptr->next){
        DFS(graph, ptr->dest, goal, count);
    }
}

int uniquePath(const Graph & graph, int src, int goal){
    int count=0;
    DFS(graph, src, goal, count);
    return count;
}


// Method 2, DP recursion

struct VertNode{
    VertNode():p_count(0), count(0) {}
    int p_count;
    int count;
};

void searchDP(const Graph & graph, vector<VertNode>& v_node, int curr, int goal){
    if(curr==goal) return;

    for(AdjEdge * ptr=graph.edges[curr].next; ptr!=nullptr; ptr=ptr->next){
        v_node[ptr->dest].count += v_node[curr].count;
        v_node[ptr->dest].p_count--;
        if(v_node[ptr->dest].p_count==0){
            searchDP(graph, v_node, ptr->dest, goal);
        }
    }

}

int uniquePathDP(const Graph & graph, int src, int goal){

    vector<VertNode> v_node(graph.V);

    for(int i=0; i<graph.V; ++i){
        v_node[i].p_count=graph.edges[i].p_count;
    }

    v_node[src].count=1;

    searchDP(graph, v_node, src, goal);

    return v_node[goal].count;
}

// Method 3, DP iteration 
int uniquePathDPIter(const Graph & graph, int src, int goal){

    vector<VertNode> v_node(graph.V);

    for(int i=0; i<graph.V; ++i){
        v_node[i].p_count=graph.edges[i].p_count;
    }

    v_node[src].count=1;

    stack<int> v_stack;

    v_stack.push(src);

    while(!v_stack.empty()){
        int curr=v_stack.top();
        v_stack.pop();

        if(curr==goal)
            return v_node[curr].count;

        for(AdjEdge * ptr=graph.edges[curr].next; ptr!=nullptr; ptr=ptr->next){
            v_node[ptr->dest].count += v_node[curr].count;
            v_node[ptr->dest].p_count--;
            if(v_node[ptr->dest].p_count==0){
                v_stack.push(ptr->dest);
            }
        }

    }

    return 0;
}
/*
   1 ------> 4
 /  \         \
0 -> 2 -> 5 -> 6 -> 7 -> 8
 \            /
  3--------->
*/

int main(){
    // create the graph given in above fugure
    int V = 9;
    // struct Graph* graph = createGraph(V);
    Graph graph(V);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(0, 3);
    graph.addEdge(1, 2);
    graph.addEdge(1, 4);
    graph.addEdge(2, 5);
    graph.addEdge(3, 6);
    graph.addEdge(4, 6);
    graph.addEdge(5, 6);
    graph.addEdge(6, 7);
    graph.addEdge(7, 8);

    int src=0;
    int goal=8;
    cout<<uniquePath(graph, src, goal)<<endl;
    cout<<uniquePathDP(graph, src, goal)<<endl;
    cout<<uniquePathDPIter(graph, src, goal)<<endl;
}