Advertisement
SMASIF

Topological Sort using DFS & Transpose Matrix

Feb 19th, 2017
169
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.97 KB | None | 0 0
  1. #include<iostream>
  2. #include<list>
  3. #include<queue>
  4. using namespace std;
  5. int v,t;
  6. int matrix[100][100];
  7. int GT[101][101];
  8. int clr[100],dis[100],fin[100],prev[100];
  9. int t_edge,b_edge,f_edge,c_edge;
  10. list <int> tp_sort;
  11. list <int> :: iterator it;
  12. void DFS();
  13. void DFS_visit(int s);
  14. void SCC();
  15. int main()
  16. {
  17.     int r,c,n,s;
  18.     int edge=1;
  19.     cout<<"Input No Of Vertices: ";
  20.     cin>>v;
  21.  
  22.     do
  23.     {
  24.         cout<<"Edge "<<edge<<": "<<endl;
  25.         cin>>r>>c;
  26.  
  27.         if(r>v || c>v)
  28.             cout<<"Invalid Input"<<endl;
  29.         else
  30.         {
  31.             matrix[r][c]=1;
  32.             edge++;
  33.         }
  34.     }while(r!=0 && c!=0);
  35.  
  36.     DFS();
  37.     if(b_edge>0)
  38.         cout<<endl<<"Cyclic Graph!! Topological Sort Is Not Possible"<<endl;
  39.     else
  40.     {
  41.         cout<<endl<<endl<<"Topological sort: ";
  42.         for(it=tp_sort.begin();it!=tp_sort.end();it++)
  43.             cout<<*it<<" ";
  44.     }
  45.     cout<<endl;
  46.     SCC();
  47.     return 0;
  48. }
  49.  
  50. void DFS()
  51. {
  52.     int i;
  53.     t=0;
  54.     t_edge=0;
  55.     b_edge=0;
  56.     f_edge=0;
  57.     c_edge=0;
  58.  
  59.     for(i=0;i<=v;i++)
  60.     {
  61.  
  62.         dis[i]=2000000;
  63.         fin[i]=2000000;
  64.         clr[i]=0;
  65.         prev[i]=-1;
  66.     }
  67.  
  68. for(i=1;i<=v;i++){
  69.     if(clr[i]==0)
  70.     {
  71.         DFS_visit(i);
  72.     }
  73. }
  74.     cout<<endl<<"Vertex: ";
  75.     for(i=1;i<=v;i++)
  76.         cout<<i<<" ";
  77.     cout<<endl<<"dis[u]: ";
  78.     for(i=1;i<=v;i++)
  79.         cout<<dis[i]<<" ";
  80.     cout<<endl<<"fin[u]: ";
  81.     for(i=1;i<=v;i++)
  82.         cout<<fin[i]<<" ";
  83.    cout<<endl;
  84.    cout<<endl;
  85.    cout<<endl;
  86.  
  87.  
  88.  
  89.         cout<<"No Of Tree Edges: "<<t_edge<<endl;
  90.         cout<<"No Of forward Edges: "<<f_edge<<endl;
  91.         cout<<"No Of Back Edges: "<<b_edge<<endl;
  92.         cout<<"No Of cross Edges: "<<c_edge<<endl;
  93.  
  94. }
  95.  
  96. void DFS_visit(int s)
  97. {
  98.     int i;
  99.     clr[s]=1;
  100.     //t=t+1;
  101.     dis[s]=++t;
  102.     for(i=1;i<=v;i++)
  103.     {
  104.         if(matrix[s][i]==1 && clr[i]==2)
  105.         {
  106.             if(dis[s]<dis[i])
  107.             {
  108.                 f_edge++;
  109.                 cout<<s<<"-"<<i<<": Forward Edge"<<endl;
  110.             }
  111.  
  112.         else
  113.         {
  114.             c_edge++;
  115.             cout<<s<<"-"<<i<<": Cross Edge"<<endl;
  116.         }
  117.     }
  118.         else if(matrix[s][i]==1 && clr[i]==1)
  119.         {
  120.             b_edge++;
  121.             cout<<s<<"-"<<i<<": Back Edge"<<endl;
  122.         }
  123.         else
  124.         {
  125.             if(matrix[s][i]==1 && clr[i]==0)
  126.             {
  127.                 prev[i]=s;
  128.                 cout<<s<<"-"<<i<<": Tree Edge"<<endl;
  129.                 t_edge++;
  130.                 DFS_visit(i);
  131.             }
  132.         }
  133.     }
  134.  
  135.     clr[s]=2;
  136.     fin[s]=++t;
  137.     tp_sort.push_front(s);
  138.  
  139.  
  140. }
  141.  
  142. void SCC()
  143. {
  144.     int i,j;
  145.     for(i=1;i<=v;i++)
  146.     {
  147.         for(j=1;j<=v;j++)
  148.             GT[j][i]=matrix[i][j];
  149.  
  150.     }
  151.     cout<<"The Transposed Matrix Is: "<<" "<<endl;
  152.     for(int i=1;i<=v;i++)
  153.     {
  154.         for(int j=1;j<=v;j++)
  155.         {
  156.             cout<<" "<<GT[i][j]<<" ";
  157.         }
  158.         cout<<endl;
  159.     }
  160.  
  161.  
  162. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement