Results 1 to 8 of 8

Math Help - Breadth First-Search Induction

  1. #1
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8

    Breadth First-Search Induction

    Given the following algorithm for a breadth first search of a graph, using queues.

    Code:
    Set the distances for each node to infinity
    Enqueue the starting node, and set distance of the node to zero.
    While the queue is not empty {
                Dequeue the first element in the queue
                Enqueue all the nodes adjacent to the node we just dequeued
                Update the distances of each of the nodes we just enqueued
    }
    Prove that for any two elements in the queue u and v. |dist(u) - dist(v)| \leq 1. A hint provided to me was to prove a stronger statement about the ordering of the elements in the queue.

    So, I thought if I could prove via induction that if u is closer to the front than v in queue then dist(u) \leq dist(v), and that |dist(front) - dist(back)| \leq 1. But I am having troubles with it.

    Is my idea good, or is there an easier property I could prove? If what I have is good, how could I prove it?

    Thanks in advance!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8
    I've managed to prove that:

    for i<j  |dist(u_j) - dist(u_i)| \leq 1 if and only if dist(u_i) \leq dist(u_j)

    However, I am still having troubles proving the statement on the right.
    I am thinking either I have to do induction of the number of loops performed by the alogrithm, or i could do a proof by contradiction but I can't seem to get either to work.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Haven View Post
    I've managed to prove that:

    for i<j  |dist(u_j) - dist(u_i)| \leq 1 if and only if dist(u_i) \leq dist(u_j)

    However, I am still having troubles proving the statement on the right.
    I am thinking either I have to do induction of the number of loops performed by the alogrithm, or i could do a proof by contradiction but I can't seem to get either to work.
    Maybe this is just me being dumb, but the last line within the while loop is:

    "Update the distances of each of the nodes we just enqueued."

    Doesn't the algorithm need to specify how we update the distances?


    Edit: Making some massive assumptions on what is meant by the problem statement, we have:

    Assumption 1: dist(u) signifies the distance from node u to the starting node.

    Assumption 2: The true distance between any two adjacent nodes is 1.

    Assumption 3: We are setting all the distances to infinity initially so that we can distinguish between visited and non-visited nodes.

    Assumption 4: We will not add a node to the queue if it has already been visited.

    Then it seems we are dealing with an algorithm that assigns to each node the distance between it and the starting node, and it should be clear that since a queue is FIFO, when the front of the queue (which contains the oldest elements) has elements distance n from the starting node, the back of the queue (newest elements) has either elements distance n from the starting node, or distance n+1, because we won't get to distance n+2 (if there are any such nodes) until all the distance n nodes are dequeued (this is not a very rigorous explanation, but you should get the idea).

    Edit 2: Sorry, I switched the words "front" and "back" which was silly.
    Last edited by undefined; June 27th 2010 at 10:54 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8
    It's my fault for oversimplification.

    let S = the node that was just dequeued in the loop.
    The distances of the nodes we enqueue is dist(S)+1
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Haven View Post
    It's my fault for oversimplification.

    let S = the node that was just dequeued in the loop.
    The distances of the nodes we enqueue is dist(S)+1
    I edited my post above. I think it addresses your question. Let me know. (I didn't see your post #4 until just now.)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8
    I understand your explanation, but I am having difficulties proving it.
    I've tried to prove it as a loop invariant, but I can't get it to work.

    assume we have performed k iterations of the loop and the property
    dist(u_i) \leq dist(u_j) for i<j
    holds for all the nodes in the queue thus far.

    If we dequeue the first node and enqueue it's neighboring nodes, one of which being u_t
    Then it is clear that dist(u_t) = dist(u_1) + 1
    However I can't seem to show that for any i
    dist(u_i) \leq dist(u_t) = dist(u_1)+1
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Haven View Post
    I understand your explanation, but I am having difficulties proving it.
    I've tried to prove it as a loop invariant, but I can't get it to work.

    assume we have performed k iterations of the loop and the property
    dist(u_i) \leq dist(u_j) for i<j
    holds for all the nodes in the queue thus far.

    If we dequeue the first node and enqueue it's neighboring nodes, one of which being u_t
    Then it is clear that dist(u_t) = dist(u_1) + 1
    However I can't seem to show that for any i
    dist(u_i) \leq dist(u_t) = dist(u_1)+1
    Okay so intuitively it's already clear, and the only problem is with formalising.

    Maybe break into cases:

    Case 1: the queue is empty.

    Case 2: the queue has one element.

    Case 3: the queue has more than one element, and the first (oldest) element has the same distance as the last (newest) element.

    Case 4: the queue has more than one element, and the first element has a distance one less than the distance of the last element.

    The proof would then proceed to show that these are all the possible cases; that is, if we consider these cases to be states, then it is a closed system. (Show which states can lead to which other states.)


    Edit: Actually, something more along the lines of your current proof, can't you just show that the distance between the first element and last element is at most 1, call them distances n and n+1, and then from this reason that since distance must be integer, and because of the ordering you determined, therefore all nodes must have distance in {n, n+1}.
    Last edited by undefined; June 27th 2010 at 11:18 PM. Reason: typo!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Sorry for so many edits. I edited my latest post and am making this post just in case you're using email notification and would not otherwise notice..
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: April 1st 2011, 10:05 AM
  2. Breadth-frist transversal
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 24th 2010, 05:27 AM
  3. search For f - 1
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: October 28th 2007, 07:11 PM

Search Tags


/mathhelpforum @mathhelpforum