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.

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.

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.

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.

Notice that the matrix shown above 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 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.