umesh adroja

umesh adroja

  • NA
  • 17
  • 335

TOPOLOGICAL SORT

Mar 31 2016 8:29 AM
  1. #include<iostream.h>  
  2. #include<conio.h>  
  3. class topologicalorder  
  4. {  
  5.     private:int n;  
  6.         int a[10][10];  
  7.         int indegree[10];  
  8.     public :void read_data();  
  9.         void find_indegree();  
  10.         void topological_sort();  
  11. };  
  12. void topologicalorder::read_data()  
  13. {  
  14.     cout<<"Enter the no of jobs :\n";  
  15.     cin>>n;  
  16.     cout<<"Enter the adjancency matrix :\n";  
  17.     for(int i=0;i<n;i++)  
  18.     {  
  19.         for(int j=0;j<n;j++)  
  20.         {  
  21.             cin>>a[i][j];  
  22.         }  
  23.     }  
  24. }  
  25. void topologicalorder::find_indegree()  
  26. {  
  27.     for(int j=0;j<n;j++)  
  28.     {  
  29.         int sum=0;  
  30.         for(int i=0;i<n;i++)  
  31.         {  
  32.             sum+=a[i][j];  
  33.         }  
  34.         indegree[j]=sum;  
  35.      }  
  36. }  
  37. void topologicalorder::topological_sort()  
  38. {  
  39.     int u,v,t[10],s[10];  
  40.     find_indegree();  
  41.     int top=-1;  
  42.     int k=0;  
  43.     for(int i=0;i<n;i++)  
  44.     {  
  45.         if(indegree[i]==0)  
  46.             s[++top]=i;  
  47.     }  
  48.     while(top!=-1)  
  49.     {  
  50.         u=s[top--];  
  51.         t[k++]=u;  
  52.         for(v=0;v<n;v++)  
  53.         {  
  54.             if(a[u][v]==1)  
  55.             {  
  56.                 indegree[v]--;  
  57.                 if(indegree[v]==0)  
  58.                     s[++top]=v;  
  59.             }  
  60.         }  
  61.     }  
  62.     cout<<"the topological sequence is :\n";  
  63.     for(i=0;i<n;i++)  
  64.         cout<<t[i]<<" ";  
  65. }  
  66. void main()  
  67. {  
  68.     topologicalorder t;  
  69.     clrscr();  
  70.     t.read_data();  
  71.     t.topological_sort();  
  72.     getch();