Results 1 to 2 of 2

Math Help - Breadth-frist transversal

  1. #1
    Junior Member
    Joined
    Nov 2008
    Posts
    36

    Breadth-frist transversal

    I understand how to list each transversal when each node has at most
    2 lines( coming in or out) but how not sure about a graph where a node has
    more than 2 line connected to it. For example consider this graph :



    Can you help me for instance list the transversal route using breadth-first search
    starting at node F.

    One way I tried and got this : F-C-E-D-I-G-H-B-A-J, but am not sure if its correct. I am not sure how to transverse through the graph, say starting at node F, using the breadth-first-search. Any Help?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,535
    Thanks
    778
    F-C-E-D-I-G-H-B-A-J
    I think J must come before D because the distance from F and J is 1 and between F and D is 2.

    One way to think about breadth-first search is to imagine water flowing from F. It first reaches nodes at distance one, then at distance two, etc. The order in which nodes at the same distance are listed (e.g., J, E, C) is probably not important.

    To write an algorithm, one considers a queue (first in, first out) of nodes. In the beginning the queue has only F. There is also a sequence of nodes already visited; initially it is empty. At each step, one takes out a node from the end of the queue, mark it as visited, and pushes all its neighbors that have not been visited and are not already in the queue into the start of the queue. This continues until the queue is empty.

    So a possible sequence of queue contents and the list of visited nodes is

    Code:
    Queue                     Visited
    ---------------+--------
    F              |
    J E C          | F
    D B I J E      | F C
    D B I J        | F C E
    D B I          | F C E J
    D B            | F C E J I
    ...
    
    I'll let you finish from here. Feel free to post your version for checking.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. frist order differential equation problem
    Posted in the Differential Equations Forum
    Replies: 5
    Last Post: September 5th 2011, 04:30 PM
  2. Replies: 2
    Last Post: April 1st 2011, 09:05 AM
  3. Breadth First-Search Induction
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: June 27th 2010, 10:12 PM
  4. Alternate Angles In Transversal
    Posted in the Geometry Forum
    Replies: 2
    Last Post: November 28th 2009, 05:24 PM
  5. No idea...transversal
    Posted in the Geometry Forum
    Replies: 2
    Last Post: July 26th 2009, 10:41 PM

Search Tags


/mathhelpforum @mathhelpforum