|
The last data structure that we will study in this tutorial is the graphs. Graphs are similar to trees except that, they do not have as many restrictions. In the previous tutorial, we saw that every tree has a root node, and all the other nodes in the tree are children of a perticular node. We also saw that the 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 the figure shown below:
Notice that our graph does not have any root node like the tree data structure. Instead, any node can be connected with any other node in the graph. Nodes do not have any clear parent-child relationship like we saw in the tree. Instead nodes are called as 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 the data. Perhaps each of the nodes above could represent a city and the edges connecting the nodes could represent the roads. Or we could use a graph to represent a computer network where the nodes are workstations and the edges are the network connections. Graphs have so many applications in the computer science and mathematics that several algorithms have been written to perform the 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 the 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 the two-dimensional array to store the information about the graph nodes. The adjacency matrix for our graph is given below.
|
