21.1.2. Executing the Algorithm by Hand

So, as before let us execute this algorithm by hand on our graph, you see how it works before we write the pseudo code. So, this time we are starting at 4. So, first step is to mark 4 as visited. So, we start mark 4 as visited and we identify that it has 3 neighbours before neighbours 1, 3, 5, and 6. So, taking them an order we start with 1; 1 is not visited. So, we mark it as visited.

In this chunk, we introduce the starting point for our depth-first search (DFS) algorithm. We begin by choosing vertex 4 as our starting point. The first action is to mark vertex 4 as visited, indicating that we are currently exploring this vertex. After marking it as visited, we identify the neighbors of vertex 4, which are vertices 1, 3, 5, and 6. We will explore these neighbors in the order they are listed, starting with vertex 1. Since vertex 1 has not been visited yet, we proceed to mark it as visited next.

Think of this as exploring a new city. You start at a landmark, like a museum (vertex 4), and you note the nearby attractions (neighbors) you could visit—an art gallery (vertex 1), a park (vertex 3), a cafe (vertex 5), and a library (vertex 6). You decide to visit the art gallery first since it’s the closest and hasn’t been explored yet.

We put 4 on the stack, saying a suspending the execution of 4, because now we are going to explore 1 in steps. So, now we go to 1, then we see that 1 has neighbours 2, 3, and 4 among these of first is 2. So, if we put 2 on the stack, since it could not are visited earlier, we put 1 on the stack, since now we are suspending 1.

This chunk illustrates the process of exploring the neighbors of the current vertex (which is now vertex 1). We add vertex 4 to a stack to remember we need to return there after exploring current neighbors. While exploring vertex 1, we find its neighbors: 2, 3, and 4. We will explore these neighbors starting from vertex 2. We mark vertex 1 as suspended by pushing it onto the stack, allowing us to return to it later once we've fully explored vertex 2.

Continuing with our city exploration analogy, imagine that you visit the art gallery (vertex 1) and discover that it leads to an exhibition hall (vertex 2) that you haven’t seen yet, but you also need to remember that you wanted to come back to the gallery after exploring this new hall. So, you make a note that you’ll return (suspend execution at vertex 1) while you investigate this exhibition.

Now when we come to 3, it has 2 neighbours 1 and 2, but both of them are already visited. So, thus nothing to become. So, we must go and must go back to the last vertex which we suspended namely 2, and explore its neighbors.

In this chunk, we examine vertex 3 to determine if there are any unexplored neighbors. Upon checking, we find that both of its neighbors (1 and 2) have already been visited, which means there are no new paths to explore from vertex 3. This leads us to backtrack to vertex 2, which we had previously suspended. This process of backtracking occurs because our goal in depth-first search is to explore as far as possible along each branch before retreating.

Imagine while exploring the exhibition hall (vertex 3) you find that all the rooms (neighbors) connected to it (rooms 1 and 2) are already examined. Just like in a real exploration, if you reach a dead end, you look for the last place you haven’t fully explored—this is like returning to hall 2 to check other entrances.

So, now we continue we find that there are 5, 6, and 8. So, we pick up 5 and see is not visited, we mark 5 again suspend 5. So, from 5, now we have 4, 6, and 7. So, we will now pick up 6 and suspend 5. From 6, we have 7, 5, 7, and 8; the 5 is already done, but 7 is not done. So, we will pick up 7 and suspend 6.

As we continue from vertex 4, we check each of its remaining unexplored neighbors (5, 6, and 8). We begin with vertex 5, marking it as visited and suspending it in the stack. Next, we check the neighbors of 5, which include vertices we have already visited (4) and those we haven't (6 and 7). We will now choose to explore vertex 6. We repeat the process of marking and suspending until we eventually find all vertices connected to 4.

It's similar to continuing your city exploration: after visiting the cafe (vertex 5), you realize the park (vertex 6) is nearby and ready to be explored. After finishing at the park, you check for any paths to new destinations—like another cafe (vertex 7) you haven’t visited from the park.

So, when we leaf 10 and I leave 9 at 15, I leave 8 at 16, I leave 7 at 17, I leave 5 at 18, and I come back to 4 and I have finally finish.

In this final stage, we see that each time we finish with a vertex that has no more unexplored neighbors, we backtrack up the stack, marking them as complete. The numbering of visits is crucial throughout this process. Eventually, we return to our starting point at vertex 4, confirming that we have explored all possible paths connected to it without missing any vertices.

Returning to the analogy, you finish exploring the entire city by visiting all the attractions in an order that ensures you don’t miss anything and end up back at your starting point. Just like exploring every venue and leaving no corner overlooked!

--