Here we are solving another exercise from the Cracking the Coding Interview. It says:
4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
First we need to represent the graph. When I was in high-school we used to represent graphs (I implemented in pascal) as a matrix of n*n elements. m[k,q] = 1 if there is a vertices from k to q. This representation is not suitable for large graphs (especially if they have small number of vertices ) but will do just well for our exercise:
class dag: def __init__(self, _matrix): self.matrix=_matrix def get_adj(self, node): result= for i,val in enumerate(self.matrix[node]): if val == 1: result.append(i) return result def nb_nodes(self): return len(self.matrix)
Before implementing our function
hasPath(dag, nodeK, nodeQ) lets write a test:
def test(): m = [[1,0,0,1], [0,1,1,1], [0,1,1,0], [0,0,1,1]] d = dag(m) assert (hasPath(d,0,2)) assert (hasPath(d,0,1)) assert (hasPath(d,2,3)) assert (hasPath(d,2,0)==False) assert (hasPath(d,1,0)==False) print 'Test Ok'
And now the required function. We will traverse the graph starting from the first node and stop when we encounter the second node.
There are 2 graph traversal strategies:
- Depth First Search: DFS involves searching a node and all its children before proceeding to its siblings.
- Breadth First Search: BFS involves searching a node and its siblings before going on to any children.
We will do DFS for the sake of this exercise: We will use a queue (FIFO) to keep nodes that need to be visited. We put the first node in the queue. Then we pop a node from the queue, visit it and put all its children in the queue. We also need to remember which nodes have been visited to avoid cycles.
So here it is:
def hasPath(dag,start, end): q=[start] visited =  * dag.nb_nodes() while len(q)>0: node = q.pop() visited[node]=1 if end==node: return True q= q+ [x for x in dag.get_adj(node) if visited[x]==0] return False
Update – let’s make it more pythonic
by taking into account mebubo ‘s comments:
class dag: def __init__(self, _matrix): self.matrix=_matrix def get_adj(self, node): return [i for (i, val) in enumerate(self.matrix[node]) if val] def hasPath(dag,start, end): q=[start] visited =  * dag.nb_nodes() while len(q)>0: node = q.pop() visited[node]=1 if end==node: return True q= q+ [x for x in dag.get_adj(node) if not visited[x]] return False