?

Algorithms & Data Structures

Free Version

Upgrade subject to access all content

Moderate

Creating a Tree with Depth-First Search

ALGOR-S1X4GV

There are several algorithms that can be used in graph traversal. One of the simplest is called Depth-First Search.

If you were to implement Depth-First Search on the graph below, what would the resulting tree, rooted at Node 1, look like?

A node is added to the tree whenever the node is explored. A node is considered explored when the algorithm is processing that node to discover its neighbors. A node’s neighbors are any nodes that are connected to that node by an edge in the graph. If there is a choice between neighboring nodes, discover them in ascending numerical order.

Ashley Salzetti. Created for Albert.io. Copyright 2016. All rights reserved.

A

Ashley Salzetti. Created for Albert.io. Copyright 2016. All rights reserved.

B

Ashley Salzetti. Created for Albert.io. Copyright 2016. All rights reserved.

C

Ashley Salzetti. Created for Albert.io. Copyright 2016. All rights reserved.

D

Ashley Salzetti. Created for Albert.io. Copyright 2016. All rights reserved.