Unique Path Graph II

Description:

Find number of total unique paths from Source to Goal.

Example:

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

Idea:

Undirected graph, 目前只有一种方法可以。 Backtrack有些慢，可以用。

DP的方法用在undirected graph上不行，因为不知道哪些是parent 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++;
        // Un-directed graph, set dest to src Edge too
        AdjEdge * ptr_rev = new AdjEdge(src);
        ptr_rev->next=edges[dest].next;
        edges[dest].next=ptr_rev;
        edges[src].p_count++;
    }   

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

// Method 1, Backtrack

void DFS(const Graph & graph, int curr, int goal, int & count, vector<bool>& vistied){
    // cout<<curr<<endl;
    if(curr==goal){
        count++;
        return;
    }

    vistied[curr]=true;

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

    vistied[curr]=false;
}

int uniquePath(const Graph & graph, int src, int goal){
    int count=0;
    vector<bool> vistied(graph.V, false);
    DFS(graph, src, goal, count, vistied);
    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, vector<bool>& vistied){
    // cout<<"->"<<curr<<endl;
    if(curr==goal) return;
    vistied[curr]=true;

    for(AdjEdge * ptr=graph.edges[curr].next; ptr!=nullptr; ptr=ptr->next){
        if(!vistied[ptr->dest]){
            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, vistied);
            // }
        }
    }

}

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;
    vector<bool> vistied(graph.V, false);

    searchDP(graph, v_node, src, goal, vistied);

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

    vector<bool> vistied(graph.V, false);

    v_node[src].count=1;

    queue<int> v_queue;

    v_queue.push(src);

    while(!v_queue.empty()){
        int curr=v_queue.front();
        v_queue.pop();
        vistied[curr]=true;

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

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

        }

    }
    // return v_node[goal].count;
    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(6, 9);
    // graph.addEdge(7, 9);
    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;
}