Getting all possible paths of two vertices in a Graph using DFS

>> Thursday, June 9, 2011

As you might have seen, I recently explained something similar, but now I'll find all possible paths. This is pretty much more of the same but it's way more tricky.
Well modify our basic DFS search and do a view more stuff

Input: vertex start, vertex end, list of lists of vertices "paths", list of vertices "path"
Output: boolean, wheter or not I found a path
add start to path
if(start == end)
    return true
else
    mark start as visited
    for each adyacent vertex w of start
        if w is not visited
            boolean found = dfs(w, end, paths, path)
            if found
                add a clone of path to paths
        path.removeLast()
    mark start as non visited
    return false

That's it! It might seem simple but in Java it's a bit longer. Hope it helped!

Read more...

Getting a Graph's path between two vertices using DFS

As you might have seen, I have made a similar post before, but this time, we use another way of going though our graph, it's called Depth First Search, and it's my favourite way as it's nature is recursive, and recursion is fancy :)
Basically, we will now go though our graph with an bucket of paint and a string, every time we see a non visited vertex, we will paint it, tie the string to it and go on, when we cannot advance any futher, we go back pulling from our string, until we see an unvisited vertex, to then repeat. You can kind of think of it like a way to get though a maze.
The algorithm is something like this

Input: a start vertex
mark start as visited
visit start
for each incident edge E of start
w = opposite(start, E) 
if(w is not visited)
mark w as visited
DFS(start)

The output of DFS can be viewed as a tree, with root on Start, every time we visit a node adyacent to start we add it as a child, and we do the same with each of start's children, making a generic tree. There are different kind of edges which we can see in this image.

Output of a DFS showing different kind of edges
Anyways, that is not important for us, what is important is to get the path between two vertex, this is quite easy, same as with BFS, we have to modify mostly the 'visit' part of the algorithm.

Input: a start vertex, an end vertex, and a list L
// This time we won't output anything, just add the path to our list!
mark start as visited
L.addLast(start)
if(start == end)
return true
else
for each incident edge E of start
w = opposite(start, E) 
if(w is not visited)  
found = DFS(start)
if(found) return true
endfor
L.removeLast()
return false

And that's it. With that algorithm we can search for a path between two vertex, we have to add an extra argument, but we can make a method to make everything nicer. Like in this java example.
Hope you find it useful!

Read more...

Getting a Graph's shortest path between two vertices using BFS

Long title indeed, but this is a rather specific entry. I've been working with graphs lately, for university, and I'm afraid there are lots and lots of different properties and algorithms (you can imagine studying that for an exam is a pain in the ass) but well, I tried searching for this on Google with no luck, there are many algorithms for getting the shortest path between two vertex, and many sites say "It can be done using BFS" but they do not explain how.
So, I found a rather nice and easy solution. First of all, let's say G is a simple graph, with no directed edges, and we don't consider edges' weight. I'll use pseudo-code in this entry since it's more CS oriented.
First of all, if you don't know what BFS is, it's Breadth First Search, it's a way of iterate through a graph, in which you go by levels.

BFS Animation

You can see wikipedia for more info, I'll assume you know the algorithm, at least just on paper, the algorithm is like this:

Input: a vertex called start
Let Q be a queue
Q.enqueue(start)
visit start
while(Q is not empty)
    w = Q.dequeue()
    for each adyacent vertex v of w do
        if v is not visited
            mark v as visited
            add v to queue
            visit v

That's it. Basically, when you solve a problem using an algorithm like this, what you want to work on is on the "visit v" part, what we are gonna do is use a map, in which we will save each vertex we visit, and once we reached our end vertex, we simply "go back". A map is a data structure which has a Key and a Value, so we will use the Key as our vertex, and the value will be the vertex' parent, that way we can just go back and return a list of visited vertex' which make the shortest path from START to END.


Input: a vertex called start, and a vertex called end
Output: a list containing the shortest path from start to end, or null if it cannot find a path
Let Q be a queue
Let M be a map
Q.enqueue(start)
map.put(start, null) // Start has no parent!
while(Q is not empty)
    w = Q.dequeue()
    for each adyacent vertex v of w do
        if v is not visited
            mark v as visited
            add v to queue
            if(v == end)
                Let L be a list
                while(v != null)
                    L.addFirst(ww)
                    ww = M.get(ww)
                return L
return null

There it is, hopefully someone will find it useful! Note that basically the only part that changes is the 'visit' part.
I'll leave the Java code just for the sake of it ;) Sorry it's in spanish, as it's from university, but this should not be much problem.

Read more...

  © Blogger template Simple n' Sweet by Ourblogtemplates.com 2009

Back to TOP