Explore BrainMass

Explore BrainMass

    Depth First Numbering

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

    Apply the depth-first search algorithm to the graph (in the attachment) to find the depth-first search numbering. Then color the tree edges (blue for example) and the back edges (black for example). Now assign directions to all the edges. You may start from any point on the graph.

    Is the resulting graph strongly connected?

    See the attached file.

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


    Solution Preview

    Please refer to http://www.csee.ogi.edu/class/cs532/13.pdf for more information on Depth First Numbering algorithm used in this response. Each node is labeled in a/b format where a can be taken as the depth first number of that node.

    Tree edges have been colored thick green and back edges have been retained as thin black lines. Since original graph is an undirected graph, every edge in it can either be a tree ...

    Solution Summary

    Since the used Depth First Numbering algorithm requires traversing neighbor nodes of a node in some order (in the order these appear in adjacency list), the ordering in adjacency list will effect the final outcome.