SHARE
TWEET

C DFS

naeem043 May 25th, 2018 (edited) 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <queue>
  3.  
  4. using namespace std;
  5. void DFS_Visit(int u);
  6. int g[7][7],color[7],prev[7],d[7], f[7],t,flage = 0,cu[7],cv[7];
  7.  
  8. void DFS(int g[7][7])
  9. {
  10.     int i,j,s=0,u,v;
  11.  
  12.    for(i=0;i<7;i++)
  13.     {
  14.         color[i] = 0;
  15.         prev[i] = 0;
  16.         d[i] = 999999;
  17.         f[i] = 999999;
  18.     }
  19.     t = 0;
  20.     color[s] = 0;
  21.     prev[s] = 0;
  22.     d[s] = 0;
  23.  
  24.     for(j=0;j<7;j++)
  25.     {
  26.         if(color[j]==0)
  27.         {
  28.             DFS_Visit(j);
  29.         }
  30.     }
  31.  
  32.  
  33.     printf("\n Discover Time:\t");
  34.     for(i=0;i<7;i++)
  35.         printf("%d\t",d[i]);
  36.  
  37.     printf("\n Final Time:\t");
  38.     for(i=0;i<7;i++)
  39.         printf("%d\t",f[i]);
  40.  
  41.     printf("\n Color:\t");
  42.     for(i=0;i<7;i++)
  43.         printf("%d\t",color[i]);
  44.  
  45.     if(flage==1)
  46.     {
  47.         printf("\n Cycle Edge\n");
  48.         for(i=0;i<7;i++)
  49.         {
  50.              printf("%d - %d\t",cu[i],cv[i]);
  51.         }
  52.  
  53.     }
  54.  
  55.     else printf("This Graph is not cycle");
  56.  
  57.  
  58. }
  59.  
  60. void DFS_Visit(int u)
  61. {
  62.    int i,k = 0, l= 0;
  63.     color[u] = 1;
  64.     t = t+1;
  65.     d[u] = t;
  66.  
  67.        for(i=0;i<7;i++)
  68.         {
  69.             if(color[i]==0 && g[u][i] !=0)
  70.             {
  71.                 prev[i] = u;
  72.                 DFS_Visit(i);
  73.             }
  74.            else if(color[i]==1 && g[u][i] !=0)
  75.            {
  76.                 flage = 1;
  77.                 cu[k] = u;
  78.                 cv[l++] = i;
  79.                 printf("cycle edge %d\n", i);
  80.  
  81.                 k++;
  82.                 l++;
  83.  
  84.            }
  85.  
  86.         }
  87.  
  88.         color[u] = 2;
  89.         t = t+1;
  90.         f[u] = t;
  91.  
  92. }
  93.  
  94.  
  95. int main()
  96. {
  97.     int i,j;
  98.  
  99.     for(i=0;i<7;i++)
  100.     {
  101.          for(j=0;j<7;j++)
  102.          {
  103.              g[i][j] = 0;
  104.          }
  105.  
  106.     }
  107. // Graph initialize
  108.     g[0][1] = 1;
  109.     g[0][2] = 1;
  110.     g[0][3] = 1;
  111.  
  112.     g[1][0] = 1;
  113.     g[1][3] = 1;
  114.     g[1][5] = 1;
  115.  
  116.     g[2][0] = 1;
  117.     g[2][4] = 1;
  118.     g[2][6] = 1;
  119.  
  120.     g[3][0] = 1;
  121.     g[3][1] = 1;
  122.     g[3][6] = 1;
  123.  
  124.     g[4][2] = 1;
  125.  
  126.     g[5][1] = 1;
  127.     g[5][6] = 1;
  128.  
  129.     g[6][2] = 1;
  130.     g[6][3] = 1;
  131.     g[6][5] = 1;
  132.  
  133.     for(i=0;i<7;i++)
  134.     {
  135.        for(j=0;j<7;j++)
  136.        {
  137.            printf("%d ",g[i][j]);
  138.        }
  139.         printf("\n");
  140.     }
  141.  
  142.     DFS(g);
  143.     return 0;
  144. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top