Advertisement
naeem043

C Topological Sort SSC DFS with shopping list

Jun 7th, 2018
236
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.38 KB | None | 0 0
  1. #include <stdio.h>
  2.  
  3. void DFS_Visit(int u);
  4. int g[9][9],color[7],prev[9],d[9], f[9],t,flage = 0,cu[9],cv[9],ts[9],m=0;
  5. char name[9][100] = {"Undershort","Pants","Belt","Shirt","Tie","Jacket","Socks","Shoes","Watch"};
  6.  
  7. void DFS(int g[9][9])
  8. {
  9.     int i,j,s=0,u,v;
  10.  
  11.    for(i=0;i<9;i++)
  12.     {
  13.         color[i] = 0;
  14.         prev[i] = 0;
  15.         d[i] = 999999;
  16.         f[i] = 999999;
  17.     }
  18.     t = 0;
  19.     color[s] = 0;
  20.     prev[s] = 0;
  21.     d[s] = 0;
  22.  
  23.     for(j=0;j<9;j++)
  24.     {
  25.         if(color[j]==0)
  26.         {
  27.             DFS_Visit(j);
  28.         }
  29.     }
  30.  
  31.  
  32.     printf("\n Discovery Time:\t");
  33.     for(i=0;i<9;i++)
  34.         printf("%d\t",d[i]);
  35.  
  36.     printf("\n Finishing Time:\t");
  37.     for(i=0;i<9;i++)
  38.         printf("%d\t",f[i]);
  39.  
  40.     printf("\n Color:\t\t\t");
  41.     for(i=0;i<9;i++)
  42.         printf("%d\t",color[i]);
  43.  
  44.     printf("\n Topological List:\t");
  45.     for(i=8;i>=0;i--)
  46.          printf("%d ",ts[i]);
  47.  
  48.     printf("\n Shopping List:\t");
  49.     for(i=8;i>=0;i--)
  50.          printf("%s ",name[ts[i]]);
  51.  
  52.     if(flage==1)
  53.     {
  54.         printf("\n This Graph is cycle\nTheCycle Edges are:\n");
  55.         for(i=0;i<9;i++)
  56.         {
  57.              printf("%d - %d\t",cu[i],cv[i]);
  58.         }
  59.  
  60.     }
  61.  
  62.     else printf("\n This Graph is not cycle");
  63.  
  64. }
  65.  
  66. void DFS_Visit(int u)
  67. {
  68.    int i,k = 0, l= 0;
  69.     color[u] = 1;
  70.     t = t+1;
  71.     d[u] = t;
  72.  
  73.        for(i=0;i<8;i++)
  74.         {
  75.             if(color[i]==0 && g[u][i] !=0)
  76.             {
  77.                 prev[i] = u;
  78.                 DFS_Visit(i);
  79.             }
  80.            else if(color[i]==1 && g[u][i] !=0)
  81.            {
  82.                 flage = 1;
  83.                 cu[k] = u;
  84.                 cv[l++] = i;
  85.                 //printf("cycle edge %d\n", i);
  86.  
  87.                 k++;
  88.                 l++;
  89.            }
  90.  
  91.  
  92.         }
  93.  
  94.         color[u] = 2;
  95.         t = t+1;
  96.         f[u] = t;
  97.         ts[m] = u;
  98.         m++;
  99.  
  100. }
  101.  
  102.  
  103. int main()
  104. {
  105.     int i,j;
  106.  
  107.     for(i=0;i<9;i++)
  108.     {
  109.          for(j=0;j<9;j++)
  110.          {
  111.              g[i][j] = 0;
  112.          }
  113.  
  114.     }
  115. // Graph initialize
  116.     g[0][1] = 1;
  117.     g[0][7] = 1;
  118.  
  119.     g[1][2] = 1;
  120.     g[1][7] = 1;
  121.  
  122.     g[2][5] = 1;
  123.  
  124.     g[3][4] = 1;
  125.  
  126.     g[4][5] = 1;
  127.  
  128.     g[6][7] = 1;
  129.  
  130.     for(i=0;i<9;i++)
  131.     {
  132.        for(j=0;j<9;j++)
  133.        {
  134.            printf("%d ",g[i][j]);
  135.        }
  136.         printf("\n");
  137.     }
  138.  
  139.     DFS(g);
  140.     return 0;
  141. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement