tsounakis

DFS Graph #1

Jun 26th, 2022 (edited)
219
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.13 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define E 4
  4. #define V 4
  5.  
  6. void DFS (int x, int *n, int *p, int **visit, int **parent, int **a)
  7. {
  8.   *n += 1;
  9.   *(*visit + x) = *n;
  10.   *(*parent + x) = *p;
  11.   *p = x;
  12.   for (int j = 0; j < V; j++)
  13.     {
  14.       if (*(*a + x + E * j) == 1 && *(*visit + j) == 0)
  15.     DFS (j, n, p, visit, parent, a);
  16.     }
  17. }
  18.  
  19. void printResult (int *visit, int *parent)
  20. {
  21.   int i, j;
  22.   printf ("visit = \n");
  23.   for (int i = 0; i < E; i++) printf ("%d\t", *(visit + i) - 1);
  24.   printf ("\nparent = \n");
  25.   for (int i = 0; i < E - 1; i++) printf ("%d\t", *(parent + i));
  26.   printf ("NP(*)\n*:No Parent means that node 3 is the root.");
  27. }
  28.  
  29. int main ()
  30. {
  31.   int *visit = (int *) calloc (E, sizeof (int));
  32.   int *parent = (int *) calloc (E, sizeof (int));
  33.  
  34.   int *a = calloc( E * E, sizeof (int *));
  35.  
  36.   *(a + 0 * E + 2) = 1;
  37.   *(a + 1 * E + 3) = 1;
  38.   *(a + 1 * E + 2) = 1;
  39.   *(a + 2 * E + 0) = 1;
  40.   *(a + 2 * E + 1) = 1;
  41.   *(a + 2 * E + 3) = 1;
  42.   *(a + 3 * E + 1) = 1;
  43.   *(a + 3 * E + 2) = 1;
  44.  
  45.   int n = 0, p = -1, s = 3;
  46.   DFS (s, &n, &p, &visit, &parent, &a);
  47.   printResult (visit, parent);
  48.   return 0;
  49. }
  50.  
Add Comment
Please, Sign In to add comment