{"id":110,"date":"2009-10-02T23:32:32","date_gmt":"2009-10-02T22:32:32","guid":{"rendered":"http:\/\/klondike.xiscosoft.es\/klog\/?p=110"},"modified":"2009-10-02T23:34:07","modified_gmt":"2009-10-02T22:34:07","slug":"an-easy-to-understand-but-efficient-algorithm-to-know-the-nodes-which-a-in-any-path-from-a-to-b","status":"publish","type":"post","link":"https:\/\/klondike.es\/klog\/2009\/10\/02\/an-easy-to-understand-but-efficient-algorithm-to-know-the-nodes-which-a-in-any-path-from-a-to-b\/","title":{"rendered":"An easy to understand (but efficient) algorithm to know the nodes which are in any path from a to b"},"content":{"rendered":"

Today I had to face a simple but interesting graph problem: Given a graph and two nodes a and b. Find all the nodes which form part of any of the possible paths from a to b.<\/p>\n

Though it may seem a bit difficult for starters it can be solved easily using a simple algorithm and knowing a few things:<\/p>\n

First we take the graph G and find the reverse graph G’ (this is a Graph with the edges reversed).<\/p>\n

This would be the transposition of the connection matrix or could be done easily if the graph is represented as a vector of lists of nodes with a edge from its position going over each position on the vector and adding that position to the list on G’ on the position of every node in that list.<\/p>\n

Now we will take a list L of all the nodes on G which are reachable from A. This can be easily done:<\/p>\n

Q := queue
\nV :- bool vector size nodes(G) initialized to false
\nV[A] = True
\nQ.insert A
\nWhile ! Q.empty<\/p>\n

n = Q.top
\nQ.pop
\nForeach Q.edgeFrom(n) e #This is for each node with an edge from n to it\n<\/p>\n

If (!V[e])<\/p>\n

Q.insert n
\nV[e] = True<\/p>\n

Then V will be True for each node reachable from A<\/p>\n

We do the same with G’ and B and store it on L’<\/p>\n

Finally if a node is in both L and L’ then it is part of at least one path from A to B<\/p>\n

Now the explanation on why it works:<\/p>\n