Explore BrainMass

Explore BrainMass

    Graph to tree for breadth and depth first search tree

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    Hi. We have been asked to do the following with a given graph (will be uploaded "cgraph.jpg")

    1. Depth first tree
    2. Breath first tree

    I know now do to a depth first search and breath first search, but not a tree (I don't even know what it is asking). I'm assuming we are to somehow put it in tree form.
    (This is to be written on paper, not used in program).

    These are my results from the
    depth first search: ABCDEF
    breath first search: ABFCDE

    I didn't post my steps however I know depth first uses stack and breath first uses queue.
    I just need to be shown how to make them "trees" (on paper).

    © BrainMass Inc. brainmass.com October 10, 2019, 7:02 am ad1c9bdddf


    Solution Preview

    To convert the given graph into a tree, you cut links C to F and C to E (see attachment).

    For Breadth search, traverse left to right at every level.
    For given problem:
    Level 1: A
    Level 2: left: B, right : F
    Level 3: C
    Level ...

    Solution Summary

    This problem describes on paper how to convert a graph into a tree, and search breadth first and depth first.