Kulesh

bfs code

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