How it works...

Let's assume we are working with the following directed graph:

Figure 10.9

The adjacency list representation of this graph is as follows:

Figure 10.10

We define a structure called "node" comprising the following three members:

Figure 10.11

The user is prompted to specify the number of vertices. Assuming the user enters the value of 5, the value of 5 will be assigned to the numb variable. A startList pointer is defined as NULL. The whole adjacency list will be accessed through this startList pointer and it will be set to point to the first vertex of the graph. The user is first asked to enter the names of the vertices.

Initially, the startList pointer is NULL, so a new node called newNode is created and the vertex name, say a, entered by the user is assigned to the nme member of newNode. The startList pointer is set to point to newNode. To connect more vertices with newNode, the temp1 pointer is set to point to newNode. Initially, both the pointers, vrt and edg, are also set to NULL. Later, the vrt pointer will be set to point to other vertices and the edg pointer will be set to point to the vertices in which this current vertex is connected to. After the first iteration of the for loop, the node of the graph will look as follows:

Figure 10.12

In the second iteration of the for loop, because the startList pointer is no longer NULL, the else block will execute and, again, a new node is created, called newNode. Next, the vertex name is assigned to the named member of the newNode. Again, the vrt and edg pointers of newNode are set to NULL. To connect newNode to the earlier vertex, we will take the help of the temp1 pointer. The vrt pointer of the node, which is pointed to by the temp1 pointer, is set to point to newNode, as follows:

Figure 10.13

Then, the temp1 pointer is set to point to newNode, and the process is repeated for the rest of the vertices. Essentially, the temp1 pointer is used for connecting more vertices. At the end of the for loop, the nodes will appear connected as follows:

Figure 10.14

Once all the vertices of the graphs are entered, the user is asked to specify the edges between the vertices. Additionally, the user is asked to enter 0 0 when all the edges of the graph are entered. Suppose that the user enters a b to indicate there is an edge from vertex a to vertex b. The vertices are assigned to the v1 and v2 variables, respectively. We first ensure that the data in v1 and v2 is not 0. If yes, that means all the edges of the graph are entered and the program will jump to the statement from where the display of the adjacency list begins.

Then, to connect the a and b vertices, first, the temp1 pointer is set to point to startList. The temp1 pointer is set to find the node whose nme member is equal to the vertex entered in variable v1, that is, a. The temp1 pointer is already pointing to vertex a. Thereafter, you need to find the last node that is connected to temp1. The temp2 pointer is used for finding the last node connected to the node pointed to by temp1. Because this is the first edge being entered of vertex a, the edg member of the node pointed to by temp2 is already NULL. So, a new node is created called newNode, and the vertex name in variable v2, that is, b is assigned to the nme variable of newNode. The edg and vrt members of newNode are set to NULL, as follows:

Figure 10.15

The edg member of temp2 is set to point to newNode as follows:

Figure 10.16

The procedure is repeated for the rest of the edges entered by the user.

The program is compiled using GCC, as shown in the following screenshot. Because no error appears during the compilation, this means the adjlistdirect.c program has successfully compiled into the adjlistdirect.exe file. On executing the executable file, the user will be prompted to specify the number of vertices and their edges. Once the vertices and edges are entered, the program will display the adjacency list representation of the directed graph, as shown in the following screenshot:

Figure 10.17

Now, let's move on to the next recipe!