Home > Uncategorized > Determine whether there exists a path in graph G of length L.

Determine whether there exists a path in graph G of length L.

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

Advertisements
Categories: Uncategorized
  1. August 14, 2012 at 9:38 pm

    Thank you so much .. that was very helpful
    I have the qualifying exam tomorrow 🙂

  2. xellos54
    October 25, 2012 at 2:11 pm

    “If the graph has a cycle, then the graph has a path of any length L”

    Huh? I have one node A with one edge (A,A) with weight of 5. I can have paths like 0, 5, 10, 15 length, but can I have e.g. path of 3 length? I don’t think so…

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: