#include <iostream>
#include <fstream>
#include <queue>
/*
1-----3 6
| |
| |
2-----4-----5
*/
const size_t SIZE = 6;
// инициализиране на графа
int graph[SIZE][SIZE] = {
{0, 1, 1, 0, 0, 0},
{1, 0, 0, 1, 0, 0},
{1, 0, 0, 1, 0, 0},
{0, 1, 1, 0, 1, 0},
{0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0}
};
void printGraph()
{
for(size_t i = 0; i < SIZE; ++i)
{
for(size_t j = 0; j < SIZE; ++j)
{
std::cout << graph[i][j] << " ";
}
std::cout << std::endl;
}
}
int main()
{
printGraph();
size_t layerIndex = 1;
size_t startVertex = 0;
std::cout << "Start vertex: " << startVertex + 1 << std::endl;
// масив, в който ще се маркират посетените върхове
bool visited[SIZE] = {false};
visited[startVertex] = true;
std::queue<size_t> currentLayer;
currentLayer.push(startVertex);
bool moreNeighbours = currentLayer.empty();
while(!moreNeighbours)
{
std::cout << "Layer " << layerIndex << ": ";
std::queue<size_t> nextLayer;
while(!currentLayer.empty())
{
size_t currentVertex = currentLayer.front();
currentLayer.pop();
// търсене на всички върхове, които все още не са посетени
// и са съседни на връх от текущия слой
for(size_t neighbour = 0; neighbour < SIZE; ++neighbour)
{
if(graph[currentVertex][neighbour] && !visited[neighbour])
{
nextLayer.push(neighbour);
visited[neighbour] = true;
std::cout << neighbour + 1 << ' ';
}
}
}
std::cout << std::endl;
++layerIndex;
currentLayer = nextLayer;
moreNeighbours = currentLayer.empty();
}
std::cout << "\nIsolated verteces: ";
// проверка за върхове, които не са свързани с останалите
for(size_t vertex = 0; vertex < SIZE; ++vertex)
{
if(!visited[vertex])
std::cout << vertex + 1 << ' ';
}
std::cout << std::endl;
return 0;
}