поиск в ширину.cpp

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Vertex {
    int id; // èäåíòèôèêàòîð âåðøèíû
    bool visited; // ôëàã ïîñåùåíèÿ
    vector<int> adjacentVertices; // ñïèñîê èäåíòèôèêàòîðîâ ñìåæíûõ âåðøèí
};

void bfs(vector<Vertex>& graph, int startVertexId) {
    queue<int> vertexQueue; // î÷åðåäü äëÿ ïîñåùåíèÿ âåðøèí
    vertexQueue.push(startVertexId); // äîáàâëÿåì ñòàðòîâóþ âåðøèíó â î÷åðåäü
    graph[startVertexId].visited = true; // ïîìå÷àåì ñòàðòîâóþ âåðøèíó, êàê ïîñåùåííóþ

    while (!vertexQueue.empty()) { // ïîêà î÷åðåäü íå ïóñòà
        int vertexId = vertexQueue.front(); // áåðåì âåðøèíó èç î÷åðåäè
        vertexQueue.pop(); // óäàëÿåì âåðøèíó èç î÷åðåäè
        cout << "Ïîñåùåííàÿ âåðøèíà: " << vertexId << endl; // âûâîäèì èäåíòèôèêàòîð ïîñåùåííîé âåðøèíû

        for (int adjacentVertexId : graph[vertexId].adjacentVertices) { // ïåðåáèðàåì ñìåæíûå âåðøèíû
            if (!graph[adjacentVertexId].visited) { // åñëè ñìåæíàÿ âåðøèíà íå áûëà ïîñåùåíà
                vertexQueue.push(adjacentVertexId); // äîáàâëÿåì ñìåæíóþ âåðøèíó â î÷åðåäü
                graph[adjacentVertexId].visited = true; // ïîìå÷àåì ñìåæíóþ âåðøèíó, êàê ïîñåùåííóþ
            }
        }
    }
}

int main() {
    // ñîçäàåì ãðàô
	setlocale(0,"Russian");
    int numVertices;
    cout << "Ââåäèòå êîëè÷åñòâî âåðøèí: ";
    cin >> numVertices;
    
    vector<Vertex> graph(numVertices);

    for(int i=0; i<numVertices; i++) {
        graph[i].id = i+1;
        graph[i].visited = false;
        int numAdjacent;
        cout << "Ââåäèòå êîëè÷åñòâî ñìåæíûõ âåðøèí äëÿ âåðøèíû " << i+1 << ": ";
        cin >> numAdjacent;
        
        for(int j=0; j<numAdjacent; j++) {
            int adjacentVertexId;
            cout << "Ââåäèòå èäåíòèôèêàòîð ñîñåäíåé âåðøèíû " << j+1 << ": ";
            cin >> adjacentVertexId;
            graph[i].adjacentVertices.push_back(adjacentVertexId);
        }
    }
    
    // Âûâîä ãðàôà
    cout << "Ãðàô:" << endl;
    for (Vertex vertex : graph) { // ïåðåáèðàåì âñå âåðøèíû ãðàôà
        cout << "Âåðøèíà " << vertex.id << " -> "; // âûâîäèì èäåíòèôèêàòîð òåêóùåé âåðøèíû â êîíñîëü
        for (int adjacentVertexId : vertex.adjacentVertices) { // ïåðåáèðàåì èäåíòèôèêàòîðû ñìåæíûõ âåðøèí òåêóùåé âåðøèíû
            cout << adjacentVertexId << " "; // âûâîäèì èäåíòèôèêàòîðû ñìåæíûõ âåðøèí òåêóùåé âåðøèíû â êîíñîëü
        }
        cout << endl; // ïåðåõîäèì íà ñëåäóþùóþ ñòðîêó
    }

    cout << endl << "Ïîèñê â øèðèíó:" << endl;
    bfs(graph, 0); // çàïóñêàåì ïîèñê â øèðèíó, íà÷èíàÿ ñ âåðøèíû ñ èäåíòèôèêàòîðîì 0

    cin.get();
    return 0;
}