Advertisement
Shailrshah

DFS using Adjacency Matrix

Oct 7th, 2013
194
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.49 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. char **a;
  4. int *visited, n;
  5. void dfs(int x){
  6.     int y;
  7.     visited[x] = 1;
  8.     printf(" %c ", 'A' + x); //index converted to char by adding A
  9.     for(y = 0; y < n; y++)
  10.         if(!visited[y] && a[x][y] == 'Y')
  11.             dfs(y);
  12. }
  13. void buildAdjacentMatrix(){
  14.     int i, j, choice;
  15.     printf("\n Enter number of vertices:");
  16.     scanf("%d",&n);
  17.     a =(char**) malloc(sizeof(char*) * n);
  18.     for(i = 0; i < n; i++) a[i] = (char*) malloc(n * sizeof(char)); //alternate to char a[n][n]
  19.     visited = (int*) malloc(sizeof(int)*n); //alternate to int visited[n]
  20.     for(i = 0; i < n; i++) visited[i] = 0;
  21.     for(i = 0; i < n; i++)
  22.         for(j = 0; j <= i; j++){
  23.             printf("Are vertices %c and %c linked?: ", 'A' + i, 'A' + j);
  24.             scanf("%d", &choice);
  25.             if(choice == 1) a[i][j] = a[j][i] = 'Y';
  26.             else a[i][j] = a[j][i] = 'N';
  27.         }
  28.     printf("The graph is:-\n");
  29.     for(i = 0; i < n; i++) printf("\t%c", 'A'+i);
  30.     printf("\n\n\n");
  31.     for(i = 0; i < n; i++){
  32.         printf("%c", 'A'+i);
  33.         for(j = 0; j < n; j++) printf("\t%c", a[i][j]);
  34.         printf("\n\n\n");
  35.     }
  36. }
  37. int main(){
  38.     char ch;
  39.     buildAdjacentMatrix();
  40.     printf("Start from which vertex?: ");
  41.     fflush(stdin); //Clears input stream
  42.     ch = getchar(); // char input from user
  43.     if(ch >= 'A' && ch <= ('A' + n-1)) dfs(ch-'A'); //DFS starts from user inputted alphabet.
  44.     else printf("Error.");
  45.     return 0;
  46.  }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement