The last data structure that we will study in this section is the graph. Graphs are similar to trees except they do not have as many restrictions. In the previous lesson, we saw that every tree has a root node, and all the other nodes in the tree are children of this node. We also saw that nodes can have many children but only one parent. When we relax these restrictions, we get the graph data structure. The logical representation of a typical graph might look something like this:

Notice that our graph does not have a root node like the tree data structure did. Instead, any node can be connected with any other node. Nodes do not have a clear parent/child relationship like we saw in the tree. Instead nodes are called neighbors if they are connected by an edge. For example, node A above has three neighbors: B, C, and D.

It is not hard to imagine how the graph data structure could be useful for representing data. Perhaps each of the nodes above could represent a city and the edges connecting the nodes could represent roads. Or we could use a graph to represent a computer network where the nodes are workstations and the edges are network connections. Graphs have so many applications in computer science and mathematics that several algorithms have been written to perform standard graph operations such as searching the graph and finding the shortest path between nodes of a graph.

Now that you have a basic idea of the logical representation of graphs, let's take a look at one way that graphs are commonly represented in computers. The representation is called an adjacency matrix, and it uses a two-dimensional array to store information about the graph nodes. The adjacency matrix for our graph is given below.

  A B C D E F
A
B
C
D
E
F
-- 1 1 1 -- --
1 -- 1 -- 1 --
1 1 -- -- -- --
1 -- -- -- 1 1
-- 1 -- 1 -- --
-- -- -- 1 -- --

Notice that the matrix has six rows and six columns labeled with the nodes from the graph. We mark a '1' in a cell if there exists an edge from the two nodes that index that cell. For example, since we have a edge between A and B, we mark a '1' in the cells indexed by A and B. These cells are marked with a dark gray background in the adjacency matrix. With our adjacency matrix, we can represent every possible edge that our graph can have. The animation below will help you to get a better understanding of how the adjacency matrix works. Follow the instructions in the animation to create your own graphs and see how they are represented with an adjacency matrix.

[View in New Window]