BREADTH-FIRST TRAVERSAL

< Day Day Up >

BREADTH-FIRST TRAVERSAL

Introduction

When a graph is traversed by visiting all the adjacent nodes/vertices of a node/vertex first, the traversal is called breadth-first traversal. For example, for a graph in which the breadth-first traversal starts at vertex v ₁ , visits to the nodes take place in the order shown in Figure 22.10.

click to expand
Figure 22.10: Breadth-first traversal of graph G starting at vertex v1.

Program

A complete C program for breadth-first traversal of a graph appears next . The program makes use of an array of n visited elements where n is the number of vertices of the graph. If visited[i] = 1 , it means that the i ^th vertex is visited. The program also makes use of a queue and the procedures addqueue and deletequeue for adding a vertex to the queue and for deleting the vertex from the queue, respectively. Initially, we set visited[i] = 0 .

#include <stdio.h> #include <stdlib.h> #define MAX 10 struct node { int data; struct node *link; }; void buildadjm(int adj[][MAX], int n) { int i,j; printf("enter

adjacency

matrix \n",i,j); for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d",&adj[i][j]); } /* A function to insert a new node in queue*/ struct node *addqueue(struct node *p,int val) { struct node *temp; if(p == NULL) { p = (struct node *) malloc(sizeof(struct node)); /* insert the new node first node*/ if(p == NULL) { printf("Cannot allocate\n"); exit(0); } p->data = val; p->link=NULL; } else { temp= p; while(temp->link != NULL) { temp = temp->link; } temp->link = (struct node*)malloc(sizeof(struct node)); temp = temp->link; if(temp == NULL) { printf("Cannot allocate\n"); exit(0); } temp->data = val; temp->link = NULL; } return(p); } struct node *deleteq(struct node *p,int *val) { struct node *temp; if(p == NULL) { printf("queue is empty\n"); return(NULL); } *val = p->data; temp = p; p = p->link; free(temp); return(p); } void bfs(int adj[][MAX], int x,int visited[], int n, struct node **p) { int y,j,k; *p = addqueue(*p,x); do{ *p = deleteq(*p,&y); if(visited[y] == 0) { printf("\nnode visited = %d\t",y); visited[y] = 1; for(j=0;j<n;j++) if((adj[y][j] ==1) && (visited[j] == 0)) *p = addqueue(*p,j); } }while((*p) != NULL); } void main() { int adj[MAX][MAX]; int n; struct node *start=NULL; int i, visited[MAX]; printf("enter the number of nodes in graph maximum = %d\n",MAX); scanf("%d",&n); buildadjm(adj,n); for(i=0; i<n; i++) visited[i] =0; for(i=0; i<n; i++) if(visited[i] ==0) bfs(adj,i,visited,n,&start); }

Example

Input and Output

Enter the number of nodes in graph maximum = 10 9

Enter adjacency matrix

0 1 0 0 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 node visited = 0 node visited = 1 node visited = 4 node visited = 2 node visited = 3 node visited = 6 node visited = 5 node visited = 7 node visited = 8

< Day Day Up >

CONNECTED COMPONENT OF A GRAPH

Introduction

The connected component of a graph is a maximal subgraph of a given graph, which is connected. For example, consider the graph that follows .

The connected component of the graph G1 is shown in Figure 22.11.

Figure 22.11: Connected component of G ₁ .

Strongly Connected Component

For a diagraph (directed graph), a strongly connected component is that component of the graph in which, for every pair of distinct vertices vi and vj, there is a directed path from vi to vj, and also a directed path from vj to vi. For example, consider the diagraph shown in Figure 22.12.

click to expand
Figure 22.12: A diagraph.

The strongly connected components of the graph are shown in Figure 22.13.

click to expand
Figure 22.13: Strongly connected components of the graph shown in Figure 22.12.

Example

Is the following diagraph strongly connected?

This table shows the possible pairs of vertices, and the forward and backward paths between them, for the previous graph:

PAIR OF VERTICES	FORWARD PATH	BACKWARD PATH

<1, 2>	1-2	2-3-4
<1,3>	1-2-3	3-1
<1,4>	1-4	4-3-1
<2,3>	2-3	3-1-2
<2,4>	2-3-1-4	4-3-1-2
<3,4>	3-1-4	4-3

Therefore, we see that between every pair of distinct vertices of the given graph there exists a forward as well as a backward path, so it is strongly connected.

Program

Write a function dfs(v) to traverse a graph in a depth-first manner starting from vertex v. Use this function to find connected components in the graph. Modify dfs() to produce a list of newly visited vertices. The graph is represented as adjacency lists.

#include <stdio.h> #define MAXVERTICES 20 #define MAXEDGES 20 typedef enum {FALSE, TRUE, TRISTATE} bool; typedef struct node node; struct node { int dst; node *next; }; void printGraph( node *graph[], int nvert ) { /* * prints the graph. */ int i, j; for( i=0; i<nvert; ++i ) { node *ptr; for( ptr=graph[i]; ptr; ptr=ptr->next ) printf( "[%d] ", ptr->dst ); printf( "\n" ); } } void insertEdge( node **ptr, int dst ) { /* * insert a new node at the start. */ node *newnode = (node *)malloc( sizeof(node) ); newnode->dst = dst; newnode->next = *ptr; *ptr = newnode; } void buildGraph( node *graph[], int edges[2][MAXEDGES], int nedges ) { /* * fills graph as adjacency list from array edges. */ int i; for( i=0; i<nedges; ++i ) { insertEdge( graph+edges[0][i], edges[1][i] ); insertEdge( graph+edges[1][i], edges[0][i] ); // undirected graph. } } void dfs( int v, int *visited, node *graph[] ) { /* * recursively traverse graph from v using visited. * and mark all the vertices that come in dfs path to TRISTATE. */ node *ptr; visited[v] = TRISTATE; //printf( "%d \n", v ); for( ptr=graph[v]; ptr; ptr=ptr->

next

) if( visited[ ptr->dst ] == FALSE ) dfs( ptr->dst, visited, graph ); } void printSetTristate( int *visited, int nvert ) { /* * prints all vertices of visited which are TRISTATE. * and set them to TRUE. */ int i; for( i=0; i<nvert; ++i ) if( visited[i] == TRISTATE ) { printf( "%d ", i ); visited[i] = TRUE; } printf( "\n\n" ); } void compINC(node *graph[], int nvert) { /* * prints all connected components of graph represented using INC lists. */ int *visited; int i; visited = (int *)malloc( nvert*sizeof(int) ); for( i=0; i<nvert; ++i ) visited[i] = FALSE; for( i=0; i<nvert; ++i ) if( visited[i] == FALSE ) { dfs( i, visited, graph ); // print all vertices which are TRISTATE. // and mark them to TRUE. printSetTristate( visited, nvert ); } free( visited ); } int main() { int edges[][MAXEDGES] = { {0,2,4,5,5,4}, {1,1,3,4,6,6} }; int nvert = 7; // no of vertices. int nedges = 6; // no of edges in the graph. node **graph = (node **)

calloc

( nvert, sizeof(node *) ); buildGraph( graph, edges, nedges ); printGraph( graph, nvert ); compINC( graph, nvert ); return 0; }

Explanation

The graph is represented as adjacency lists. The graph contains an array of n pointers where n is the number of vertices in the graph. Each entry i in the array contains a list of vertices to which i is connected. For example, if the graph is as shown in the first diagram, the adjacency lists for the graph are as shown in the subsequent diagram.

Each node in list i contains a vertex to which i is connected.
dfs(v) is implemented recursively. A Boolean vector visited[] is maintained whose entries are initially all FALSE . dfs(v) marks v as visited by making visited[v] = TRUE . It then finds all the adjacent nodes of v and starts dfs() from those nodes that have not yet been visited. For example, if dfs(v) is called with v == 0 , it marks 0 and then it traverses the adjacency list graph[0] and calls dfs(1) . This marks 1 and traverses the adjacency list graph[1] . But since 0 is already marked , dfs(2) is called. It marks 2 and starts traversal of graph[2] . But since 1 is marked, it returns. All the previous invocations return as there are no nodes being considered in the lists. Thus, the marked vertices are {0, 1, 2}.
compINC() is a function that finds all the connected components of a graph. It maintains a local copy of the vector visited[] and passes it as a parameter to dfs(v) . compINC() passes that vertex as a parameter to dfs() that has not yet been visited. Thus each invocation of dfs() finds one connected component of the graph.
In order to modify dfs() to produce a list of newly visited vertices, we tag the vertices visited using dfs() as TRISTATE . In compINC() , all these TRISTATE vertices will form one connected component. This status is then converted to TRUE . The next invocation to dfs() returns another set of vertices tagged as TRISTATE , which forms another connected component and so on.

For example, in the previous program, first all vertices are tagged as FALSE . After the invocation of dfs(0) , the vertices tagged as TRISTATE are {0, 1, 2}. These are output and their tags are changed from TRISTATE to TRUE . The next invocation of dfs(3) tags vertices {3, 4, 5, 6} as TRISTATE . These are then output and their tags are changed from TRISTATE to TRUE . Since there is no vertex remaining whose tag is FALSE , the algorithm stops.

Points to Remember

All the reachable vertices can be traversed from a source vertex by using depth-first search.
The data representation (a graph in this case) should be such that it should make algorithms operate on the data efficiently . Being represented as adjacency lists, we could easily traverse the list to get the vertices adjacent to a particular vertex.
Note how a simple recursive procedure solves the problem of finding all the reachable vertices from a vertex.
Note the use of descriptive words such as FALSE , TRUE and TRISTATE , rather than integers 0, 1 and 2. It makes the program easily understandable.