CareerCup

You can do smth similar to DFS( or BFS) travel that you only visit the node that you have not visited to prevent loop. You also have to keep track the path from the source so that we can print it out when you reach the destination.

Something to note
- The length of the path is less or equal to N which is the number of vertices
- When you reach the destination then print the path and stop the current search branch since the destination can not be visited second time
- We need to un-visit a node at the end of the recursive function to allow investigation from other branch that might come back to the same node (this is the main different from original DFS or BFS)

class Graph {
public:
    Graph(int n) : g(n), visit(n, false), path(n, -1) {}
    void add(int from, int to) { 
        g[from].push_back(to); g[to].push_back(from); }
    void print_path(int l) const {  
        for (int i=0; i< l; ++i) cout << path[i] << ' ';  
        cout << endl; 
    }
    void traverse(int source, int dest) {
	fill(visit.begin(), visit.end(), false);
	DFS(source, dest, 0); 
    }  
private:
    void DFS(int u, int dest, int level) {
	path[level] = u;
	if (u == dest) {
	    print_path(level+1);
	    return;
	}
	visit[u] = true;
	for (auto v : g[u] )
	    if (!visit[v]) 
	        DFS(v, dest, level + 1);
        visit[u] = false;
    }
    vector<vector<int> > g;
    vector<bool> visit;
    vector<int> path;
}

Beside I don't care if you up vote or down-vote my answer, but if you down-vote, that means I did something stupid and I want to know what is your perspective.

{{
class Graph {
public:
Graph(int n) : g(n), visit(n, false), path(n, -1) {}
void add(int from, int to) {
g[from].push_back(to); g[to].push_back(from); }
void print_path(int l) const {
for (int i=0; i< l; ++i) cout << path[i] << ' ';
cout << endl;
}
void traverse(int source, int dest) {
fill(visit.begin(), visit.end(), false);
DFS(source, dest, 0);
}
private:
void DFS(int u, int dest, int level) {
path[level] = u;
if (u == dest) {
print_path(level+1);
return;
}
visit[u] = true;
for (auto v : g[u] )
if (!visit[v])
DFS(v, dest, level + 1);
visit[u] = false;
}
vector<vector<int> > g;
vector<bool> visit;
vector<int> path;
}
}}

class Graph {
public:
    Graph(int n) : g(n), visit(n, false), path(n, -1) {}
    void add(int from, int to) { 
        g[from].push_back(to); g[to].push_back(from); }
    void print_path(int l) const {  
        for (int i=0; i< l; ++i) cout << path[i] << ' ';  
        cout << endl; 
    }
    void traverse(int source, int dest) {
	fill(visit.begin(), visit.end(), false);
	DFS(source, dest, 0); 
    }  
private:
    void DFS(int u, int dest, int level) {
	path[level] = u;
	if (u == dest) {
	    print_path(level+1);
	    return;
	}
	visit[u] = true;
	for (auto v : g[u] )
	    if (!visit[v]) 
	        DFS(v, dest, level + 1);
        visit[u] = false;
    }
    vector<vector<int> > g;
    vector<bool> visit;
    vector<int> path;
}

static void PrintAllPaths(List<int>[] graph, int n, int source, int dest)
{
    DFS(source, dest, graph, new List<int>(), new bool[n]);
}

static void DFS(int v, int dest, List<int>[] g, List<int> path, bool[] used)
{
    path.Add(v);
    used[v] = true;
    
    if (v == dest)
    {
        Print(path);
    }
    else
    {
        foreach(int u in g[v])
        {
            if (!used[u]) DFS(u, dest, g, path, used);
        }
    }
    
    path.RemoveAt(path.Count - 1);
    used[v] = false;
}

print path in a recursive way

GRAPH={'A':['B','C','D'], 'B':['A','C','D'], 'C':['A','B','D'], 'D':['A','B','C']}

def find_noloop_path(s, t, path):
    if s in path:###already visited in path
        return

    if s == t:###find the target
        print path + [t]
        return

    path.append(s)
    for n in GRAPH[s]:
        find_noloop_path(n, t, path[:])


find_noloop_path('A', 'C', [])

result:
['A', 'B', 'C']
['A', 'B', 'D', 'C']
['A', 'C']
['A', 'D', 'B', 'C']
['A', 'D', 'C']

ArrayList<ArrayList<Node>> allPath(Node s, Node t){
	Queue<ArrayList<Node>> q = new Queue<ArrayList<Node>>();
	ArrayList<Node> list = new ArrayList<Node> ();
	list.add(s);
	q.enque(list);
	ArrayList<ArrayList<Node>> result = new ArrayList<ArrayList<Node>>();
	while(!q.empty()){
		ArrayList<Node> cur = q.deque();
		Node temp = cur.get(cur.size()-1);
		for(Node n : temp.neighbors){
			if(!cur.contains(n)){
				ArrayList<Node> tar = new ArrayList<Node>(cur.subList(0, cur.size()));
				tar.add(n);
				if(n == t){
					result.add(tar);
				}	
				else
					q.enque(tar);
			}
		}
	}
	return result;
}

Here my C++ solution:

#include <iostream> 
#include <vector> 
#include <stack>
using namespace std; 
  
class Graph { 
public: 
    Graph(int n) : g(n) {} 
    
    void add(int from, int to) { 
        g[from].push_back(to); g[to].push_back(from); } 
    
public:
    void print_path() {  
        for(int i = 0; i < path.size(); i++) {
        	cout << path[i] << ' ';
        }
        cout << endl; 
    }
    void traverse(int source, int dest) {
		DFS(source, dest);
    }  
private:
    void DFS(int u, int dest) {
		path.push_back(u);
		
		if (u == dest) {
	    	print_path();
		}
		else {
			for (auto v : g[u]) {
				bool stop = false;
		    	
		    	for(auto s : path) {
		    		if(s == v) {
		    			stop = true;
		    		}
		    	}
		    
		    	if(!stop) {
		    		DFS(v, dest);
		    	}
	    	}
		}
    	path.pop_back();
    }
    
    vector<vector<int> > g;
    vector<int> path; 
}; 
  
int main() { 
    // your code goes here 
    
    Graph g(8); 
    
    //g.add(0, 7); 
    g.add(0, 4); 
    
    //g.add(1, 2); 
    //g.add(1, 7); 
    
    //g.add(2, 7);    
    //g.add(2, 1); 
    //g.add(2, 5); 
    
    // no node with 3 
    
    g.add(4, 0); 
    g.add(4, 5);    
    g.add(4, 6); 
    
    g.add(5, 4); 
    //g.add(5, 2); 
    g.add(5, 6);    
    
    g.add(6, 4);    
    g.add(6, 5); 
    
    //g.add(7, 2);    
    //g.add(7, 1);    
    //g.add(7, 0);        
    
    g.traverse(0, 6); 
    
    return 0; 
}