Panicked Depth First Search: Part 7 of Ann's Visit to G'Raph

Depth first search is a search algorithm that fully explores a single path before backtracking to test other paths. The algorithm operates in a recursive way, first exploring all of the options down one subpath before considering other subpaths. For example, on a graph the algorithm will explore the neighbors of a neighbor before returning to original node to test other direct neighbors. Unlike breadth first search, which uses a queue based approach to track unexplored states, depth first search uses an approach based on a stack.

Ann realized that she had made a critical mistake almost as soon as she left the library. In her rush to get to the school, she had neglected to bring a map with her. In any other town, this would not have been a major problem -- she would just run in the general direction of the school. But finding your way around in G'Raph was not that simple.

Ann stopped when she reached Thomas's farm. There were two paths in front of her, and she was not sure which way led to the school. She looked around for the farmer, but Thomas was not in his radish patch.

Making a quick decision, Ann chose the path out of Thomas's farm that was on her right. She ran over the bridge, and found herself at the local pottery kiln. An assortment of bowls were lined up outside the kiln. Judging from the quality of craftsmanship at least a few of the bowls must have been made by third graders at the school. Ann hoped that she was getting close.

Now Ann had another decision to make -- two new paths led away from the kiln. Again Ann chose the path to her right, and she ran over the bridge. This time the result was less promising. Ann had come to a dead end. She was on an island that appeared to be a mud quarry. There were no new bridges that might take her to the school.

Ann backtracked quickly, returning to the pottery kiln island.

She then ran down another bridge, arriving at a carrot farm. It was another dead end.

Ann backtracked to the pottery kiln again. This time there were no more paths to take, so she backtracked further. She returned to Thomas's farm. From the farm, she took the other bridge and arrived at another (smaller) radish farm. From the looks of it, this farm was decidedly less successful than Thomas's farm. Ann paused for the briefest moment to wonder what could cause the difference in radish growing performance between two almost indistinguishable islands of mud. Maybe it had something to do with crop rotation strategies.

Yet again, Ann was faced with a choice of bridges. She started with the path to her right. Much to her relief, this bridge led directly to the school.

Ann ran up to the school. Florence and Edgar were already there. Their scooters were parked nearby, and Edgar held a folded map of G'Raph in his hand. Ann cursed herself again for not having brought a map. She could have saved a lot of backtracking.

"You made it!" exclaimed Edgar. "I was afraid that you would get lost without a map."

"I did get lost." admitted Ann. "Or at least, I hit a few dead ends and had to backtrack."

"Ah… a depth first search." noted Florence. "Nice."

"Depth first search?" asked Ann. She was still a little out of breath from all the running.

"Depth first search is when you keep exploring along one path until you hit either a dead end or a node that you have seen before. Then you backtrack to the most recent decision point and try a different option. If there are no new options at that point, then you backtrack again." explained Edgar.

"Think about searching a binary tree." suggested Florence. "With depth first search, you keep exploring deeper and deeper until you come to a dead end."

"Or find what you are looking for." added Edgar.

"Yes. Good point." replied Florence. "You can also find what you are looking for. Edgar, remember that time we used depth first search on that choose your own adventure novel?"

"Fun times." answered Edgar.

Ann just nodded. She was too tired to appreciate the algorithmic beauty of her own frantic run. A map would have saved her from having to experience depth first search first hand.

The school's principal, having seen the group standing outside, came out to see what was going on.

"Have you seen a strange man in a dark cloak?" asked Ann without bothering to introduce herself.

"Umm… yes. Why do you ask?" asked the principal.

"Did he talk to anyone?" asked Ann, ignoring the principal's question.

"Yes. He talked with one of our star students, Elizabeth. He had some question about some sort of math problem." answered the principal. "I was there too, but honestly could not understand what he was talking about. Elizabeth seemed certain that she could figure it out though. She went right home to work on it. She is very bright, you know. Probably the best scholar that our school has ever taught. She will find the answer."

"Do you know what the question was?" asked Ann.

"It was something about islands and bridges. I think he called it 'vertex covering'. I had not heard of it before, but it sounded like fun."

Ann felt her stomach drop. She was familiar with the vertex covering problem from her own time in school. Like the traveling salesman problem, it was unknown whether the vertex covering problem had an efficient solution. The problem fell into a class of NP-hard problems.

Unless Ann missed her guess, Elizabeth had just fallen victim to the same spell as Geoffrey. G'Raph High School's star student was a risk of becoming unnaturally obsessed with a single NP-hard problem.

So far, the wizard had targeted two star scholars. Unfortunately, Ann had no idea why.

To be continued in Part 8: Minimum Spanning Trees, Prim's Algorithm, and Bridge Upgrades...

Follow Ann's visit to G'Raph from the beginning with Part 1: The City of G'Raph.

--------------------

Find out more about breadth first search in: Breadth First Search and the Search for the Pig Thief.

Or find out about stacks and queues in: Stacks, Queues, Priority Queues, and the Prince's Complaint Line.