FAQ: Graph Search: Conceptual - Graph Search Traversal Order

This community-built FAQ covers the “Graph Search Traversal Order” exercise from the lesson “Graph Search: Conceptual”.

Paths and Courses
This exercise can be found in the following Codecademy content:

FAQs on the exercise Graph Search Traversal Order

There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head here.

Looking for motivation to keep learning? Join our wider discussions.

Learn more about how to use this guide.

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

Can some one explain the post order traversal mentioned in the example? Did quite understand how it started with “Spikes”… Below is the statement from the lesson…

"
Now, let’s say we want the same values, but with each value only added to the list once its vertex has been popped from the stack. In this case, our post-order DFS traversal would result in a list that looked like:

[“Spikes”, “Snakes”, “Lava”, “Piranhas”, “Lasers”]
"

3 Likes

Here’s the graph:

Now you set out, in this order

“lasers” => “lava” => “snakes” => “spikes”. Those names are appended to your stack.

You’re now at the end of a branch, so you back up, popping as you go, appending each name to your “visited” list:

[ "spikes","snakes" , "lava"]

Now you are back at “lasers”, the only remaining name on the stack, but you don’t want to pop that yet, because you’re not done. It’s time to explore the second branch:

“lasers” =>“piranhas”. (end of branch, as “spikes” has already been visited) Now the stack is [“lasers’, 'piranhas”]

So, pop “piranhas”, append to the “visited” list, then pop “lasers”, giving the final list:

[ "spikes","snakes" , "lava", "piranhas", "lasers"]

15 Likes

The final question is as follows:

What would the resulting lists look like from pre-order, post-order, and reverse post-order DFS traversals if the origin vertex were “Spikes”?

What would it look like? I would honestly think the answer to all questions is “empty” since “Spikes” has no edges (correct?) but that feels wrong to me.

5 Likes

@byteninja93187, you’re correct. Since the graph is directed, “Spikes” has no reachable neighbors, so each search would be an empty list.

8 Likes

But you still visited “Spikes” so it should return its value.

2 Likes

This seems to be incorrect to me. After reading through the dialogue again, I note this text at the end: “What happens if there are unvisited vertices that are not reachable from the current path? The search would visit them in (here alphabetical) order after exploring the current path.”

Surely, this implies that, for example in a pre-order DFS, upon visiting “Spikes” as the origin vertex and discovering that there are no available paths, the algorithm would then (in this case) resort to choosing a new vertex alphabetically. This should mean that it chooses its next vertex is either “Lasers”, or, if the alphabetisation takes the current vertex as a starting point; “Piranhas” would be the next closest word in an alphabetised order of all vertices after “Spikes”. Do you follow my logic?

Would love to hear anyone’s take on this.

2 Likes

I’m also curious about that! Can anybody help us out here?

Well finally got this far and I’m not gonna just get this far… so my take is this:

To get the presort order you’d have to change the direction of the edges so the edges at Spike to resemble those at lasers. So the the spike vertex would now have outward directed edges like lasers’s vertex It helped me to pencil and paper it with something like a Binary tree but obviously not something you’d want to implement.
Spikes
/
Snakes Piranhas
/
Lava
/
Lasers

Then lets reverse alphabetical sort to start with? Since going out from Lasers was also vaguely patterned off of alphabetization.

So for post sort: lasers => lava => snakes => piranhas =>spikes

Reverse post sort/top sort: spikes =>snakes => piranhas =>lava=>lasers…

YOOOOOO~~~!!! THIS THOUGH

2 Likes

This link could help:

https://eli.thegreenplace.net/2015/directed-graph-traversal-orderings-and-applications-to-data-flow-analysis/

There is this excerpt from the “DAGs with multiple roots” heading:

The idea is a fairly simple modification of the DFS traversal shown earlier. We pick an arbitrary unvisited node in the graph, treat it as a root and start dutifully traversing. When we’re done, we check if there are any unvisited nodes remaining in the graph. If there are, we pick another one and restart. So on and so forth until all the nodes are visited:

The page then goes on to describe modified code for traversing graphs with no clear root node (ie in the graph in slide 4 of the exercise where “spikes” or “lasers” or any other vertex could be the starting/root vertex):

while len(allnodes) > len(visited):
        # While there are still unvisited nodes in the graph, pick one at random
        # and restart the traversal from it.
        remaining = allnodes - visited
        root = remaining.pop()
        orders.append([])
        dfs_walk(root)

So they basically already have a set of all the vertices which is unordered and can use that to see which nodes are unvisited and then start a traversal from there as it hints at in the exercise.

Any other thoughts/feedback would be welcome, especially if I’ve made a mistake but the website is well worth a visit

I don’t understand how is this done , please help

You may notice that the post-order list is not the reverse of the pre-order list. A reverse post-order list would still begin with “Lasers”, but then begin to differ:

["Lasers", "Piranhas", "Lava", "Snakes", "Spikes"]

I am not happy how simply they mentioned about reverse post order . useless

Clarifying question: What happens if there are unvisited vertices that are not reachable from the current path? Do they mean vertices that are not adjacent to any of the vertices in the current path?

First, it’s important to note that a vertex that is not reachable from a specific path can still have adjacent vertices to it. A vertex is adjacent to another if there is an edge between them, whether that edge is directed or not.

An example of this is present in the exercise: the vertex “Spikes” is adjacent to both “Snakes” and “Piranhas”, but if we start the search from “Spikes” there would not be a path to anywhere from it, although it has adjacent vertices. Therefore, the search would start and end in “Spikes” unless the graph implementation has a list of all its vertices for the search algorithm to choose another starting vertex to continue the search.

In this case, they follow that quote [What happens if there are unvisited vertices that are not reachable from the current path?] by saying [The search would visit them in (here alphabetical) order after exploring the current path.] .

So, after checking the “Spikes” vertex, the algorithm would then go to the first (alphabetically) vertex, “Lasers”, and continue the search from there, resulting in the following lists:

~> Pre-Order: [“Spikes”, “Lasers”, “Lava”, “Snakes”, “Piranhas”]
~> Post-Order: [“Spikes”, “Snakes”, “Lava”, “Piranhas”, “Lasers”]
~> Reverse Post-Order: [“Spikes”, “Lasers”, “Piranhas”, “Lava”, “Snakes”]

1 Like