Need some insight to directed graphs

[thumpkidd9]

Hello,

I want to find all the paths from 1 vertex to another in an acyclic directed graph. I feel as though this has to be done recursively but I cant figure out just how. I'm using an adjacency list not a matrix. So for example f you have a graph

A-B
A-C
B-C
C-D

Then all paths from A-D should be A-B-C-D and A-C-D

I can find one path with no problem using DFS, but somehow when I hit a dead end, I need to contruct another path, starting at source vertex. Any ideas?

 

[stefanwagner]

Without seeing some code, we can only guess...

seeking a job as java-programmer in Berlin:

http://home.arcor.de/hirnstrom/bewerbung

 

[thumpkidd9]

dfs is a helper method to allpaths. Here is what I have so far. It works well with some example but not with all of them.

public boolean dfs(int source, int dest, boolean[] visited, boolean[] dfs, Path p, Vector v) {
		visited[source] = true;
		dfs[source] = true;
		Edge ptr = adjLists[source].neighbors;
		for(; ptr!=null; ptr=ptr.next) {
			if(!visited[ptr.vnum]) {
				if(dfs(ptr.vnum, dest, visited, dfs, p, v)) return true;
				if(ptr.vnum == dest) {
					//p.addVertex(adjLists[ptr.vnum].label);
					return false;
				}
				p = new Path();
			}
			else {
				if(dfs[ptr.vnum]) return true;
			}
		}
 		if(source != dest) dfs[source] = false; // hit a dead end, cant be in dfs
        else {
        	for(int i = 0; i<numVerts; i++) {
				if(dfs[i] && visited[dest]) {
					p.addVertex(adjLists[i].label);
				}
				visited[i] = false;
			}
			v.add(p);
			p = new Path(); // reset path
		}
        return false;
	}