Suppose you are given an undirected graph G, and two vertices s and t. We know t

Question

Suppose you are given an undirected graph G, and two vertices s and t. We know that we can check to see if there is a path from s to t by simply doing a breadth first search or a depth first search. While both of these are incredibly time efficient, sometimes we are interested in what we can do when we restrict how much space we have.

It turns out that, if you, starting with a pointer at s, randomly choose a neighboring vertex of the pointer, move the pointer to that neighbor, and repeat, you can expect that you will find t in O(V3 ) steps with high probability, unless there is no such path, of course. This gives us a really nice randomized algorithm for guessing if there is a path from s to t that uses only enough space to remember one vertex!

Show that this algorithm does not work for directed graphs. That is, give a set of directed graphs {Gn|n >= 0} which each have a path from s to t, but, as n grows, the probability that the algorithm finds t in C|V |3 steps goes to 0 (C is some fixed constant that describes how many random steps the algorithm takes - should answer should work regardless of the value of C), and prove that this is really the case for this family of graphs.

Explanation / Answer

Graph g(4);

    g.addEdge(0, 1);

    g.addEdge(0, 2);

    g.addEdge(1, 2);

    g.addEdge(2, 0);

    g.addEdge(2, 3);

    g.addEdge(3, 3);

    int u = 1, v = 3;

    if(g.isReachable(u, v))

        cout<< " There is a path from " << u << " to " << v;

    else

        cout<< " There is no path from " << u << " to " << v;

    u = 3, v = 1;

    if(g.isReachable(u, v))

        cout<< " There is a path from " << u << " to " << v;

    else

        cout<< " There is no path from " << u << " to " << v;

    return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.