![]](http://coweb.math.gatech.edu:8080/files/schemes/math/after.gif)
Graphs and Trees (Shortest Distance,Searching Algorithms, and Minimum Spanning) by Jonathan Stewart
I. Introduction
A. Graphs
A graph consists of nodes connected by edges. The most common application of graphs are by representing maps.
For instance, one node (sometimes called a vertex) could represent Atlanta, while another represents San Diego.
The line connecting them would be the distance between them, as shown in the Figure below:
This graph is very simple, but also serves to illustrate the difference between a Directed and undirected graph. The graph above is undirected because the arrows point in either direction.
Thus, according the graph, it is possible to travel from Atlanta to San Diego and vice versa. If the arrow had only pointed in the direction of San Diego, then that would be the only
possible direction of travel. It would therefore become a directed graph.
For a graph to be considered connected, one must be able to travel to any node from any node. That means that the graph above is connected, whereas the
graph below is NOT connected since you cannot travel from Atlanta to Chicago or New York for instance.
B. Trees
A tree is a graph in which every item can be traced to a single origin using a single path(Dictionary.com). All trees are graphs, but all graphs are NOT trees.
An example of a tree is shown below. It is an example of a Binary Tree, because each node branches into 2 child nodes (also called leaves).
Aside from the Minimum Spanning Tree problems, trees are worth mentioning because they have applications for such things as Game Theory,
as we have seen in class with Poker analysis.
II. Finding the Shortest Distance
This is probably one of the most common applications of graph theory. If you wanted to drive from Miami to Seattle, chances are you wouldn't ever want to
see a sign welcoming you to the Empire State. This is the logic behind services like Mapquest.com, which show you the shortest distance between two locations.
Mapquest calculates the distance between the intermediate cities and finds which ones you need to pass through to reach your destination the quickest. This is exactly
how we find the shortest distance, only we use nodes (or vertices) in place of actual cities.
We will use the figure below for analysis, which is also Figure 3.20 from page 242 of the 2nd Edition textbook.
We want to find the shortest distance between the starting and ending nodes, V0 and V7. The notation is as follows: d(VN) is the distance from V0 to VN.
If there is no connection between VN and V0, then d(VN)=infinity. If N=0, then d(VN) = d(V0) = 0. Also remember that traversal of the graph can ONLY include tail to head travel.
In this example for instance, you can go from V0 to V1, but not vice versa.
To accomplish this task we have to first break it down into smaller pieces. We must calculate the shortest possible distance from V0 to each of the nodes:
Step by Step Calculations
The distance to V0 from V0 is 0, so d(V0) = 0.
Next we have V1. The distance from V0 to V1 is 2, so d(V1) = 2.
In the same way, we see that the distance from V0 to V2 is 4, this d(V2)=4.
There are two ways to get to V3, either by V1 or V2. So we must compare d(V1) + 3 = 5 and d(V2) + 3 = 7.
We can conlude from this that it is short to travel through V1. d(V3)=5.
Using the same method as before, we find that d(V4)= 5 as we travel through V2 to get there.
From the same method we also find that d(V5)=6, d(V6)=7, and d(V7)=8.
We can see that the shortest path for this problem is V0,V1,V3,V5,V6,V7 for a total distance of 8 units, as we just calculated for the value of d(V7).
III. Minimum (Spanning) Trees
Minimum Spanning Tree problems can be thought of like a computer network. The goal is to find the most cost effective way to connect every node to the network.
Obviously every computer, or node, doesn't have to be connected to everything else, it only needs some path to exist between the two, no matter how many intermediate
nodes exist between them.
The two methods of finding this optimal network are via Prim's algorithm and Kruskal's algorithm. Both create an acycle tree as a result.
A. Prim's Algorithm
Given the tree below, we want to find the minimum tree using Prim's method.
Prim's algorithm works by first choosing any node. For this case let's pick the middle one, but you can begin anywhere. From here we begin connecting to other nodes via the
shortest (or least cost) way. So from the middle node we see that the adjacent nodes have distance 2,3,7,8. We choose 2 because it is the smallest. Then from the new node we see
that 1 is the shortest. We continue this process of seeking out the shortest distances between nodes, while still being cautious not to form a cycle.
After this process is complete we end up with the result below (in Blue). This method can be repeated for any undirected tree, as in the example.
B. Kruskal's Algorithm
Kruskal's algorithm works by ordering the edge distance from least to greatest and then making the connections:
d(e_1)<= d(e_2) <= ....<= d(e_n)
The figure below shows a new tree. We will use this one as an example to illustrate how Kruskals algorithm works.
You can see that the shortest edge is 1, near the top of the graph. From here we trace all of the shorest distances, as we ranked them, thus the edge with
distance 1 is connected to 2, which is connected to 3, to 4, etc...
This process would essentially yield the same results as the previous algorithm. The only real difference would be the order in which the nodes are
added to the new tree. Below you can see the final tree outlined in blue.
IV. Searching
A. Breadth First Search (BFS)
BFS is analogous to the following situation:
Imagine you are in a dark room and need to find something, let's say a ball. One way to look for the ball is to start at the door and look at the entire
area around you within arms length. If you don't find it, move forward and repeat until you feel the ball in front of you or run into the back wall and decide
the ball isn't there at all.
To better understand the actual process, let's do a real example with the figure below.
Beginning with node A, we will use the Breadth First Search Algorithm to find the node marked "J".
First we begin at A. A is not J, so we move on to examine nodes B, C, and D. None of these are equal to J,so we continue the process until we find J.
As we continue, we look at nodes E, F, G and continue the same process.
We end up with a list of visited nodes, which are as follows: A,B,C,D,E,F,G,H,I,J.
Had we been looking for node "Z", our list would have been A,B,C,D,E,F,G,H,I,J, and we would not have found the item.
As you can see, we begin searching the nodes adjacent to our current position, then move out one step, examine all the newly adjacent
nodes, etc... as you can see by the listed nodes. This example makes it easy to see how the process works.
B. Breadth First Search (BFS)
DFS differs from BFS in that rather from beginning at the doorway to find the missing ball in the dark room, you immediately move to the
back of the room, examining everything in the way. If you don't find the ball, you go back to the doorway, pick a new direction, and walk to the back
of the room again.
Again we will look at the same tree to analyze exactly what path the algorithm would take when using DFS, and again, we will be
searching for node "J".
First we evaluate the first node A. A is not J, so we move down to B. B is not J, so we move to E. Since E is obviously not J either,
we return to A again, but this time move down to C. From here we proceed to the left once more as far as we can go, this making us evaluate F, H,I, and J. J is equal to J, so we can end the search.
The result of using the Depth First Search algorithm is that our list of visited nodes becomes: A,B,E,C,F,H,I,J
For this particular situation, it seems that DFS proves to be faster.
Outside Links
For a more visual version of BFS and DFS, refer to the Fall 2003 CS1321 Lecture Slides, located here:
http://www.cc.gatech.edu/classes/AY2004/cs1321_fall/lecture/CS1_28_DFSBFSgraphs.ppt
