Algoritmi → Grafovi i stabla → Uvod u grafove: pojmovi i predstavljanje

Uvod u grafove: pojmovi i predstavljanje

Osnovni pojmovi

    1 ----- 2
    |       |  \
    |       |   5
    4 ----- 3

Ovaj graf ima 5 čvorova i 5 grana: 1–2, 1–4, 2–3, 2–5 i 3–4.

Vrste grafova:

• neusmeren – grana važi u oba smera (prijateljstvo, dvosmerna ulica);
• usmeren – grana u → v ide samo u jednom smeru (jednosmerna ulica, „zadatak u mora pre zadatka v“);
• težinski – svaka grana ima broj (dužinu, cenu, vreme).

U zadacima se graf skoro uvek zadaje ovako: u prvom redu broj čvorova n i broj grana m, a zatim m redova sa po dva čvora koje grana spaja (i težinom, ako je graf težinski).

Matrica susedstva

Matrica a dimenzija n × n: a[u][v] = 1 ako postoji grana između u i v, inače 0. Za neusmeren graf matrica je simetrična.

#include <iostream>
using namespace std;

int a[101][101];        // matrica susedstva, čvorovi 1..n (n <= 100)

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        a[u][v] = 1;    // neusmeren graf: grana u oba smera
        a[v][u] = 1;
    }
    // stepen svakog čvora = broj jedinica u njegovoj vrsti
    for (int u = 1; u <= n; u++) {
        int stepen = 0;
        for (int v = 1; v <= n; v++) stepen += a[u][v];
        cout << "stepen(" << u << ") = " << stepen << endl;
    }
    return 0;
}

Provera „da li su u i v povezani granom“ traje O(1), ali matrica zauzima n² memorije – za n = 10⁵ to je 10¹⁰ polja, nemoguće.

Lista susedstva

Za svaki čvor čuvamo spisak njegovih suseda – vector<int> graf[n + 1]. Memorija je srazmerna broju grana, pa ovo radi i za milion čvorova. Ovo je predstavljanje koje se koristi u skoro svim algoritmima na grafovima (BFS, DFS, Dijkstra…).

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graf(n + 1);   // graf[u] = spisak suseda čvora u
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graf[u].push_back(v);
        graf[v].push_back(u);          // za usmeren graf ovaj red se izostavlja
    }
    for (int u = 1; u <= n; u++) {
        cout << u << ":";
        for (int v : graf[u]) cout << " " << v;
        cout << endl;
    }
    return 0;
}

Za težinski graf u listu stavljamo parove (sused, težina): vector<vector<pair<int,int>>> graf(n + 1); i graf[u].push_back({v, w});

Lista grana

Ponekad je dovoljno samo zapamtiti sve grane u jedan niz. Tako rade Kruskalov i Bellman-Fordov algoritam:

struct Grana {
    int u, v, w;      // krajevi i težina
};
vector<Grana> grane(m);
for (auto &g : grane) cin >> g.u >> g.v >> g.w;

Matrica kao graf

Tabla ili lavirint su graf i bez zapisivanja grana: polje (i, j) je čvor, a susedi su mu polja gore, dole, levo i desno. Susede obilazimo pomoću nizova pomeraja:

int di[4] = {-1, 1, 0, 0};
int dj[4] = {0, 0, -1, 1};
for (int k = 0; k < 4; k++) {
    int ni = i + di[k], nj = j + dj[k];
    if (ni >= 0 && ni < n && nj >= 0 && nj < m && tabla[ni][nj] != '#') {
        // (ni, nj) je sused polja (i, j)
    }
}

Tako se rešavaju zadaci Broj ostrva i Najkraći put u lavirintu.

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje