Determine whether there exists a path in graph G of length L.
Solution:
If the graph has a cycle, then the graph has a path of any length L.
If the graph does not have a cycle , then we are finding a simple path of length L.
We will use DFS with some modification to find simple path of length L.
For this with every node n, we will maintain a value named maxPath (other than start_time and end_time) which determines path of Maximum value.
We will initialize each nodes of G with maxPath = 0;
So, the steps to find simple path of Lengh L is :
1. Run modified DFS-visit()
2. check each node for the maxPath value.
DFS-visit(u) {
time = time + 1
u.start = time;
for each v <em>belongs-to</em> adj[u]
if ( v.color = WHITE ) {
DFS-visit(v)
if (u.maxPath < v.maxPath + 1 )
u.maxPath = v.maxPath + 1;
}
u.endtime = time + 1;
u.color = BLACK
Advertisement
