9 Graph – Introduction to Data Structures in C

Chapter 9

Graph

Chapter Outline

9.1 INTRODUCTION

Graphs are frequently used in every walk of life. Every day we come across various kinds of graphs appearing in newspapers or television. The countries in a globe are seen in a map. A map depends on the geographic location of the places or cities. As such, a map is a well-known example of a graph. In the map, various connections are shown between the cities. The cities are connected via roads, rail or aerial network. How to reach a place is indicated by means of a graph. Using the various types of the links the maps can be shown.

Fig. 9.1 illustrates a graph that contains the cities of India connected by means of road. Assume that the graph is the interconnection of cities by roads. As per the graph, Mumbai, Hyderabad and Kolkata are directly connected to all the other cities by road. Delhi is directly connected to Mumbai, Hyderabad, and Kolkata. Delhi is connected to Chennai via Hyderabad.

Generally, we provide the address of our office / residence to a stranger who is not aware of our address and location of city. At this juncture we use the graph for the easiest representation of our residential location. Fig. 9.2 shows the location of place by graph. By using the graph any stranger can easily find location. For example, a pilgrim wishes to reach the Gurudwara in Nanded. The path is shown in the figure for reaching the Gurudwara. The devotee has to reach the destination via Shivaji statue, Mahatma Gandhi statue and then Gurudwara as per the graph. Once a map is provided, any stranger can reach any destination by using appropriate conveyance.

Figure 9.1 Map representation of connection of cities

Figure 9.2 Representation of a map

In Fig. 9.2, four places are connected by road links. In the graph the road links are called as edges and the places are called as vertices. The graph is a collection of the vertices and the edges, hence a map is treated as graph. The following section describes the graph and relevant theories.

Like tree, graphs are nonlinear data structures. Tree nodes are arranged hierarchically from top to bottom like a parent is placed at the top and child as successor at the lower level. Tree has some specific structure whereas graph does not have a specific structure. It varies from application to application.

9.2 GRAPH

A graph is set of nodes and arcs. The nodes are also termed as vertices and arcs are termed as edges. The set of nodes as per the Fig. 9.3 is denoted as {O, P, R, S, Q}. The set of arcs in the following graph are {(O,P), (O,R), (O,Q), (R,S), (Q,S)}. Graph can be represented as,

G= (V,E) and V(G)= (O, Q, P, R, S) or group of vertices.

Similarly, E(G)= ((O,P), (O,R), (O,Q),(R,S),(Q,S)) or group of edges.

Figure 9.3 Graph

A graph is linked if there is pathway between any two nodes of the graph, such a graph is called connected graph or else, it is non-connected graph. Fig. 9.4 and 9.5 are connected and nonconnected graphs, respectively. In both the figures four nodes are depicted. In the latter all the nodes are not connected by links whereas in the former case all the nodes are joined by paths or links.

Figure 9.4 Connected graph

Figure 9.5 Non-connected graph

Undirected Graph A graph containing unordered pair of nodes is termed as undirected graph.

The vertices are {A, B, C, D} and edges are {(A, B), (A, D), (A, C), (B, D), (B, C), (D, C)}. The graph has four nodes and six edges. This type of graph is known as completely connected network, in which every node is having out going path to all nodes in the network. For a complete network the number of links =N (N−1)/2, where N is the number of vertices or nodes. In the Fig. 9.6 N is 4. By substituting its value the number of edges obtained will be equal to 6.

Figure 9.6 Undirected graph

Directed Graph This kind of graph contains ordered pairs of vertices. For example, graph vertices are {A,B,C,D,E} and edges are {(A,B),(B,D),(C,D)(C,A), (C,E), (E, A)}. Fig. 9.7 represents a graph having five nodes and six edges.

A direction is associated with each edge. The directed graph is also known as digraph.

Figure 9.7 Directed graph

V(G) = {A, B, C, D, E} and

group of directed edges = {(A,B), (B,D), (C,D)(C,A), (C,E), (E, A)}.

9.3 TERMINOLOGIES OF GRAPH

Weighted Graph A graph is supposed to be weighted if its every edge is assigned some value which is greater than or equal to zero, i.e. non-negative value. The value is equal to the length between two vertices. Weighted graph is also called as network. Weighted graph is shown in Fig. 9.8.

Adjacent Nodes When there is an edge from one node to another then these nodes are called adjacent nodes.

Incidence In an undirected graph the edges v0 , v1 is incident on nodes. In a direct graph the edge v0, v1 is incident from node v0. It is incident to node v1.

Path A path from edges u0 to node un is a sequence of nodes u0, u1,u2, u3.. .un−1, un. Here, u0 is adjacent to u1, u1 is adjacent to u2 and un−1 is adjacent to un.

Figure 9.8 A weighted graph

Length of Path Length of path is nothing but total number of edges included in the path from source node to destination node.

Closed Path When first and last nodes of the path are same, such path is known as closed path. In Fig. 9.9 closed path at node A is shown.

Figure 9.9 Closed path for node A

Simple Path In this path all the nodes are different with an exception that the first and last nodes of the path can be similar.

Cycle Cycle is a simple path. The first and last nodes are same. In other words, a closed simple path is a cycle. In a digraph a path is known as cycle if it has one or more nodes. The starting node is connected to the last node. In an undirected graph a path is called cycle if it has at least three nodes. The starting node is connected to last node. In the following figure path ACDBA is a closed path. Example of a cycle is shown in Fig. 9.10.

Figure 9.10 Example of a cycle

Cycle Graph A graph having cycle is called cycle graph. In this case the first and last nodes are the same. A closed simple path is a cycle. This is same as closed path shown in Fig. 9.10.

Acyclic Graph A graph without cycle is called acyclic graph. Examples of acyclic graphs are shown in Fig. 9.11.

Figure 9.11 Acyclic graphs

Dag A directed acyclic graph is called dag after its acronym (reduction). Fig. 9.12 is a graph showing the dag.

Figure 9.12 Dag

Degree In an undirected graph, the total number of edges linked to a node is called degree of that node. In a digraph there are two degrees for every node called indegree and outdegree. In the above Fig. 9.12, E has two edges hence degree is 2. Similarly, D has degree three and so on.

Indegree The indegree of a node is the total number of edges coming to that node. In Fig. 9.12, C is receiving two edges hence, the indegree is two.

Outdegree: The outdegree of a node is the total number of edges going outside from that node. In the above Fig. 9.12 the outdegree of D is one.

Source A node, which has only outgoing edges and no incoming edges, is called a source. The indegree of source is zero. In Fig. 9.12 the node E is the source since it does not have any incoming edges. It has only the outgoing edges.

Sink A node having only incoming edges and no outgoing edges is called sink node. Node C in Fig. 9.12 is a sink node because it has only incoming edges but no outgoing edges.

Pendant Node When indegree of node is one and outdegree is zero then such a node is called pendant node.

Reachable If a path exists between two nodes it will be called reachable from one node to other node.

Isolated Node When degree of node is zero, i.e. node is not connected with any other node then it is called isolated node. In Fig. 9.13 B node is the isolated node.

Figure 9.13 Isolated node

Successor and Predecessor In digraph if a node V0 is adjacent to node V1 then V0 is the predecessor of V1 and V1 is the successor of V0.

Complete Graph The graph in which any V0 node is adjacent to all other nodes present in the graph is known as a complete graph. An undirected graph contains the edges that are equal to edges= n(n−1)/2. The following figure shows the complete graph.

The ‘n’ is the number of vertices present in the graph.

Articulation Poi nt On removing the node the graph gets disconnected, then that node is called the articulation point.

Biconnected Graph The biconnected graph is the graph which does not contain any articulation point.

Multigraph A graph in which more than one edge is used to join the vertices is called multigraph. Edges of multigraph are parallel to each other.

Figure 9.14 Multigraph

Fig. 9.14 shows the multigraph in which one can see the parallel edges between A and D, D and C, B and C, and A and B.

Regular Graph Regular graph is the graph in which nodes are adjacent to each other i.e. each node is accessible from any other node.

9.4 GRAPH REPRESENTATION

The graph can be implemented by linked list or array. Fig. 9.15 illustrates a graph and its representation and implementation is also described.

Figure 9.15 Model graph

Different possibilities of graph representations are dependent on two cases:

  1. If there is no edge between two nodes.

    There is no edge between nodes P and Q.

  2. If there is an edge between any two nodes.

The nodes P and Q are having an edge.

Hence, following Table 9.1 provides the representation of the graph (Fig. 9.15).

 

Table 9.1 Representation of a graph

As per the table 9.1, there is an edge in between the nodes P and Q, P and R, and there is no edge between nodes P and S. The symbol ✓ indicates existence of edge and ✘ indicates absence of edge between two nodes.

From the above table one can predict the path to reach a particular node. For example, initial node is P and the destination node is U. We have to find the path to reach node U from P.

There is no edge between P and U. Then, find out the edge for nearest node in forward direction. By observing, we know there are two edges from P to Q and P to R. We can select either Q or R. Suppose, we have selected node Q, again find out next nearest successive node to Q by observing column Q. The next successive forward node will be S. Then, refer column S and it provides two edges Q and U. The node U is our solution. Thus, by using the above table, paths between any two nodes can be determined. The path should be P-Q-S-U. The graph can be represented by sequential representation and linked list representation.

Adjacency Matrix The matrix can be used to represent the graph. The information of adjacent nodes will be stored in the matrix. Presence of edges from a particular node can be determined easily. The matrix can be represented by two-dimensional array. In a twodimensional array [][], the first sub-script indicates row and second, column. For example, there are five nodes in the graph then the 0th row indicates node1 and so on. Likewise, column represents node1, node2, and so on. For example, consider a two-dimensional array.

Nodes[j[k]

1 indicates presence of edge between two nodes j and k.

0 indicates absence of an edge between two nodes j and k.

Thus, the matrix will contain only 0 and 1 values.

Figure 9.16 An example of graph

The matrix for the graph given in Fig. 9.16 would be

In the above matrix ,Mat[0][1]=1, which represents an edge between node P and Q. Entry of one in the matrix indicates that there is an edge and 0 for no edge. Thus, adjacency is maintained in the matrix X. One can also represent the undirected graph with adjacency matrix. Fig. 9.17 is an undirected graph.

Figure 9.17 Undirected graph

The adjacency matrix for the above graph would be as follows:

The above matrix is symmetric since x[i][j]= x[j][i].

In undirected graph the sum of row elements and column elements is the same. The sum represents the degree of the node. In this matrix the sum of any row or any column is 2, which is nothing but the degree of each node is 2.

We can also represent in the same way a weighted graph with adjacency matrix. The contents of the matrix will not be only 0 and 1 but the value is substituted with the corresponding weight.

For a null graph, that contains n vertices but no edges, all the elements of such null graph in an adjacency matrix are 0.

Figure 9.18 Null matrix

Fig. 9.18 represents the null graph and the adjacency matrix is as follows:

A program on adjacency of a graph is illustrated below.

Example 9.1

Write a program to demonstrate adjacency of graph

Solution

#include <stdio.h>

#include <conio.h>

main()

{

int mej=1,k,beg,num, des;

int adj[20][20]={( 0,0)};

char g_type;

clrscr();

printf("\nEnter number of nodes : ");

scanf("%d",&num);

printf("Enter type of graph,(d)irected or (u)ndirected: ");

g_type=getch();

fflush(stdin);

if(g_type=='u') me=num*(num−1)/2;

else me=num*(num−1);

while (j<=me)

{

printf("\n Enter edges %d ( 0 to exit ): "j);

scanf ("%d %d",&beg,&des);

if((beg==0) && (des==0)) break;

if ( beg > num || des > num || beg<=0 || des<=0)

{

    printf("Invalid edges !\n");

    j--;

}

else

{

    adj[ beg ][ des ]=1;

    if( g_type== 'u')

      adj[beg][des]=1;

      if(g_type=='u')

          adj[des][beg]=1;

      }

      j++;

}

printf ("\n The adjency of matrix is : \n");

for (j=1;j<=num;j++)

{

      for (k=1;k<=num;k++)

      printf (" %d ",adj[j][k]);

      printf ("\n");

   }

  return 0;

}

OUTPUT

Enter number of nodes: 5

Enter type of graph,(d)irected or (u)ndirected: u

Enter edges 1 ( 0 to exit ): 1 1

Enter edges 2 ( 0 to exit ): 2 1

Enter edges 3 ( 0 to exit ): 2 2

Enter edges 4 ( 0 to exit ): 0 1

Invalid edges !

Enter edges 4 ( 0 to exit ): 1 2

Enter edges 5 ( 0 to exit ): 0 0

The adjency of matrix is:

1 1 0 0 0

1 1 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

Explanation In this program maximum edges are calculated by using formula. If the graph is directed type, the formula is me=num*(num−1); where, num is the total number of nodes. When the graph is undirected then the formula is me=num*(num−1)/2.

After computing maximum edges, the user is prompted to enter edges. When 0,0 are entered the while loop is terminated. When the entered edges are greater than num and less than or equal to zero, message “Invalid edges” is displayed. Otherwise, adj[ beg ][ des ]=1.

9.4.1 Adjacency List

Two lists are maintained for adjacency of list. The first list is used to store information of all the nodes. The second list is used to store information of adjacent nodes for each node of a graph.

In case a graph comprises of N nodes, then two lists are to be prepared.

  1. First list keeps the track of all the N nodes of a graph.
  2. The second list is used to keep the information of adjacent nodes of each and every node of a graph. As such there will be N lists that would keep the information of adjacent nodes.

Header node is used to represent each list, which is assumed to be the first node of a list. Fig. 9.19 represents a header node.

Figure 9.19 Header node

struct node

{

struct * next

int num;

struct edge *aj;

};

Structure of an Edge Fig. 9.20 is the representation of an edge.

Figure 9.20 An edge of graph

struct edge

{

int num;

struct edge *ptr;

};

Consider a graph cited in Fig. 9.21.

Figure 9.21 An example of graph

Adjacency list for the above graph would be given in Fig. 9.22.

Figure 9.22 Adjacency list

9.5 TRAVERSAL IN GRAPH

Traversing in a graph is nothing but visiting each and every node of a graph. The following points are to be noted in a graph:

  1. The graph has no first node or root. Therefore, the graph can be started from any node.
  2. In graph, only those nodes are traversed which are accessible from the current node. For complete traversing of graph, the path can be determined by traversing nodes step by step.
  3. In the graph, the particular node can be visited repeatedly. Hence, it is necessary to keep the track of the status of every node whether traversed or not.
  4. In graph to reach a particular node, more paths are available.

Two techniques are used for traversing nodes in a graph. They are depth first and breadth first. These techniques have been elaborated in detail in the following sections.

9.6 SPANNING TREES

A spanning tree is an undirected tree, containing only those nodes that are necessary to join all the nodes in the graph. The nodes of spanning trees have only one path between them. In spanning trees, the number of edges are less by one than the number of nodes (see Fig. 9.23).

Figure 9.23 Spanning trees

Depth first spanning tree is shown in Fig. 9.24.

Figure 9.24 Depth first spanning tree

Breadth first spanning tree is shown in Fig. 9.25.

Figure 9.25 Breadth first spanning

Weighted Graph When the edges of the graph contain positive values as weight it is known as weighted graph or network.

Prim’s Algorithm In this algorithm, the traversing can start from any node and addition can be done in spanning tree according to the weight of the edge. For example, we start with node n1, and then the next step is to check the entire connecting path to that node and find out which path has minimum weight. Thus, the nodes with minimum weight are added in Prim’s algorithms. Here, while program implementation it is essential to know the weight of the edge. For example, we have two edges e1 and e2 with weights 3 and 5. The edge e1 has minimum weight than e2 and hence, e1 will be added to spanning tree.

Example 9.2

Write a program to create minimum spanning tree using Prim’s algorithm.

Solution

#include<stdio.h>

# include <conio.h>

#include <process.h>

struct prim

{

int pred_sor;

int stat;

int distance;

};

struct node { int x; int w; };

int adjc[10][10],num;

int main()

{

int y=1,wt,counter;

struct node trees[10];

void create (void );

void show (void );

int m_tree(struct node*, int*);

clrscr();

create();

printf("Adjacency of Matrix : ");

show();

counter=m_tree(trees,&wt);

printf("Weight of spanning trees is : %d\n", wt);

printf("Edges to be included in spanning trees : ");

while(y<=counter)

{

    printf("%d->",trees[y].x);

    printf("%d\num",trees[y].w);

    y++;

}

return 0;

}

void create()

{

int y=1,m_edge,start,end,wt;

printf("Enter number of vertices : ");

scanf("%d",&num);

m_edge=num*(num−1)/2;

while (y<=m_edge)

{

    printf("Enter node %d( 0 to Exit) : ",y);

    scanf("%d %d",&start,&end);

    if((start==0) && (end==0)) break;

    printf("Enter weight of this node : ");

    scanf("%d",&wt);

    if( start > num || end > num || start<=0 || end<=0)

    {

        printf("Wrong node!\n");

        --y;

    }

    else

    {

        adjc[start][end]=wt;

        adjc[end][start]=wt;

    }

y++;

}

if(y<num−1)

{

    printf("Spanning tree not possible\n");

    exit(0);

}

}

void show()

{

int y=1,p;

while (y<=num)

{

    for(p=1;p<=num;p++)

    printf("%3d",adjc[y][p]);

    printf("\n");

    y++;

}

}

int m_tree(struct node trees[10],int *wht)

{

struct prim p_ion[10];

int y=1,mm,counter,cur;

int perm(struct prim *);

int uu,vv;

wht=0;

while(y<=num)

{

    p_ion[y].pred_sor=0;

    p_ion[y].distance = 9999;

    p_ion[y].stat = 0;

    y++;

}

p_ion[1].pred_sor=0;

p_ion[1].distance = 0;

p_ion[1].stat = 1;

cur=1;

counter=0;

while( perm(p_ion) != 1 )

{

      for(y=1;y<=num;y++)

      {

            if ( adjc[cur][y] > 0 && p_ion[y].stat == 0 )

            {

                  if( adjc[cur][y] < p_ion[y].distance )

                  {

                      p_ion[y].pred_sor = cur;

                      p_ion[y].distance = adjc[cur][y];

                  }

              }

         }

         mm=9999;

         for(y=1;y<=num;y++)

         {

              if(p_ion[y].stat == 0 && p_ion[y].distance < mm)

              {

                  mm = p_ion[y].distance;

                  cur=y;

              }

         }

         p_ion[cur].stat=1;

         uu=p_ion[cur].pred_sor;

         vv=cur,counter++;

         trees[counter].x=uu;

         trees[counter].w=vv;

         *wht=*wht+adjc[uu][vv];

}

return (counter);

}

int perm(struct prim p_ion[10] )

{

int y=1;

while(y<=num)

    if( p_ion[y++].stat == 0 )

    return 0;

return 1;

}

OUTPUT

Enter number of vertices : 5

Enter node 1( 0 to Exit) : 1 1

Enter weight of this node : 5

Enter node 2( 0 to Exit) : 1 1

Enter weight of this node : 3

Enter node 3( 0 to Exit) : 0 0

Spanning tree not possible

Explanation In this program the structure prim is defined as follows:

struct prim

{

int pred_sor;

int stat;

int distance;

};

struct node {int x; int w;};

The function create () is used to compute maximum edges. The m_tree () function is used to calculate the edges. The show () function is used to display the nodes.

9.6.1 Breadth First Search

This is one of the popular methods of traversing graph. This method uses the queue data structure for traversing nodes of the graph. Any node of the graph can act as a beginning node. Using any node as starting node, all other nodes of the graph are traversed. To shun repeated visit to the same node an array is maintained which keeps status of visited node.

Figure 9.26 A model graph

Take the node P of Fig. 9.26 as a beginning node. Initially, the node P is traversed. After this, all the adjacent nodes of P are traversed, i.e. Q, T and S. The traversal of nodes can be carried in any sequence. For example, the sequence of traverse of nodes is Q, S and T. The traversal will be

P Q S T

First, all the nodes neighbouring Q are traversed, then neighbouring nodes of S and finally T are taken into account. The adjacent node of Q is R and T is U. Similarly, the adjacent node of T is U and S does not have any adjacent node. Hence, in this step the traversal now should be in the following way:

P Q S T R U

Now, the new nodes obtained are R and U after traversing. The new adjacent node of R is U and U node does not have any adjacent node. Node U has been visited in the previous case hence it must be ignored in this step.

9.6.2 Depth First Search

In this method, also a node from graph is taken as a starting node. Traverse through all the possible paths of the starting node. When the last node of the graph is obtained and path is not available from the node; then control returns to previous node. This process is implemented using stack.

Consider the following graph shown in Fig. 9.27

Figure 9.27 A model graph

Consider, P as starting node. Then, traverse the node adjacent to P and we will get Q and then R (adjacent to Q) and U (adjacent to R). The traversal will be

P Q R U

The search is always carried in forward direction. After reaching to U, we reach the end of the path and further movement in forward direction is not possible. Hence, the controls go to the previous node and again traverse through the available paths for non-traversed nodes.

In reverse direction, we get the node R and it has unvisited node. Hence, Q is taken and it gives T. The node T gives U, but it is already visited. Therefore, control in reverse direction checks all the nodes. It takes P and it gives node S. The sequence of traversal will be

P Q R U T S

The following program explains both the above procedures.

Example 9.3

Write a program to demonstrate breadth first search and depth first search.

Solution

#include<stdio.h>

#include <conio.h>

# include <process.h>

#define num 21

int aj[num][num],tra_sed[num],count;

int main()

{

int j,x,select;

int show (void),create(void),dfs(int);

int dfs_rsn(int),bfs(int),adj_edg(int);

void nodes(void);

clrscr();

create();

for (;;)

{

    printf("1. Adjacency of matrix\n");

    printf("2. Depth First Search with stack\n");

    printf("3. Depth First Search with recursion\n");

    printf("4. Breadth First Search\n");

    printf("5. Adjacent vertices\n");

    printf("6. Elements\n");

    printf("7. Quit\n");

    printf("Enter option : ");

    scanf("%d",&select);

    switch(select)

    {

    case 1:

        printf("Adjacency of Matrix\n");

        show();

        break;

    case 2:

        printf("Enter Beginning node for Depth First Search : ");

        scanf("%d",&x);

        for(j=1;j<=count;j++)

        tra_sed[j]=0;

        dfs(x); break;

    case 3:

        printf("Enter Beginning node for Depth First Search : ");

        scanf("%d",&x);

        for(j=1;j<=count;j++)

        tra_sed[j]=0;

        dfs_rsn(x); break;

    case 4:

    printf("Enter Beginning node for Breadth First Search : ");

        scanf("%d", &x);

        for(j=1;j<=count;j++)

        tra_sed[j]=0;

        bfs(x);

        break;

    case 5:

        printf("Enter node to search adjacent vertices : ");

        scanf("%d", &x);

        printf("Adjacent Vertices : ");

        adj_edg(x);

        break;

    case 6:

        nodes();

        break;

    case 7:

        exit(0);

    default:

        printf("Invalid selection\n");

        break;

    }

}

}

create()

{

int j,m_edges,start,target;

printf("Enter number of nodes : ");

scanf("%d",&count);

m_edges=count*(count−1);

for(j=1;j<=m_edges;j++)

{

    printf("Enter edge %d( 0 0 to quit ) : "j);

    scanf("%d %d",&start,&target);

    if((start==0) && (target==0))

        break;

    if( start > count || target > count || start<=0 || target<=0)

    {

        printf("Invalid edges try again !\n");

        --j;

    }

    else aj[start][target]=1;

}

return 0;

}

show()

{

int j;

for(j=1j<=countj++)

{

    for(j=1j<=countj++)

        printf("%5d",aj[j][j]);

    printf("\n");

}

return 0;

}

dfs_rsn(int x)

{

int j;

tra_sed[x]=1;

printf(" %d ",x);

for(j=1j<=countj++)

if(aj[x][j]==1 && tra_sed[j]==0)

dfs_rsn(j);

return 0;

}

dfs(int x)

{

int j,stack[num],TOP=−1,popve;

TOP++;

stack[TOP]=x;

while (TOP>=0)

{

    popve=stack[TOP];

    TOP-- ;

    if( tra_sed[popve]==0)

    {

        printf("%d ",popve);

        tra_sed[popve]=1;

    }

    else

        continue;

    for(j=countj>=1j--)

    {

        if( aj[popve][j]==1 && tra_sed[j]==0)

        {

            TOP++;

            stack[TOP]=j;

        }

    }

}

return 0;

}

bfs(int x)

{

int j,fr,re;

int queue[20];

fr=re= −1;

printf("%d ",x);

tra_sed[x]=1;

re++;

fr++;

queue[re]=x;

while(fr<=re)

{

    x=queue[fr];

    fr++;

    for(j=1j<=countj++)

    {

        /* Check for adjacent unvisited nodes */

        if( aj[x][j]==1 && tra_sed[j]==0)

        {

            printf("%d "j);

            tra_sed[j]=1;

            re++;

            queue[re]=j;

        }

    }

}

return 0;

}

adj_edg(int x)

{

int j;

for(j=1;j<=count;j++)

if(aj[x][j]==1)

printf("%d "j);

printf("\n");

return 0;

}

void nodes()

{

int j;

for(j=1;j<=count;j++)

    tra_sed[j]=0;

for(j=1;j<=count;j++)

{

    if(tra_sed[j]==0)

        dfs_rsn(j);

}

printf("\n");

}

OUTPUT

Enter number of nodes : 5

Enter edge 1( 0 0 to quit ) : 1 1

Enter edge 2( 0 0 to quit ) : 2 2

Enter edge 3( 0 0 to quit ) : 1 5

Enter edge 4( 0 0 to quit ) : 0 0

1. Adjacency of matrix

2. Depth First Search with stack

3. Depth First Search with recursion

4. Breadth First Search

5. Adjacent vertices

6. Elements

7. Quit

Enter option : 1

Adjacency of Matrix

1 1 0 0 0

Explanation In this program following user defined functions are defined to perform various tasks. Create () function when executed prompts user to enter number of edges and corresponding edge values. When user enters edges, maximum edges are calculated. For complete details of the procedure read the topic depth first search. The function adj_edg () calculates the edges. The function bfs () performs breadth first search. For details, refer the topic breadth first search illustrated in the same topic.

Summary
  1. In this chapter graph theory is described. Also, its implementation is illustrated with numerous examples.
  2. A graph is a set of nodes and arcs. The nodes are also termed as vertices and arcs are termed as edges.
  3. A graph is linked if there is a pathway between any two nodes of the graph, such a graph is called connected graph or else it is non-connected graph.
  4. The graph can be implemented by linked list or array.
  5. Explanation on adjacency matrix is provided in the form of matrix. The information of adjacent nodes can be stored in the matrix. Presence of edges from a particular node can be determined easily. The matrix can be represented by two-dimensional array. In twodimensional, array [][] the first subscript.
  6. Traversal in a tree is also explained in this chapter. The node can be visited repeatedly. Hence, it is necessary to keep the track of node as to whether it has been visited or not.
  7. Spanning tree is discussed in detail. Two methods have been elaborated together with examples. Breadth first and depth first spanning trees have been illustrated in detail.
Exercises
  1. Answer the following questions:
    1. What do you mean by edges and vertices of a graph?
    2. Define the following terms applicable to a graph:
      1. Degree
      2. Dag
      3. Indegree
      4. Outdegree
      5. Cycle.
    3. Distinguish between the directed and undirected graphs.
    4. What do you mean by complete graph?
    5. Explain traversing of a graph.
    6. Distinguish between the breadth first and depth first traversals in a graph.
    7. Describe spanning trees.
    8. How are graphs implemented in computer memory?
    9. Distinguish between the tree and graph.
    10. Define the following terms in a graph:
      1. Source
      2. Sink
      3. Isolated node
      4. Articulation point.
  2. Select the appropriate options for each of the following questions:
    1. The header is used to point
      1. first node of the list
      2. last node of the list
      3. NULL value
      4. none of the above.
    2. Traversing means
      1. visiting all the nodes
      2. shifting all the nodes at forward
      3. randomly accessing the elements
      4. none of the above.
    3. Graph is a
      1. linear data structure
      2. nonlinear data structure
      3. none of the above.
    4. Graph contains
      1. edges
      2. arcs
      3. edges and arcs
      4. none of the above.
    5. The indegree of a node is
      1. the total number of edges coming to that node
      2. the total number of edges leaving from that noded
      3. the total number of edges coming and leave to that node
      4. None of the above.
    6. The directed graph is also called
      1. trigraph
      2. digraph
      3. none of the above.
    7. Length of path is nothing but
      1. total number of edges included in the path from source to destination node
      2. total number of edges included in the path from destination to source
      3. none of the above.
    8. When first and last nodes of the path are same such a path is known as
      1. open path
      2. closed path
      3. none of the above.
    9. A directed acyclic graph is called
      1. dag
      2. acycle
      3. none of the above.
    10. When a degree of node is zero then the node is called
      1. group node
      2. isolated node
      3. none of the above.
    11. Traversal in graph is
      1. to visit only few nodes of a graph
      2. to visit all nodes of a graph
      3. none of the above.
  3. Attempt the following program:
    1. Write a program to demonstrate breadth first search and depth first search.
    2. Write a program to demonstrate spanning tree.
    3. Write a program to count the number of nodes of a graph.
    4. Write a program to count the indegree and outdegree of every node of a graph.
    5. Write a program to find the number of source nodes in a graph.
    6. Write a program to find the number of sink nodes in a graph.
    7. Write a program to find the successors and predecessors of each node in a graph.
    8. Write a program to find the number of isolated nodes in a graph.
    9. Find the adjacency matrix for the graph given below: