Kulesh

bfs path reconstruct

Dec 21st, 2016
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.51 KB | None | 0 0
  1. #include<iostream>
  2. #include<time.h>
  3. #include<stdlib.h>
  4. #include<vector>
  5.  
  6. using namespace std;
  7.  
  8. int E[10][10];
  9. int visited[10];
  10. vector<int> parent;
  11.  
  12. struct queue{
  13. vector <int> arr;
  14. int front;
  15. int size;
  16. void enqueue(queue &a, int b){
  17. a.arr.push_back(b);
  18. a.size++;
  19. }
  20. int dequeue(queue &a){
  21. int x = a.arr[a.front];
  22. a.front++;
  23. a.size--;
  24. return x;
  25. }
  26. };
  27.  
  28. void bfs(int i){
  29. for(int j = 1; j < 10; j++){
  30. visited[j] = 0;
  31. parent.push_back(-1);
  32. }
  33. queue Q;
  34. Q.front = 0;
  35. Q.size = 0;
  36. visited[i] = 1;
  37. Q.enqueue(Q, i);
  38.  
  39. while(Q.size != 0){
  40. int a = Q.dequeue(Q);
  41. for(int k = 1; k < 10; k++) {
  42. if(E[a][k] == 1){
  43. if(visited[k] == 0){
  44. visited[k] = 1;
  45. parent[k] = a;
  46. Q.enqueue(Q, k);
  47. }
  48. }
  49. }
  50. }
  51. }
  52.  
  53. int main() {
  54. E[1][2] = 1;
  55. E[2][1] = 1;
  56. E[3][1] = 1;
  57. E[1][3] = 1;
  58. E[2][4] = 1;
  59. E[4][2] = 1;
  60. E[9][8] = 1;
  61. E[8][9] = 1;
  62. E[7][6] = 1;
  63. E[6][7] = 1;
  64. E[6][3] = 1;
  65. E[3][6] = 1;
  66. E[4][6] = 1;
  67. E[6][4] = 1;
  68. E[4][5] = 1;
  69. E[5][4] = 1;
  70. E[4][8] = 1;
  71. E[8][4] = 1;
  72. bfs(1);
  73. cout << "Reachable points from 1" << endl;
  74. for(int i = 1; i < 10; i++){
  75. cout << visited[i] << endl;
  76. }
  77.  
  78. int c;
  79. int i = 9;
  80. while(parent[i] > 0){
  81. i = parent[i];
  82. c++;
  83. }
  84. cout << c << endl;
  85. return 0;
  86. }
Add Comment
Please, Sign In to add comment