Playground
//koristi C++11 - http://mendo.mk/Lecture.do?id=26 #include <iostream> #include <vector> #include <queue> #include <cstring> using namespace std; const int MAX_N = 101; //grafot vector<int> G[MAX_N]; //oznacuvanje na nivoto na sekoe teme int level[MAX_N]; void BFS(int start) { int marked[MAX_N]; memset(marked, 0, sizeof(marked)); //sekogash e dobra ideja da gi inicijalizirame vrednostite vo niza (0) memset(level, 0, sizeof(level)); queue<int> queue; queue.push(start); //korenot e vekje poseten, i istiot ima nivo 0 marked[start] = 1; level[start] = 0; while(!queue.empty()) { int node = queue.front(); queue.pop(); for (auto next : G[node]) { if (marked[next] == 0) { queue.push(next); marked[next] = 1; //pronajdovme neposeteno teme //postavi go negovoto nivo level[next] = level[node] + 1; } } } } int main() { int N; cout << "Number of vertices: " << endl; cin >> N; int E = N - 1; //brojot na rebra e N-1, bidejki grafot e drvo cout << "Enter the connections, one per line." << endl; for (int i=0; i<E; i++) { int v1, v2; cin >> v1 >> v2; G[v1].push_back(v2); G[v2].push_back(v1); //grafot e nenasocen } //pochnuvame od temeto 0 (kako toa da e koren na drvoto) //kaj nekoi problemi, koe teme e koren kje ni bide dadeno na vlez BFS(0); for (int i=0; i<N; i++) { cout << "Level of vertex " << i << " is equal to " << level[i] << endl; } return 0; }
Input data
Program output
5 0 1 0 2 0 3 2 4
Execute
Language: ????????? | Memory: ???? KB | Time: ??? ms
Nothing has been executed, yet!