Поиск в ширину (BFS) - Resources

Поиск в ширину (BFS) - Resources

d[x]

x

const int inf = 1e9;

bool used[N];       // true if the vertex has been visited
vector<int> v[N];   // adjacency list

int d[N];           // distances from the source
int p[N];           // parent of each vertex

void bfs(int n, int s) {
    // initialization
    for (int i = 1; i <= n; i++) {
        d[i] = inf;
        p[i] = -1;
        used[i] = false;
    }

    queue<int> q;

    // starting vertex
    q.push(s);
    d[s] = 0;
    used[s] = true;

    while (!q.empty()) {
        int x = q.front();
        q.pop();

        for (int y : v[x]) {
            if (!used[y]) {
                used[y] = true;
                d[y] = d[x] + 1;
                p[y] = x;
                q.push(y);
            }
        }
    }
}