Introduction

In this article we will discuss another important non-linear data structure – Graph. Graphs are used to represent relationship between pairs of elements, which are not necessarily hierarchical in nature. In this article we will study the representation of graphs, operations on them, shortest path problems and several applications of graphs, including topological sorting.  Firstly we will define some of the important terms which are associated with graphs.

Definition and Terminology

A graph is a 2-tuple (V,E) such that V is a set of vertices and E is a set of edges. We write it as:

G = (V,E) where V={v1, v2, …., vn) and E={e1, e2, …., en)

Here E is a set of pairs of vertices and these pairs are called edges.

Figure 1

The graph, shown in figure-1, has the following set of vertices and set of edges:

V = {V1, V2, V3, V4, V5}
E = { e1, e2, e3, e4, e5, e6, e7}

Now let us take a simple graph as shown in figure-2.

Figure 2

In this figure-2 we have numbered the nodes 1, 2, 3, 4, 5, and 6. Therefore you can represent V and E as:

V(G) = {1,2,3,4,5,6} and    E(G) = {(1,2), (1,4), (1,3), (2,4), (2,5), (4,5), (3,6), (4,6)}

This graph is also called as undirected graph. In an undirectd graph the edge incident with node 1 and node 2 can be written as (2,1). However you can also have a directed graph in which each edge is represented in an ordered pair of vertices. Thus for a directed graph an edge e=(v,w) means that an edge e has ‘v’ as initial vertex and ‘w’ as final vertex.

Figure-3 shows a general example of a directed graph.

Now let us study some basic terminology that are more frequently used when we will study graphs.

Adjacent Vertex

If e=(u, v) is an edge in an undirected graph then the vertex u and v are called adjacent vertex.

Incidence Vertex

If e=(u, v) is an edge in an undirected graph then e is said to be incident on vertex u and v.

Degree

The number of edges incident on a vertex determines its degree. The degree of a vertex u is written as:

degree(u)

If vertex u does not belong to any edge then its degree can be represented as: degree(u)=0. However if you have a directed graph then its degree can be of two types indegree and outdegree and in this case
Degree of a vertex is equal to indegree plus outdegree.

Isolated Vertex

If a vertex has no edge then it is called as an isolated vertex. An isolated vertex has zero degree.
Null Graph

If a graph has null set of vertices then it is called as null graph.

Connected Graph

A graph is said to be connected if there is a path from every vertex to every other vertex; otherwise the graph is not connected. If there is an edge between very pair of vertices in a graph then the graph is called strongly connected.

Weighted Graph

A graph is said to be weighted if every edge in the graph is assigned some weight or value. This weight can represent any positive value.

Path

A path from a vertex vi to vj is a sequence of vertices v1, v2, …. such that (vi, vi +1) is an edge where i varies from 1 to j-1 and all edges are distinct.

Cycle

A path in which the initial vertex and the final vertex are same is called a cycle.

Sub Graph

A graph ‘g’ is said to be sub graph of a graph ‘G’ if all the vertices and edges of ‘g’ are in ‘G’.

3 Representation of Graphs in C

Graph can be represented by using a two-dimensional array (matrix) or a linked list. Firstly we will study various matrix related techniques for graph representation.

• Incidence Matrix

In this we take a matrix, such that if G=(V,E) represents a graph on ‘n’ vertices then the incidence matrix can be defined as:

Aij = 1 if the jth edge is incident to the ith vertex
= 0 otherwise

For example, let we have a graph, as shown in figure-4.

Figure-5 shows the incidence matrix of graph shown in figure-4.

• Adjacency Matrix

In this we take a matrix, such that if G=(V,E) represents a graph on ‘n’ vertices then the adjacency matrix can be defined as:

Aij = 1 if (Vi, Vj) is an edge of G
= 0 otherwise

Figure-6 shows the adjacency matrix of graph shown in figure-4.

Using an adjacency matrix you can easily compute the degree of a vertex. For an undirected graph, the degree of a vertex Vi is the number of 1’s in the ith row. And for a directed graph, the degree of a vertex Vi is the number of 1’s in the ith column.

Adjacency List

In this representation we store a graph using a linked list. We store all the vertices in a list and then for each vertex we have a linked list of its adjacent vertices, that is the list for any vertex consists of the vertices adjacent to it.

For example, let we have a graph, as shown in figure-4. The adjacency list of this graph is as shown in figure-7.

This adjacency list is for an undirected graph. However if you have a directed graph, as shown in figure-8

Figure 8

then its adjacency list will be as shown in figure-9

Implementation of an Adjacency List

To implement an adjacency list we use a linked list of nodes. The definition of a node of an adjacency list is as:

struct GraphNode
{
 int vertex;
 struct GraphNode *link;
};

Here each graph node consists of an integer field (information) that contains the node number and a link field contain that contains the address of another graph node.

To simplify this we use following statement:

typedef struct GraphNode GraphNode;

Since there can be any number of nodes in a linked list therefore we declare an array of GraphNode as:

GraphNode *adj[Size];

Here Size specifies total number of nodes in a graph.

Here is the function that creates an adjacency list of a graph.

Implementation : AdjList

AdjList(GraphNode *adj[], int n)
{
 GraphNode *temp, *current;
 int i,j,value,num;
 printf("\nCreating an Adjacency lists of a Graph.\n");
 for(i=1; i<=n; i++)
 {
 printf("\nNode number %d: ",i);
 printf("\nEnter the number of nodes in the adjacency list  of nodes %d :", i);
 scanf("%d",&num);
 for(j=1; j<=num; j++)
 {
 printf("Enter node number %d: ",j);
 scanf("%d", &value);
 temp = getnode();
 if (temp==NULL)
 {
 printf("\nError. ");
 return;
 }
 temp->vertex=value;
 temp->link=NULL;
 if (adj[i] == NULL)
 adj[i]=temp;
 else
 current->link = temp;
 current = temp;
 } }}

Here we have used a function getnode(). This function is used to create a node dynamically. The function definition of this getnode() function is as:

GraphNode *getnode()
{
 GraphNode *t;
 t = (GraphNode *)malloc(sizeof(GraphNode));
 return t;
}

Once you create an adjacency list, it showl be displayed. Here is the function that displays an adjacency list.

Implementation : DisplayGraph

DisplayGraph(GraphNode *adj[], int n)
{
 GraphNode *current;
 int i;
 printf("\nContents of an Adjacency list are as....\n");
 for(i=1; i<=n; i++)
 {
 printf("\nNode %d: ",i);
 current=adj[i];
 while (current != NULL)
 {
 printf("--> %d ", current->vertex);
 current=current->link;
 }
 printf("-->NULL");
 }}

Operations on Graphs

There are two major operations that we can perform on graphs – insertion and deletion. But before using a graph, one must initialize it. Now let us study these operations one by one.

Initialization of an Adjacency List

While initializing an adjacency list we must set NULL to all adjacency list. Here is the implementation of this function.

InitializeGraph(GraphNode *adj[], int n)
{
 int i;
 for(i=1; i<=n; i++)
 adj[i] = NULL;
}

Insertion into a Graph

When somebody tells you to perform insert operation in a graph, then there are two possibilities:

• Inserting an edge into a Graph
• Inserting a node into a Graph

Inserting an edge into a Graph

When we insert an edge it is necessary to specify the node number to which this edge is being connected. For example, let we want to insert an edge between nodes ‘x’ and ‘y’. For this firstly we create two nodes and then update the adjacency list.

Here is the algorithm that implements this task.

Algorithm : InsertEdge

InsertEdge(adj[], x, y)

Here ‘adj’ is an array of graph nodes and ‘x’ and ‘y’ are the nodes between which a new edge is being inserted. Parameter ‘adj’ passed be reference (pointer to pointer) to allow it to change during insertion of a new edge.

Step-1 : Create two graph nodes temp1 and temp2
Step-2 : Set temp1->vertex=y
Step-3 : Set temp1->link=adj[x]
Step-4 : Update the value of ‘adj[x]’ as adj[x]=temp1
Step-5: Set temp2->vertex=x;
Step-6 : Set temp2->link=adj[y];
Step-7 : Update the value of ‘adj[y]’ as adj[y]=temp2;
Step-8 : Exit

Here is the ‘C’ implementation of this algorithm.

Implementation : InsertEdge

InsertEdge(GraphNode *adj[], int x, int y)
{
 GraphNode *temp1,*temp2;
 temp1 = getnode();
 if (temp1==NULL)
 {
 printf("\nUnable to create a new node. Press any key to continue....");
 return;
 }
 temp2 = getnode();
 if (temp2==NULL)
 {
 printf("\nUnable to create a new node. Press any key to continue....");
 freenode(temp1);
 return;
 }
 temp1->vertex=y;
 temp1->link=adj[x];
 adj[x]=temp1;
 temp2->vertex=x;
 temp2->link=adj[y];
 adj[y]=temp2;
}

Inserting a node into a Graph

When we want to insert a new node to graph then its adjacency list is updated as:

InsertNode(GraphNode *adj[], int T)
{
 adj[T] = NULL;
}

Deletion from a Graph

Like insertion we can have following delete operation in a graph:

• Deleting an edge from a graph
• Deleting a node from a graph.

Deleting an edge from a Graph

When we want to delete an edge we have to specify the node numbers to which this edge is connected. For example, let we want to delete an edge between the nodes ‘x’ and ‘y’. once we delete an edge it becomes necessary to update adjacency list.

Here is the algorithm that deletes an edge from a graph.

Algorithm : DeleteEdge

DeleteEdge(adj[], x, y)

Here ‘adj’ is an array of graph nodes and ‘x’ and ‘y’ are the nodes between which an edge is being deleted. Parameter ‘adj’ passed be reference (pointer to pointer) to allow it to change during deletion of an edge.

Perform the following steps if  (adj[x] != NULL)
Step-1 : Reset flag=False
Step-2 : Check if (adj[x]->vertex == y) then go to step-3;
Otherwise go to step-5
Step-3 : Set current=adj[x] and update the value of ‘adj[x]’ as:
adj[x]=adj[x]->link;
Step-4 :     Set flag=True and go to step-10
Step-5 : Set current = adj[x]
Step-6 : Repeat through step- 9 while (current != NULL)
Step-7 : Set previous = current and current=current->link;
Step-8 : If (current->vertex == y) then set                                previous->link = current->link
Otherwise go to step-6
Step-9 : Set flag=True and go to step-10
Step-10 : Check if (flag==True) then go to step-11 ;
Otherwise go to step-20
Step-11 : Check if (adj[y] == NULL) then print an error message
And go to step-20
Step-12 : Check if (adj[y]->vertex == x) then go to step-13;
Otherwise go to step-15
Step-13 : Set current=adj[y] and update the value of ‘adj[y]’ as
adj[y]=adj[y]->link
Step-14 : Set flag=True and go to step-20
Step-15 : Set current = adj[y]
Step-16 : Repeat through step-19 while (current != NULL)
Step-17 : Set previous = current and current=current->link;
Step-18 : If (current->vertex == x) then set previous->link = current->link
Otherwise go to step-16
Step-19 : Set flag=True 
Step-20 : Exit

The ‘C’ implementation of this algorithm is as:

Implementation : DeleteEdge

DeleteEdge(GraphNode *adj[], int x, int y)
{
 GraphNode *temp, *current, *previous;
 int flag;
 flag=False;
 if (adj[x] == NULL)
 {
 printf("\nIllegal edge. Press any key to continue....");
 return;
 }
 if (adj[x]->vertex == y)
 {
 current=adj[x];
 adj[x]=adj[x]->link;
 freenode(current);
 flag=True;
 }
 else
 {
 current = adj[x];
 while (current != NULL)
 {
 previous = current;
 current=current->link;
 if (current->vertex == y)
 {
 previous->link = current->link;
 freenode(current);
 flag=True;
 break;
 } }}
 if (flag==True)
 {
 if (adj[y] == NULL)
 {
 printf("\nIllegal edge. Press any key to continue....");
 return;
 }
 if (adj[y]->vertex == x)
 {
 current=adj[y];
 adj[y]=adj[y]->link;
 freenode(current);
 flag=True;
 }
 else
 {
 current = adj[y];
 while (current != NULL)
 {
 previous = current;
 current=current->link;
 if (current->vertex == y)
 {
 previous->link = current->link;
 freenode(current);
 flag=True;
 break;
 }}}}}

Deleting a node from a Graph

When we delete a node then we firstly have to delete all the edges, which are incident to that node and then we delete this node.

Here is the algorithm that delete  a node from a graph.

Algorithm : DeleteNode

DeleteNode(adj[], n, m)

Here ‘adj’ is an array of graph nodes, ‘n’ is th total number of nodes in a graph and ‘m’ is the node which is being deleted. Parameter ‘adj’ passed be reference (pointer to pointer) to allow it to change during deletion of a node.

Step-1 : Set current = adj[m]
Step-2 : Repeat through step-4  while (adj[m] != NULL)
Step-3 : Increment the value of ‘current’ as
current = current->link;
Step-4 : Update the value of ‘adj’ as adj[m]=current
Step-5 : Initialize i=1
Step-6 : Repeat through step-13  while (i<= n)
Step-7 : Check if ( i != m) then go to step-8
Otherwise go to step-12
Step-8 : Check if (adj[i]->vertex == m) then go to step-9
Otherwise go to step-10
Step-9 : Set current = adj[i] and update the value of ‘adj[i]’ as
adj[i]=adj[i]->link;
and go to step-13
Step-10 : Set current = adj[i]->link and previous = adj[i]
Step-11 : Repeat through step-12 while (current != NULL)
Step-12 : Check if (current->vertex == m) then
Set previous->link = current->link and go to step-13
Otherwise  Set previous = current and    current = current->link
And go to step-11
Step-13 : Increment the value of ‘i’ as i=i+1
Step-14 : Exit

The ‘C’ implementation of this algorithm is as:

Implementation : DeleteNode

DeleteNode(GraphNode *adj[], int n, int m)
{
 GraphNode *current, *previous;
 int i;
 current = adj[m];
 while (adj[m] != NULL)
 {
 current = current->link;
 freenode(adj[m]);
 adj[m]=current;
 }
 for(i=1; i<= n; i++)
 {
 if ( i != m)
 {
 if (adj[i]->vertex == m)
 {
 current = adj[i];
 adj[i]=adj[i]->link;
 freenode(current);
 continue;
 }
 current = adj[i]->link;
 previous = adj[i];
 while (current != NULL)
 {
 if (current->vertex == m)
 {
 previous->link = current->link;
 freenode(current);
 break;
 }
 else
 {
 previous = current;
 current = current->link;
 }}}}}