Чтобы выполнить поиск в ширину (BFS) на графе с помощью C++, вы можете использовать различные структуры данных и алгоритмы. Вот несколько методов с примерами кода:

Метод 1: использование списка смежности

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void BFS(vector<vector<int>>& graph, int startVertex) {
    int numVertices = graph.size();
    vector<bool> visited(numVertices, false);
    queue<int> q;
    visited[startVertex] = true;
    q.push(startVertex);
    while (!q.empty()) {
        int currentVertex = q.front();
        cout << currentVertex << " ";
        q.pop();
        for (int neighbor : graph[currentVertex]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}
int main() {
    int numVertices = 7; // Number of vertices in the graph
    vector<vector<int>> graph(numVertices);
    // Add edges to the graph
    graph[0] = {1, 2};
    graph[1] = {0, 3, 4};
    graph[2] = {0, 5, 6};
    graph[3] = {1};
    graph[4] = {1};
    graph[5] = {2};
    graph[6] = {2};
    int startVertex = 0; // Starting vertex for BFS
    cout << "BFS traversal: ";
    BFS(graph, startVertex);
    return 0;
}

Метод 2: использование матрицы смежности

#include <iostream>
#include <queue>
using namespace std;
const int MAX_VERTICES = 100;
void BFS(int graph[MAX_VERTICES][MAX_VERTICES], int numVertices, int startVertex) {
    bool visited[MAX_VERTICES] = {false};
    queue<int> q;
    visited[startVertex] = true;
    q.push(startVertex);
    while (!q.empty()) {
        int currentVertex = q.front();
        cout << currentVertex << " ";
        q.pop();
        for (int neighbor = 0; neighbor < numVertices; ++neighbor) {
            if (graph[currentVertex][neighbor] && !visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}
int main() {
    int numVertices = 7; // Number of vertices in the graph
    int graph[MAX_VERTICES][MAX_VERTICES] = {0};
    // Add edges to the graph
    graph[0][1] = graph[1][0] = 1;
    graph[0][2] = graph[2][0] = 1;
    graph[1][3] = graph[3][1] = 1;
    graph[1][4] = graph[4][1] = 1;
    graph[2][5] = graph[5][2] = 1;
    graph[2][6] = graph[6][2] = 1;
    int startVertex = 0; // Starting vertex for BFS
    cout << "BFS traversal: ";
    BFS(graph, numVertices, startVertex);
    return 0;
}

Метод 3. Использование класса графа

#include <iostream>
#include <queue>
#include <list>
using namespace std;
class Graph {
    int numVertices;
    list<int> *adjacencyList;
public:
    Graph(int vertices) {
        numVertices = vertices;
        adjacencyList = new list<int>[numVertices];
    }
    void addEdge(int vertex, int neighbor) {
        adjacencyList[vertex].push_back(neighbor);
    }
    void BFS(int startVertex) {
        bool *visited = new bool[numVertices];
        for (int i = 0; i < numVertices; ++i)
            visited[i] = false;
        queue<int> q;
        visited[startVertex] = true;
        q.push(startVertex);
        while (!q.empty()) {
            int currentVertex = q.front();
            cout << currentVertex << " ";
            q.pop();
            for (int neighbor : adjacencyList[currentVertex]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
        delete[] visited;
    }
};
int main() {
    int numVertices = 7; // Number of vertices in the graph
    Graph graph(numVertices);
    // Add edges to the graph
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 5);
    graph.addEdge(2, 6);
    int startVertexHere's the revised code example for Method 3:
```cpp
#include <iostream>
#include <queue>
#include <list>

using namespace std;

class Graph {
    int numVertices;
    list<int> *adjacencyList;

public:
    Graph(int vertices) {
        numVertices = vertices;
        adjacencyList = new list<int>[numVertices];
    }

    void addEdge(int vertex, int neighbor) {
        adjacencyList[vertex].push_back(neighbor);
    }

    void BFS(int startVertex) {
        bool *visited = new bool[numVertices];
        for (int i = 0; i < numVertices; ++i)
            visited[i] = false;

        queue<int> q;
        visited[startVertex] = true;
        q.push(startVertex);

        while (!q.empty()) {
            int currentVertex = q.front();
            cout << currentVertex << " ";
            q.pop();

            for (int neighbor : adjacencyList[currentVertex]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }

        delete[] visited;
    }
};

int main() {
    int numVertices = 7; // Number of vertices in the graph
    Graph graph(numVertices);

    // Add edges to the graph
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 5);
    graph.addEdge(2, 6);

    int startVertex = 0; // Starting vertex for BFS

    cout << "BFS traversal: ";
    graph.BFS(startVertex);

    return 0;
}

В этом коде мы определяем класс Graph, который использует список смежности для представления графика. Функция addEdgeдобавляет ребро между двумя вершинами, а функция BFSвыполняет поиск в ширину графа, начиная с указанной вершины.