TEXT   96

Untitled

Guest on 22nd April 2022 02:51:07 PM

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. void bfs(int **, int, int);
  4. void dfs(int **, int, int);
  5. int main()
  6. {
  7.     int **i_adjmatrix, i_number_of_nodes, i_itervar, i_itervar1, i_u, i_v, i_ch;
  8.     do
  9.     {
  10.         printf("\nEnter ther number of nodes:");
  11.         scanf("%d", &i_number_of_nodes);
  12.     } while (i_number_of_nodes <= 0);
  13.  
  14.     i_adjmatrix = (int **)calloc(i_number_of_nodes, sizeof(int *));
  15.  
  16.     for (i_itervar = 0; i_itervar < i_number_of_nodes; i_itervar++)
  17.     {
  18.         i_adjmatrix[i_itervar] = (int *)calloc(i_number_of_nodes, sizeof(int));
  19.     }
  20.  
  21.     printf("\nEnter the edges for the graph:\n");
  22.     do
  23.     {
  24.         printf("\n\tEnter the node pairs (u v) which you want to connect:");
  25.         scanf("%d%d", &i_u, &i_v);
  26.         i_adjmatrix[i_u - 1][i_v - 1] = 1;
  27.         i_adjmatrix[i_v - 1][i_u - 1] = 1;
  28.         printf("\nDo you want to insert more number of edges? (1-yes/0-no):");
  29.         scanf("%d", &i_u);
  30.     } while (i_u != 0);
  31.  
  32.     printf("\nThe input graph is:\n");
  33.     for (i_itervar = 0; i_itervar < i_number_of_nodes; i_itervar++)
  34.     {
  35.         for (i_itervar1 = 0; i_itervar1 < i_number_of_nodes; i_itervar1++)
  36.         {
  37.             printf("%d ", i_adjmatrix[i_itervar][i_itervar1]);
  38.         }
  39.         printf("\n");
  40.     }
  41.  
  42.     do
  43.     {
  44.         printf("\n\t1. BFS");
  45.         printf("\n\t2. DFS");
  46.         printf("\n\t3. Exit");
  47.         printf("\n Enter your choice:");
  48.         scanf("%d", &i_ch);
  49.  
  50.         switch (i_ch)
  51.         {
  52.         case 1:
  53.             printf("\nEnter the start node:");
  54.             scanf("%d", &i_u);
  55.             bfs(i_adjmatrix, i_number_of_nodes, i_u - 1);
  56.             break;
  57.         case 2:
  58.             printf("\nEnter the start node:");
  59.             scanf("%d", &i_u);
  60.             dfs(i_adjmatrix, i_number_of_nodes, i_u - 1);
  61.             break;
  62.         case 3:
  63.             break;
  64.         default:
  65.             printf("\nEnter proper choice...!");
  66.         }
  67.     } while (i_ch != 3);
  68.  
  69.     free(i_adjmatrix);
  70.  
  71.     return 0;
  72. }
  73.  
  74. void dfs(int **a, int n, int s)
  75. {
  76.     int *d, *parent, *stk;
  77.     int i, k, top = -1, u, v, count = 0;
  78.  
  79.     d = (int *)calloc(n, sizeof(int));
  80.     parent = (int *)calloc(n, sizeof(int));
  81.     stk = (int *)calloc(n, sizeof(int));
  82.  
  83.     for (i = 0; i < n; i++)
  84.     {
  85.         d[i] = -1;
  86.         parent[i] = -1;
  87.     }
  88.     d[s] = 0;
  89.     stk[++top] = s;
  90.  
  91.     while (top != -1)
  92.     {
  93.         v = stk[top--];
  94.         count++;
  95.         for (u = 0; u < n; u++)
  96.         {
  97.             if (a[v][u] == 1)
  98.             {
  99.                 if (d[u] < 0)
  100.                 {
  101.                     d[u] = d[v] + 1;
  102.                     parent[u] = v;
  103.                     stk[++top] = u;
  104.                 }
  105.             }
  106.         }
  107.     }
  108.  
  109.     if (count == n)
  110.     {
  111.         printf("\nGraph is connected\n");
  112.     }
  113.     else
  114.     {
  115.         printf("\nGraph is not connected\n");
  116.     }
  117.  
  118.     for (i = 0; i < n; i++)
  119.     {
  120.         printf("\nDistance from node %d to node %d is %d and path between them is", s + 1, i + 1, d[i]);
  121.         if (i != s)
  122.         {
  123.             printf(" %d ", i + 1);
  124.             k = i;
  125.             while (parent[k] != -1)
  126.             {
  127.                 k = parent[k];
  128.                 printf("-> %d ", k + 1);
  129.             }
  130.         }
  131.     }
  132.  
  133.     free(d);
  134.     free(parent);
  135.     free(stk);
  136. }
  137.  
  138. void bfs(int **a, int n, int s)
  139. {
  140.     int *d, *parent, *q;
  141.     int i, k, front = -1, rear = -1, u, v, count = 0;
  142.  
  143.     d = (int *)calloc(n, sizeof(int));
  144.     parent = (int *)calloc(n, sizeof(int));
  145.     q = (int *)calloc(n, sizeof(int));
  146.  
  147.     for (i = 0; i < n; i++)
  148.     {
  149.         d[i] = -1;
  150.         parent[i] = -1;
  151.     }
  152.     d[s] = 0;
  153.     q[++rear] = s;
  154.  
  155.     while (front != rear)
  156.     {
  157.         v = q[++front];
  158.         count++;
  159.         for (u = 0; u < n; u++)
  160.         {
  161.             if (a[v][u] == 1)
  162.             {
  163.                 if (d[u] < 0)
  164.                 {
  165.                     d[u] = d[v] + 1;
  166.                     parent[u] = v;
  167.                     q[++rear] = u;
  168.                 }
  169.             }
  170.         }
  171.     }
  172.  
  173.     if (count == n)
  174.     {
  175.         printf("\nGraph is connected\n");
  176.     }
  177.     else
  178.     {
  179.         printf("\nGraph is not connected\n");
  180.     }
  181.  
  182.     for (i = 0; i < n; i++)
  183.     {
  184.         printf("\nDistance from node %d to node %d is %d and path between them is", s + 1, i + 1, d[i]);
  185.         if (i != s)
  186.         {
  187.             printf(" %d ", i + 1);
  188.             k = i;
  189.             while (parent[k] != -1)
  190.             {
  191.                 k = parent[k];
  192.                 printf("-> %d ", k + 1);
  193.             }
  194.         }
  195.     }
  196.  
  197.     free(d);
  198.     free(parent);
  199.     free(q);
  200. }

Raw Paste


Login or Register to edit or fork this paste. It's free.