Advertisement
SMASIF

DFS With Edges

Feb 5th, 2017
217
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.98 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3. int v,t;
  4. int matrix[100][100];
  5. int clr[100],dis[100],fin[100],prev[100];
  6. int t_edge,b_edge,f_edge,c_edge;
  7. void DFS();
  8. void DFS_visit(int s);
  9. int main()
  10. {
  11. int r,c,n,s;
  12. int edge=1;
  13. cout<<"Input No Of Vertices: ";
  14. cin>>v;
  15.  
  16. do
  17. {
  18. cout<<"Edge "<<edge<<": "<<endl;
  19. cin>>r>>c;
  20.  
  21. if(r>v || c>v)
  22. cout<<"Invalid Input"<<endl;
  23. else
  24. {
  25. matrix[r][c]=1;
  26. edge++;
  27. }
  28. }while(r!=0 && c!=0);
  29.  
  30. DFS();
  31. return 0;
  32. }
  33.  
  34. void DFS()
  35. {
  36. int i;
  37. t=0;
  38. t_edge=0;
  39. b_edge=0;
  40. f_edge=0;
  41. c_edge=0;
  42.  
  43. for(i=0;i<=v;i++)
  44. {
  45.  
  46. dis[i]=2000000;
  47. fin[i]=2000000;
  48. clr[i]=0;
  49. prev[i]=-1;
  50. }
  51.  
  52. for(i=1;i<=v;i++){
  53. if(clr[i]==0)
  54. {
  55. DFS_visit(i);
  56. }
  57. }
  58. cout<<endl<<"Vertex: ";
  59. for(i=1;i<=v;i++)
  60. cout<<i<<" ";
  61. cout<<endl<<"dis[u]: ";
  62. for(i=1;i<=v;i++)
  63. cout<<dis[i]<<" ";
  64. cout<<endl<<"fin[u]: ";
  65. for(i=1;i<=v;i++)
  66. cout<<fin[i]<<" ";
  67. cout<<endl;
  68. cout<<endl;
  69. cout<<endl;
  70.  
  71.  
  72.  
  73. cout<<"No Of Tree Edges: "<<t_edge<<endl;
  74. cout<<"No Of forward Edges: "<<f_edge<<endl;
  75. cout<<"No Of Back Edges: "<<b_edge<<endl;
  76. cout<<"No Of cross Edges: "<<c_edge<<endl;
  77.  
  78. }
  79.  
  80. void DFS_visit(int s)
  81. {
  82. int i;
  83. clr[s]=1;
  84. t=t+1;
  85. dis[s]=t;
  86. for(i=1;i<=v;i++)
  87. {
  88. if(matrix[s][i]==1 && clr[i]==0)
  89. {
  90. prev[i]=s;
  91. t_edge++;
  92. DFS_visit(i);
  93. }
  94. else if(matrix[s][i]==1 && clr[i]==1)
  95. b_edge++;
  96. else
  97. {
  98. if(matrix[s][i]==1 && clr[i]==2)
  99. {
  100.  
  101.  
  102. if(dis[s]<dis[i])
  103. f_edge++;
  104. else
  105. c_edge++;
  106.  
  107. }
  108. }
  109. }
  110.  
  111. clr[s]=2;
  112. t=t+1;
  113. fin[s]=t;
  114.  
  115.  
  116. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement