fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3.  
  4. using namespace std;
  5. int a[100][100], vs[100], n;
  6. stack<int> st;
  7. void DFS(int start) {
  8. 	st.push(start);
  9. 	vs[start] = 1;
  10. 	cout << start << "(0) ";
  11. 	while (!st.empty()) {
  12. 		int u = st.top();
  13. 		bool check = true;
  14. 		for (int i = 1; i <= n; i++) {
  15. 			if (a[u][i] && vs[i] == 0) {
  16. 				vs[i] = 1;
  17. 				st.push(i);
  18. 				check = false;
  19. 				cout << i << "(" << u << ") ";
  20. 				break;
  21. 			}
  22. 		}
  23. 		if (check) st.pop();
  24. 	}
  25. }
  26.  
  27. void DFS2(int start) {
  28. 	st.push(start);
  29. 	vs[start] = 1;
  30. 	int prev = 0;
  31. 	cout << start << "(" << prev << ") ";
  32.  
  33. 	while (!st.empty()) {
  34. 		int u = st.top();
  35. 		st.pop();
  36. 		prev = u;
  37. 		for (int i = 1; i <= n; i++) {
  38. 			if (a[u][i] && vs[i] == 0) {
  39. 				cout << i << "(" << prev << ") ";
  40. 				vs[i] = 1;
  41. 				st.push(u);
  42. 				st.push(i);
  43. 				break;
  44. 			}
  45. 		}
  46. 	}
  47. }
  48.  
  49. int main() {
  50.     cout << "So dinh: ";
  51.     cin >> n;
  52.     // Khoi tao ma tran ke
  53.     cout << "Nhap ma tran:\n";
  54.     memset(vs, 0, 100);
  55.     for (int i = 1; i <= n; i++) {
  56.         for (int j = 1; j <= n; j++) {
  57.             cin >> a[i][j];
  58.         }
  59.     }
  60.     cout << "Thuc hien thuat toan BFS tu dinh: ";
  61.     int start;
  62.     cin >> start;
  63.     // DFS(start);
  64. 	DFS2(start);
  65. }
  66.  
  67.  
  68. /**
  69. Test:
  70.  
  71. 5
  72. 0 1 1 1 0
  73. 1 0 0 0 1
  74. 1 0 0 0 1
  75. 1 0 0 0 1
  76. 0 1 1 1 0
  77.  
  78. 13
  79. 0 1 1 1 0 0 0 0 0 0 0 0 0
  80. 1 0 1 1 0 1 0 0 0 0 0 0 0
  81. 1 1 0 1 1 0 0 0 0 0 0 0 0
  82. 1 1 1 0 0 0 1 0 0 0 0 0 0
  83. 0 0 1 0 0 1 1 1 0 0 0 1 0
  84. 0 1 0 0 1 0 1 0 0 0 0 1 0
  85. 0 0 0 1 1 1 0 1 0 0 0 0 0
  86. 0 0 0 0 1 0 1 0 0 0 0 1 0
  87. 0 0 0 0 0 0 0 1 1 0 1 0 1
  88. 0 0 0 0 0 0 0 0 1 0 1 1 1
  89. 0 0 0 0 0 0 0 1 1 0 0 1 1
  90. 0 0 0 0 1 1 0 1 0 1 0 0 0
  91. 0 0 0 0 0 0 0 1 1 1 0 0 0
  92.  
  93. **/
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
So dinh: Nhap ma tran:
Thuc hien thuat toan BFS tu dinh: 5425(0)
https://ideone.com/IPf94Z
language:
C++ (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!