Drum minim cu BFS în C++: distanță și traseu

Ce măsurăm într-un traseu

Într-un graf neorientat, o succesiune de vârfuri consecutive adiacente se numește lanț. Dacă vârfurile nu se repetă, lanțul este elementar. În limbajul obișnuit al problemelor apare și formularea „drum minim”; în această lecție ea desemnează un lanț de lungime minimă într-un graf neorientat. Pentru grafuri orientate, traseele trebuie să respecte sensul arcelor.

Lungimea traseului este numărul de muchii parcurse, nu numărul de vârfuri enumerate. Traseul 1 2 4 are două muchii și trei vârfuri. Distanța de la un vârf la el însuși este zero, prin traseul format numai din acel vârf. Dacă două vârfuri sunt în componente diferite, nu există traseu între ele.

Lucrăm fără costuri pe muchii. Fiecare trecere costă exact un pas. Dacă muchiile ar avea costuri diferite, minimizarea numărului de muchii nu ar minimiza neapărat suma costurilor, iar programul de mai jos nu ar rezolva acea problemă.

Imagine indisponibilă: De la 1 la 4 există traseele 1-2-4 și 1-3-4, ambele de lungime doi; BFS păstrează părintele 2 pentru 4, iar vârful 5 rămâne inaccesibil.

Distanțe și părinți prin BFS

BFS procesează vârfurile pe niveluri. Mai întâi avem sursa la distanța zero, apoi vecinii ei la distanța unu, apoi vârfurile noi descoperite de aceștia la distanța doi. Coada păstrează această ordine.

Inițializăm dist[i] = -1 pentru toate vârfurile. Această valoare înseamnă încă inaccesibil din explorarea curentă. Pentru sursă punem dist[s] = 0. Când descoperim un vecin y din x, atribuim dist[y] = dist[x] + 1 și memorăm tata[y] = x. Prima descoperire oferă distanța minimă: o cale mai scurtă ar fi trecut printr-un nivel procesat deja.

Părintele păstrează un singur traseu minim, nu toate variantele. În exemplu, vecinii sunt examinați crescător, astfel încât 2 îl descoperă pe 4 înaintea lui 3. Distanța rămâne doi în ambele cazuri, dar alegerea părintelui stabilește traseul afișat.

Program: distanța și un traseu minim

Citim n m, apoi m muchii, apoi s t. Avem un graf neorientat simplu, 1 <= n <= 100, 0 <= m <= n*(n-1)/2, muchii distincte cu capete diferite în 1..n și sursa/destinația în același interval. Prima linie afișată conține distanța sau -1. Numai dacă destinația este accesibilă, a doua linie conține traseul.

După BFS, reconstruim de la destinație înapoi către sursă, urmărind părinții. Părintele sursei este zero, valoare care nu reprezintă niciun vârf. Salvăm vârfurile într-un tablou și îl afișăm invers. Nu încercăm reconstruirea când distanța este -1.

Varianta clasică, cu tablouri

#include <iostream>

int main() {
    int n, m;
    std::cin >> n >> m;
    int a[101][101] = {};
    for (int i = 0; i < m; ++i) {
        int x, y;
        std::cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
    int s, t;
    std::cin >> s >> t;
    int dist[101] = {};
    int tata[101] = {};
    int q[101] = {};
    int drum[101] = {};
    for (int i = 1; i <= n; ++i) dist[i] = -1;
    int st = 0, dr = 0;
    q[dr++] = s;
    dist[s] = 0;
    while (st < dr) {
        int x = q[st++];
        for (int y = 1; y <= n; ++y) {
            if (a[x][y] && dist[y] == -1) {
                dist[y] = dist[x] + 1;
                tata[y] = x;
                q[dr++] = y;
            }
        }
    }
    std::cout << dist[t] << '\n';
    if (dist[t] == -1) return 0;
    int k = 0;
    for (int x = t; x != 0; x = tata[x]) drum[k++] = x;
    for (int i = k - 1; i >= 0; --i) {
        std::cout << drum[i];
        if (i > 0) std::cout << ' ';
    }
    std::cout << '\n';
}

Varianta echivalentă cu std::vector

#include <iostream>
#include <vector>

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> a(n + 1, std::vector<int>(n + 1, 0));
    for (int i = 0; i < m; ++i) {
        int x, y;
        std::cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
    int s, t;
    std::cin >> s >> t;
    std::vector<int> dist(n + 1, 0);
    std::vector<int> tata(n + 1, 0);
    std::vector<int> q(n + 1, 0);
    std::vector<int> drum(n + 1, 0);
    for (int i = 1; i <= n; ++i) dist[i] = -1;
    int st = 0, dr = 0;
    q[dr++] = s;
    dist[s] = 0;
    while (st < dr) {
        int x = q[st++];
        for (int y = 1; y <= n; ++y) {
            if (a[x][y] && dist[y] == -1) {
                dist[y] = dist[x] + 1;
                tata[y] = x;
                q[dr++] = y;
            }
        }
    }
    std::cout << dist[t] << '\n';
    if (dist[t] == -1) return 0;
    int k = 0;
    for (int x = t; x != 0; x = tata[x]) drum[k++] = x;
    for (int i = k - 1; i >= 0; --i) {
        std::cout << drum[i];
        if (i > 0) std::cout << ' ';
    }
    std::cout << '\n';
}

Pentru graful din imagine și s=1, t=4, rezultatul este 2, apoi 1 2 4. Pentru t=5, afișăm numai -1. Pentru s=t=5, afișăm 0, apoi 5, chiar dacă vârful este izolat.

Reprezentări și cost

Varianta clasică rezervă a[101][101] și tablouri auxiliare de 101 poziții. Varianta cu std::vector rezervă dimensiunile n+1. În ambele, vârfurile folosesc indicii 1..n, iar coada și traseul folosesc indici de la zero. Indicele descrescător pentru afișarea traseului este int, astfel încât poate ajunge la -1 fără o depășire nesemnată.

BFS cu matrice are timp O(n²) în cazul cel mai defavorabil. Reconstruirea adaugă cel mult O(n), deoarece un traseu minim nu are nevoie să repete un vârf. Memoria matricei este O(n²), plus O(n) pentru tablourile auxiliare. Faptul că am folosit BFS nu face automat implementarea O(n+m); acel cost presupune liste de vecini.

DFS nu înlocuiește BFS pentru această sarcină: prima cale găsită în adâncime poate fi mai lungă decât alta care pornește printr-un vecin diferit. De asemenea, zero nu poate reprezenta simultan „nevizitat” și distanța sursei; folosirea lui -1 elimină ambiguitatea.

Exersează

1. Ce distanță are traseul 3 7 2 8?
2. Pe muchiile 1-2, 2-3, 3-4, 1-4, ce traseu minim găsești de la 1 la 4?
3. Ce afișează programul pentru un singur vârf și s=t=1?

Răspunsuri: trei; 1 4, de lungime unu; 0 pe prima linie și 1 pe a doua. Urmează arborii, unde între două vârfuri există un singur lanț elementar.