Implementing Graph Traversal (Breath First and Depth First)

Program Coding

// Include necessary headers

int main()


{



int ichoice,i,no=0,j;

int **graph=NULL;

char *symbl=NULL,gt,c,src,dest;

int getindex(char *,char ,int );


do{

    printf("\n\n\tGraph\n");

    printf("\n\t 1 to Create Graph \n");

    printf("\n\t 2 to Depth First Search \n");

    printf("\n\t 3 to Breath First Search\n");

    printf("\n\t 4 to Exit the program \n");

    printf("\n Your Choice -> ");



    scanf("%d",&ichoice);



    switch(ichoice) {

        case 1:
            if(graph!=NULL) {
                for(i=0;i<no;i++) 

                    free(graph[i]);
                free(graph);
                free(symbl);
            }

            printf("\n\tHow many nodes -> ");
            scanf("%d",&no);

            graph = malloc(no*sizeof(int *));
            symbl = malloc(no*sizeof(char));

            for(i=0;i<no;i++)
                graph[i] = (int *)malloc(no*sizeof(int));

            printf("\n\nGraph Type Directed or undirected -> ");
            getchar();

            gt = getchar();

            printf("\n\tEnter Nodes Avoid Repetition\n\t");

            for(i=0;i<no;i++) {
                scanf(" %c",&c);
                symbl[i] = c;
            }

            printf("\n\nEnter Edge pair\n");

            while(1) {
                scanf(" %c %c",&src,&dest);

                i=getindex(symbl,src,no);
                j=getindex(symbl,dest,no);

                if(i==-1||j==-1) break;

                if(gt =='d' || gt== 'D')
                    graph[i][j]=1;
                else
                    graph[i][j]=graph[j][i]=1;
            }

            printf("\n\nEdges created\n\n");
            break;

        case 2:
            dfs(graph,symbl,no);
            break;
        case 3:
            bfs(graph,symbl,no);
            break;
        case 4:
            exit(0);
    }
}while(1);

return 0;

}

int getindex(char *sy,char c,int n) { 

    int i;

    for(i=0;i<n;i++){

        if(sy[i]==c) 

            return i; 

    }
    return -1;
}

bfs(int **graph,char *symb,int n) {

    int x=0,*visited,i,que[20];
    int front=-1,rear=-1;
    char cc;

    visited = (int *) malloc(sizeof(int) * n);
    //Get Where to begin

    printf("\n\nWhere to Begin Traverse\n");
    getchar();

    cc = getchar();

    x=getindex(symb,cc,n);

    if(x==-1) {
        printf("\n\n\tInvalid Node....");
        return;
    }

    for(i=0;i<n;i++) 

        visited[i]=0;

    printf("\n\nBreath First Traversal\n");
    printf("%c ",symb[x]);

    visited[x]=1;

    rear++; 

    front++;
    que[rear]=x;

    while( front <= rear ) {
        x = que[front];
        front ++;

        for(i=0;i<n;i++) {
            if( (graph[x][i] == 1) && (visited[i] == 0) ) {
                printf("%c ",symb[i]);
                visited[i]=1;
                rear++;
                que[rear]=i;
            }
        }

    }     
}



dfs(int **graph,char *symb,int n) {

    int i,top=-1,stack[20],pop_v,j,t,*visited;
    int x=0;
    char cc;

    visited = (int *) malloc(sizeof(int ) * n); 

    for(i=0;i<n;i++)
        visited[i] = 0;

    printf("\n\nWhere to Begin Traverse\n");
    getchar();
    cc = getchar();
    x = getindex(symb,cc,n);

    if(x==-1) {
        printf("\n\tInvalid Node...");
        return ;
    }
    top++;
    stack[top] = x;
    printf("\n\nDepth First Traversal\n");

    while( top >= 0) {
        pop_v = stack[top];
        top--;
        if( visited[pop_v] == 0) {
            printf("%c ",symb[pop_v]);
            visited[pop_v] = 1;
        }
        else continue;

        for(i=n-1;i>=0;i--) {
            if( (graph[pop_v][i] == 1) && (visited[i] == 0) ) {
                top++;
                stack[top]=i;
            }
        } 

    }
}

The author is not liable for any discrepancies......