Category Archives: Examples

These are updates to my examples database.

Floyd-Warshall Shortest Paths

The Floyd Warshall algorithm is an all pairs shortest paths algorithm. This can be contrasted with algorithms like Dijkstra’s which give the shortest paths from a single node to all other nodes in the graph.

Floyd Warshall’s algorithm works by considering first the edge set of the graph. This is the set of all paths of the graph through one edge. Node pairs that are connected to one another through an edge will have their shortest path set to the length of that edge, while all other node pairs will have their shortest path set to infinity. The program then runs through every triplet of nodes (i, j, k) and checks if the path from i to k and the path from k to j is shorter than the current path from i to j. If so, then the distance and the path is updated.

So lets consider an example on the graph in the image above. The edge set of this graph is E = {(0, 1), (0, 2), (0, 3), (1, 3), (3, 4)}. So our initial table is:

  0 1 2 3 4
0 inf (0, 1) (0, 2) (0, 3) inf
1 (0, 1) inf inf (1, 3) inf
2 (0, 2) inf inf inf inf
3 (0, 3) (1, 3) inf inf (3, 4)
4 inf inf inf (3, 4) inf

As we look to update the paths, we first look for routes that go through node 0:

Because node 0 connects to both node 1 and node 2, but node 1 does not connect to node 2, we have the following truth holding in the matrix above:
cost(0, 1) + cost(0, 2) < cost(1, 2), so we can update the shortest path from node 1 to node 2 to be (1, 0, 2).

Because node 0 connects to both node 2 and node 3, but node 2 does not connect to node 3, we have the following truth holding in the matrix above:
cost(0, 2) + cost(0, 3) < cost(2, 3), so we can update the shortest path from node 2 to node 3 to be (2, 0, 3).

Because node 3 connects to both node 0 and node 4, but node 0 does not connect to node 4, we have the following truth holding in the matrix above:
cost(0, 3) + cost(3, 4) < cost(0, 4), so we can update the shortest path from node 0 to node 4 to be (0, 3, 4).

Because node 3 connects to both node 1 and node 4, but node 1 does not connect to node 4, we have the following truth holding in the matrix above:
cost(1, 3) + cost(3, 4) < cost(1, 4), so we can update the shortest path from node 1 to node 4 to be (1, 3, 4).

Because node 3 connects to both node 2 and node 4, but node 2 does not connect to node 4, we have the following truth now holding:
cost(2, 3) + cost(3, 4) < cost(2, 4), so we can update the shortest path from node 2 to node 4 to be (2, 0, 3, 4).

The final table giving the list of shortest paths from every node to every other node is given below.

  0 1 2 3 4
0 inf (0, 1) (0, 2) (0, 3) (0, 3, 4)
1 (0, 1) inf (1, 0, 2) (1, 3) (1, 3, 4)
2 (0, 2) (1, 0, 2) inf (2, 0, 3) (2, 0, 3, 4)
3 (0, 3) (1, 3) (2, 0, 3) inf (3, 4)
4 (0, 3, 4) (1, 3, 4) (2, 0, 3, 4) (3, 4) inf

To see more examples and to help answer questions, check out the script in my examples section on the Floyd-Warshall algorithm

Degree Centrality of a Graph

Degree Centrality Example

I wanted to spend some time on centrality measures of a graph. These are measurements of how important each node (or edge) is to the overall graph. But how do we define, or determine, importance? There is no unique way to answer this question, so there are varying metrics for measuring centrality. Which one you choose depends on several factors including how many other nodes of the graph are included, as well as the run time of the metrics you’re considering.

I have just published a script focusing on the degree centrality metric. The degree centrality metric is called a “walk metric” because it determines how important a node is by how many other nodes that can be reached by walks of up to a certain length. Lets look at the definition of the degree of a node to see if we can understand why it is called a walk metric.

In an undirected graph G = (V, E), the degree of a node u [in] V is the |{v | (u, v) [in] E}|. This is the size of the set of nodes that are connected to node u via a single edge. Another way of describing a single edge is a walk of length one. So the degree metric measures the importance of a node by the number of unique walks of length one.

The normalized degree centrality of a node v in a graph G = (V,E) measures how many nodes are connected to the node v, compared to the maximum possible number of edges that can be connected to this node. Because we are dealing with simple undirected graphs (at most a single edge between any two distinct vertices), this maximum possible number will always be |V – 1|. So the normalized degree can be calculated by dividing the degree of the node (the number of nodes it is connected to) by |V – 1|.

So for the example above, the node 0 has degree 6 because it is connected to nodes 2, 5, 9, 10, 11, and 12. There are 15 total nodes in this graph, so to calculate the normalized degree centrality of the node 0, it will be 6 / 14, which rounds to 0.428571.

To see more examples and to help answer questions, check out the script in my examples section on degree centrality

Tarjan’s Strongly Connected Components Algorithm

I just added a program that finds the strongly connected components of a graph using Tarjan’s Algorithm.

A strongly connected component of a graph is a subgraph S of G where every pair of nodes, u and v in S there is a path from u to v and a path from v to u.

To find these strongly connected components we implement Tarjan’s algorithm. The idea behind Tarjan’s algorithm is to begin by running a depth first search from an arbitrary node in the graph, labeling nodes reachable from this start node in the order they are reached. The algorithm is also interested in the “oldest” node that could be reached by a given node. This is indicated by the keeping track of the lowest label that can be reached from that node. We will call the first property label(v) and the second lowlink(v).

When the algorithm starts label(v) is the same as lowlink(v) whenever a node is discovered. As the algorithm is executed, the DFS is being run on each discovered node, which in turn updates the lowlink(v) property telling of (older) nodes that can be reached. If an older node can be reached, then we update lowlink. If we reach a node that cannot connect to any older nodes after the DFS call, i.e if label(v) is the same a lowlink(v), then this means that this node does not have a path to any node with a lower label. So this node will be the first node of a new strongly connected component.

Feel free to check it out an let me know what you think in the comments below.

Longest Common Subsequence

Suppose you and I each had an ordered list of items and we were interested in comparing how similar those lists are. One calculation we can perform on these two strings is the Longest Common Subsequence. A sequence X is an ordered list of elements <x1, …, xn>. A subsequence Z is another sequence where (1) Each element of Z is also an element of X and (2) The elements of Z occur in the same order (in Z) as they do in X.

Note that we do not say that the elements of Z need to be a continuous block of elements. If this were true we would be defining a substring. So as an example, suppose we have as an initial string,
X = C, O, M, P, U, T, E, R. 
Then the following are all subsequences: 
Z1 = C, M, U, T, R
Z2 = C, O, M, P
Z3 = U, T, E, R
Z4 = O, P, T, E

I will note that Z2 and Z3 are also substrings since they contain continuous sets of characters. 

The length of a substring is simply the number of characters it contains. So X has length 8, Z1 has length 5, Z2, Z3 and Z4 have length 4. 

Suppose now that we had a second string, Y = P, R, O, G, R, A, M, M, E, R and are interested in the longest common subsequence between the two. We can do that by observing that there is a bit of recursion going on with this question. What I mean by that is that asking the question of “What is the longest common subsequence between X and Y” is the same as asking “What is the longest common subsequence between X and Y once we have seen 8 characters of X and 10 characters of Y”

There are three possible ways to answer this question. 

If X<sub>8</sub> equals Y<sub>10</sub>, then we ask the same question about X<sub>7 and Y<sub>9</sub> and add 1 to the answer. 
If X<sub>8</sub> is not equal to Y<sub>10</sub>, then the answer to this will be the same as the maximum of the pair X<sub>7</sub>, Y<sub>10</sub> and the pair X<sub>8</sub>, Y<sub>9</sub>. 
If we reach a situation where we reach the beginning of either string, we are forced to answer 0 to that question. 

Then the function has the following look: 

LCS(Xi, Yj) =
0, if i is 0 or j is 0
1 + LCS(Xi-1, Yj-1) if Xi equals Yj
max(LCS(Xi-1, Yj), LCS(Xi, Yj-1))

Below is a table showing how we would solve the problem mentioned.

The strategy used to devise this concept is called dynamic programming. It is useful we can solve larger problems by solving overlapping subproblems, as was the case here. In this situation we generally can store the data in a table form and avoid re-solving subproblems for which many larger problems will be dependent.

You can see this algorithm in action at LEARNINGlover.com: Longest Common Subsequece. Let me know what you think.

Independent Set Puzzles

In this post, I want to return to the idea of NP-Complete problems. There is a more technical, more formal definition that I can refer you to, but I like to refer to the images from Garey and Johnson’s “Computers and Intractability: A Guide to the Theory of NP Completeness”. The images helps to understand the difficulty of NP-Complete problems by presenting two images. The first image shows a single individual speaking to someone saying that he has been unable to solve the problem. The second image shows that same individual speaking to the same person behind the desk, but saying that not only was he unable to solve the problem but neither was a long line of people. The theory of NP Complete problems revolves around the concept that if an efficient algorithm exists for an NP-Complete problem, then an efficient algorithm exists for all problems in the class NP.

Today, I would like to present a puzzle I created to play with the Independent Set problem. This is the problem where we are given a graph G = (V, E) and are asked to find a maximum set of vertices S such that there is no edge in the graph G between any two vertices in S. The decision version (the problem asking whether there is an independent set of size k) of this problem is NP-Complete, so the known algorithms for problem either have a slow running time, or do not solve it exactly.

This problem is very related to another puzzle I posted last year called the clique problem. In fact, Karp originally proved that Clique was NP-Complete by showing that if Clique could be solved efficiently, then Independent Set could be solved efficiently. He did this by constructing a second graph [G bar], called the compliment of G (containing the same vertices in G, along with the edges that are not present in G. Any edge present in G will not be present in ). Then he showed that the nodes representing a maximum clique in G would represent a maximum independent set in . He had already shown that Independent Set was NP-Complete, which meant that both Independent Set and Clique were among the most difficult problems within the class known as NP.

The puzzle begins with an undirected graph and asks users to find a maximum independent set. Users should click on the numbers in the table below the graph indicating the nodes they wish to select in their independent set (purple indicates that the node is selected, gray indicates that it is not). Once a user have a potential solution, they can press the “Check” button to see if their solution is optimal. If a user is having trouble and simply wishes to see the maximum independent set, they can press the “Solve” button. And to generate a new problem, users can press the “New Problem” button.As a result of this relationship between the Clique problem and the Independent Set problem, the Bron-Kerbosch algorithm that was used to find maximum cliques previously can also be used here.

Lets Learn About XOR Encryption

One of the more common things about this generation is the constant desire to write up (type) their thoughts. So many of the conversations from my high school days were long lasting, but quickly forgotten. Today’s generation is much more likely to blog, tweet, write status updates or simply open up a notepad file and write up their thoughts after such a conversation.

When we feel that our thoughts are not ready for public eyes (maybe you want to run your idea by the Patent and Trademark Office before speaking about it) we may seek some form of security to ensure that they stay private. An old fashioned way of doing this was to write in a diary and enclosed it within a lock and key. The mathematical field of encryption also tries to grant privacy by encoding messages so that only people with the necessary information can read them.

The type of encryption I want to speak about today is called XOR encryption. It is based on the logical operation called “exclusive or” (hence the name XOR). The exclusive or operation is true between two logical statements if exactly one of the two statements is true, but not both statement. This can be represented with the following truth table

Input 1 Input2 XOR Result
T T F
T F T
F T T
F F F

XOR Encryption is particularly useful in this day and age because we every character we type is understood by the computer as a sequence of zeros and ones. The current standard encoding that is used is Unicode (also known as UTF-8). Under this encoding the letter ‘a’ is represented as the binary string ‘01100001’. Similarly every letter, number and special character can be represented as its own binary string. These binary strings are just an assignment of numbers to these characters so that we can to help represent them in the computer. The numbers can the be thought of in base 10, which is how we generally think about numbers, or in base 2 which is how computers generally work with numbers (or a number of other ways). The way we would use these binary strings in encoding is first by translating a text from human-readable text to machine readable text via its binary string. For example, the word “Invincible”, we would get the following binary strings:

Letter Unicode in base 10 Unicode in base 2
I 73 01001001
n 110 01101110
v 118 01110110
i 105 01101001
n 110 01101110
c 99 01100011
i 105 01101001
b 98 01100010
l 108 01101100
e 101 01100101

To encrypt the message we need a key to encode the message and will simply perform an XOR operation on the key and every character in the string. Similarly, do decrypt the message we perform XOR operation on the key and every character in the encoded message. This means that the key (much like a normal key to a diary) must be kept private and only those whom the message is to be shared between have access to it.

Here is a link to the script where you can check out XOR Encrpytio. Try it out and let me know what you think.

Discrete-time Markov Chains

Much of how we interact with life could be described as transitions between states. These states could be weather conditions (whether we are in a state of “sunny” or “rainy”), the places we may visit (maybe “school”, “the mall”, “the park” and “home”), our moods (“happy”, “angry”, “sad”). There are a number of other ways to model states and even the possibility of infinitely many states.

Markov Chains are based on the principle that the future is only dependent on the immediate past. so for example, if I wished to predict tomorrow’s weather using a Markov Chain, I would need to only look at the weather for today, and can ignore all previous data. I would then compare the state of weather for today with historically how weather has changed in between states to determine the most likely next state (i.e what the weather will be like tomorrow). This greatly simplifies the construction of models.

To use Markov Chains to predict the future, we first need to compute a transition matrix which shows the probability (or frequency) that we will travel from one state to another based on how often we have done so historically. This transition matrix can be calculated by looking at each element of the history as an instance of a discrete state, counting the number of times each transition occurs and dividing each result by the number of times the origin state occurs. I’ll next give an example and then I’ll focus on explaining the Finite Discrete State Markov Chain tool I built using javascript.

Next, I want to consider an example of using Markov Chains to predict the weather for tomorrow. Suppose that we have observed the weather for the last two weeks. We could then use that data to build a model to predict tomorrow’s weather. To do this, lets first consider some states of weather. Suppose that a day can be classified in one of four different ways: {Sunny, Cloudy, Windy, Rainy}. Further, suppose that over the last two weeks we have seen the following pattern.

Day 1 Sunny
Day 2 Sunny
Day 3 Cloudy
Day 4 Rain
Day 5 Sunny
Day 6 Windy
Day 7 Rain
Day 8 Windy
Day 9 Rain
Day 10 Cloudy
Day 11 Windy
Day 12 Windy
Day 13 Windy
Day 14 Cloudy

We can look at this data and calculate the probability that we will transition from each state to each other state, which we see below:

Rain Cloudy Windy Sunny
Rain 0 1/3 1/3 1/3
Cloudy 1/2 0 1/2 0
Windy 2/5 1/5 2/5 0
Sunny 0 1/3 1/3 1/3

Given that the weather for today is cloudy, we can look at the transition matrix and see that historically the days that followed a cloudy day have been Rainy and Windy days each with probability of 1/5. We can see this more mathematically by multiplying the current state vector (cloudy) [0, 1, 0, 0] by the above matrix, where we obtain the result [1/2, 0, 1/2, 0].

In similar fashion, we could use this transition matrix (lets call it T) to predict the weather a number of days in the future by looking at Tn. For example, if we wanted to predict the weather two days in the future, we could begin with the state vector [1/2, 0, 1/2, 0] and multiply it by the matrix T to obtain [1/5, 4/15, 11/30, 1/6].

We can also obtain this by looknig at the original state vector [0, 1, 0, 0] and multiplying it by T2.

T2 =

1

3/10 8/45 37/90 1/9
1/5 4/15 11/30 1/6
13/50 16/75 59/150 2/15
3/10 8/45 37/90 1/9

When we multiply the original state vector by T2 we arrive at this same answer [1/5, 4/15, 11/30, 1/6]. This matrix T2 has an important property in that every state can reach every other state.

In general, if we have a transition matrix where for every cell in row i and column j, there is some power of the transition matrix such that the cell (i, j) in that matrx is nonzero, then we say that every state is reachable from every other state and we call the Markov Chain regular.

Regular Markov Chains are important because they converge to what’s called a steady state. These are state vectrs x = [x0, …, xn] such that xTn = x for very large values of n. The steady state tells us how the Markov Chain will perform over long periods of time. We can use algebra and systems of linear equations to solve for this steady state vector.

For the Javascript program I’ve written, I have generated a set of painting samples for a fictional artist. The states are the different colors and the transitions are the colors that the artist will use after other colors. as well as the starting and ending colors. Given this input, we can form a Markov Chain to understand the artist’s behavior. This Markov Chain can then be used to solve for the steady state vector or to generate random paintings according to the artist’s profile. Be sure to check it out and let me know what you think.

Topological Sort

One of the things I generally say about myself is that I love learning. I can spend hours upon hours reading papers and algorithms to better understand a topic. Some of these topics are stand alone segments that I can understand in one sitting. Sometimes, however, there is a need to read up on some preliminary work in order to fully understand a concept.

Lets say that I was interested in organizing this information into a new course. The order I present these topics is very important. Knowing which topics depend on one another allows me to use the topological sorting algorithm to determine an ordering for the topics that respects the preliminary work.

The input for the topoligical sorting algorithm is a Directed Acyclic Graph (DAG). This is a set of relationships between pairs of topics, where if topic 1 must be understood before topic 2, we would add the relationship (topic 1, topic 2) to the graph. DAGs can be visualized by a set of nodes (points) representing the topics. Relationships like the one above (topic 1, topic 2) can then represented by a directed arc originating at topic 1 and flowing in the direction of topic 2. We say that the graph is “Acyclic” because there cannot be a cycle in the topic preliminaries. This amounts to us saying that a topic cannot be a prerequisite for itself. An example of a DAG is shown in the image above.

With the topics represented as a DAG, the topologial ordering algorithm works by searching the set of nodes for the one with no arcs coming into it. This node (or these nodes is multiple are present) represents the topic that can be covered next without losing understanding of the material. Such a node is guaranteed to exist by the acyclic property of the DAG. Once the node is selected, we can remove this node as well as all arcs that originate at this node from the DAG. The algorithm then repeats the procedure of searching for a nod with no arcs coming into it. This process repeats until there are no remaining nodes from which to choose.

Now lets see how the topological sort algorithm works on the graph above. We will first need to count the in-degree (the number of arcs coming into) each node.

Node | Indegree
—————-
0 | 2
1 | 2
2 | 0
3 | 2
4 | 2
5 | 2
6 | 0
7 | 2
8 | 3

Node to be removed (i.e. node with the minimum indegree): Node 2.
Arcs connected to node 2: (2, 5), (2, 3)
Resulting Indegree Count:
Node | Indegree
—————-
0 | 2
1 | 2
3 | 1
4 | 2
5 | 1
6 | 0
7 | 2
8 | 3

Node to be removed: Node 6:
Arcs connected to node 6: (6, 1), (6, 3), (6, 4), (6, 5), (6, 7), (6, 8)
Resulting Indegree Count:
Node | Indegree
—————-
0 | 2
1 | 1
3 | 0
4 | 1
5 | 0
7 | 1
8 | 2

Node to be removed: Node 3
Arcs connected to node 3: (3, 0), (3, 8)
Resulting Indegree Count:
Node | Indegree
—————-
0 | 1
1 | 1
4 | 1
5 | 0
7 | 1
8 | 1

Node to be removed: Node 5
Arcs connected to node 5: (5, 0), (5, 8)
Resulting Indegree Count:
Node | Indegree
—————-
0 | 0
1 | 1
4 | 1
7 | 1
8 | 0

Node to be removed: Node 0:
Arcs connected to node 0: (0, 1), (0, 4)
Resulting Indegree Count:
Node | Indegree
—————-
1 | 0
4 | 0
7 | 1
8 | 0

Node to be removed: Node 1
Arcs connected to node 1: none
Resulting Indegree Count:
Node | Indegree
—————-
4 | 0
7 | 1
8 | 0

Node to be removed: Node 4
Arcs connected to node 4: none
Resulting Indegree Count:
Node | Indegree
—————-
7 | 1
8 | 0

Node to be removed: Node 8
Arcs connected to node 8: (8, 7)
Resulting Indegree Count:
Node | Indegree
—————-
7 | 0

Node to be removed: Node 7
Arcs connected to node 7: none
Resulting Indegree Count:
Node | Indegree
—————-

Since there are no nodes remaining, we have arrived at a topological ordering. Going through this iteration, we can see that we arrived at the ordering (2, 6, 3, 5, 0, 1, 4, 8, 7). There were several occasions where there were multiple nodes with indegree of 0 and we could have selected an alternative node. This would have given us a different topological ordering of the nodes, but it would still be valid.

There are more learning opportunities and an interactive demonstration of the algorithm at Topological Sort Examples at LEARNINGlover.

The RSA Algorithm

I can remember back when I was in school, still deciding whether I wanted to study pure or applied mathematics. One of the common questions I would receive from those in applied mathematical realms would sound like “What’s the point of doing mathematics with no real world applications?”. Generally my response to these questions was about the intrinsic beauty of mathematics, no different from an artist painting not for some desire to be a millionaire, but because of an burning desire to paint. Whether their paintings would one day be on the walls of a Smithsonian museum or sit on their mother’s refrigerator is generally outside of the thought process of the artist. So too, would I argue about the thought process of a pure mathematician.

When I was an undergrad and learned about the RSA algorithm (named for Ron Rivest, Adi Shamir, and Leonard Adleman who discovered the algorithm) it helped me explain this concept a lot better. The algorithm is based on prime numbers and the problem of finding the divisors of a given number. Many mathematicians throughout the ages have written papers on the beauty of prime numbers (see Euclid, Eratosthenes, Fermat, Goldbach, etc). For a large period in time one of the beautiful things about prime numbers was that they were so interesting in themselves. There were questions about how to check if a number is prime, question of patterns in primes, famous conjectures like the Goldbach conjecture and the twin prime conjecture, quick ways of finding prime numbers or numbers that are almost always prime, etc. In short, this was an active area of research that much of the applied world was not using. This all changed in 1977 when Rivest, Shamir and Adleman published the RSA algorithm.

The algorithm is in the area called public key cryptography. These algorithms differ from many of the previous cryptography algorithms, namely symmetric key cryptography. Whereas symmetric key cryptography depends uses the same device (key) to encode as to decode, public key cryptography creates two keys – one for encoding that is generally shared with others, and another for decoding which is kept private. These two keys in generally relate to a mathematical problem that is very difficult to solve.

In my example script for the RSA Algorithm, I show two people who want to communicate, Alice and Bob. Bob wants people to be able to send him messages securely so he decides to use the RSA algorithm. To do this, he first needs to think of two prime numbers, p1 and p2.
From these, he computes the following:
n = p1 * p2

Next, he computes Euler’s function on this n which can be calculated as
(n) = (p1 – 1) * (p2 – 1)

Then Bob looks for a number e that is relatively prime to . This is what he will use as the encryption key.

One he has e, he can calculate d, which is the multiplicative inverse of e in (n).
This means that e * d = 1 (mod (n)).

The public key that will be used for encryption will be the pair (e, n). This is what he posts publicly via his web page for others to communicate with him securely. Bob also has a private key pair (d, n) that he will use to decrypt messages.

Alice sees Bob’s public key and would like to communicate with him. So she uses it to encode a message. The formula she uses to encrypt her message is c = me mod n, where c is the encrypted message. Once Alice encrypts her message, she sends it to Bob.

Bob receives this encoded message and uses the private key (d, n) to decode the message from Alice. The formula to decrypt is m = cd mod n.

For a more illustrative idea of how this algorithm works as well as examples, be sure to visit Script for the RSA Algorithm.

The Depth-First-Search Algorithm

I remember when I was younger I used to play the game of hide-and-seek a lot. This is a game where a group of people (at least two) separate into a group of hiders and a group of seekers. The most common version of this that I’ve seen is having one person as the seeker and everyone as hiders. Initially, the seeker(s) is given a number to count towards and close their eyes while counting. The hiders then search for places to hide from the seeker. Once the seeker is finished counting, their job is to find where everyone is hiding or admitting that they cannot find all the seekers. Any seekers not found are said to have won, and seekers that are found are said to have lost.

I played this game a number of times in my childhood, but I remember playing it with a friend named Dennis in particular. Dennis had a certain way he played as seeker. While many of us would simply go to places we deemed as “likely” hiding spots in a somewhat random order, Dennis would always begin by looking in one area of the room, making sure that he had searched through every area connected to that area before going to a new area. He continued this process until he either found everybody or concluded that he had searched every spot he could think of and gave up.

It wasn’t until years later that I was able to note the similarity between Dennis’s way of playing hide-and-seek and the Depth-First-Search algorithm. The Depth-First-Search Algorithm is a way of exploring all the nodes in a graph. Similar to hide-and-seek, one could choose to do this in a number of different ways. Depth-First-Search does this by beginning at some node, looking first at one of the neighbors of that node, then looking at one of the neighbors of this new node. If the new node does not have any new neighbors, then the algorithm goes to the previous node, looks at the next neighbor of this node and continues from there. Initially all nodes are “unmarked” and the algorithm proceeds by marking nodes as being in one of three states: visited nodes are marked as “visited”; nodes that we’ve marked to visit, but have not visited yet are marked “to-visit”; and unmarked nodes that have not been marked or visited are “unvisited”.

Consider a bedroom with the following possible hiding locations: (1) Under Bed, (2) Behind Cabinet, (3) In Closet, (4) Under Clothes, (5) Behind Curtains, (6) Behind Bookshelf, and (7) Under Desk. We can visualize how the bedroom is arranged as a graph and then use a Breadth First Search algorithm to show how Brent would search the room. Consider the following bedroom arrangement, where we have replaced the names of each item by the number corresponding to that item. Node (0) corresponds to the door, which is where Dennis stands and counts while others hide.

Bedroom Items as a Graph

Now consider how a Breadth First Search would be run on this graph.

Bedroom Items as a Graph Colored by DFS

The colors correspond to the order in which nodes are visited in Depth-First-Search.

The way we read this is that initially Dennis would start at node 0, which is colored in Blue.
While Dennis is at node 0, she notices that nodes 1, 5, and 6 (under bed, behind curtains, and behind bookshelf) are the nearby and have not been checked yet so she places them on the “to visit” list.
Next, Dennis will begin to visit each node on the “to visit” list, and when a node is visited, she labels it as visited. At each location, she also takes note of the other locations she can reach from this location. Below is the order of nodes Dennis visits and how he discovers new locations to visit.

Order Visited Node Queue Adding Distance From Node 0
1 0 6,5,1 0
2 6 5,1 7,3,2 1
3 7 3,2,5,1 2
4 3 2,5,1 2
5 2 5,1 4 2
6 4 5,1 3
7 5 1 1
8 1 1

Here is a link to my Examples page that implements the Depth-First-Search Algorithm on Arbitrary Graphs.