Dərs 4: Qraflar

Bu dərsin qeydləri hələ tam deyil. Əlavə olunana qədər dərsin videosuna baxmağınız tövsiyə olunur. Sonda əlavə resurslar bölməsinə baxmağı da unutmayın.

Sonuncu dərs! Bu dərsdə qraflar haqqında danışacağıq. Qraflar haqqında saysız sayda alqoritm var, amma bu dərsdə elə şeylər öyrənəcəyik ki, əvvəlki respublika olimpiadalarına düşmüş məsələləri həll edə bilək.

Qraflar haqqında ümumi danış. Onları C++-da necə göstəririk (matrix və qonşuluq listi). Ağaclar haqqında danış.

Özünü yoxla
Ağac? məsələsini həll et.

Özünü yoxla
Ağac tap məsələsini həll et.

DFS haqqında daha geniş danış.

Özünü yoxla
Komponentlər məsələsini həll et.

Cycle tapmaq haqqında danış.

int n;
vector<vector<int>> adj;
vector<char> color;
vector<int> parent;
int cycle_start, cycle_end;

bool dfs(int v) {
    color[v] = 1;
    for (int u : adj[v]) {
        if (color[u] == 0) {
            parent[u] = v;
            if (dfs(u)) return true;
        } else if (color[u] == 1) {
            cycle_end = v;
            cycle_start = u;
            return true;
        }
    }
    color[v] = 2;
    return false;
}

void find_cycle() {
    color.assign(n, 0);
    parent.assign(n, -1);
    cycle_start = -1;

    for (int v = 0; v < n; v++) {
        if (color[v] == 0 && dfs(v)) break;
    }

    if (cycle_start == -1) {
        cout << "Cycle yoxdur" << endl;
    } else {
        vector<int> cycle;
        cycle.push_back(cycle_start);
        for (int v = cycle_end; v != cycle_start; v = parent[v])
            cycle.push_back(v);
        cycle.push_back(cycle_start);
        reverse(cycle.begin(), cycle.end());

        cout << "Cycle var: ";
        for (int v : cycle)
            cout << v << " ";
        cout << endl;
    }
}

İkili rəngləmə haqqında danış.

Özünü yoxla
İkili rəngləmə məsələsini həll et.

Özünü yoxla
Çayı keçmək məsələsini həll et.

Topological sort haqqında danış.

int n; // number of vertices
vector<vector<int>> adj; // adjacency list of graph
vector<bool> visited;
vector<int> ans;

void dfs(int v) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u])
            dfs(u);
    }
    ans.push_back(v);
}

void topological_sort() {
    visited.assign(n, false);
    ans.clear();
    for (int i = 0; i < n; ++i) {
        if (!visited[i])
            dfs(i);
    }
    reverse(ans.begin(), ans.end());
}

Özünü yoxla
Kurs cədvəli məsələsini həll et.

Xanalar üzərində DFS haqqında danış.

Özünü yoxla
Ən böyük ada məsələsini həll et.

BFS haqqında danış.

Özünü yoxla
Yanğın məsələsini həll et.

Özünü yoxla
Xətlər məsələsini həll et.

Özünü yoxla
Sehr qutusu məsələsini həll et.

Dijkstra alqoritmi haqqında danış.

const int INF = 1000000000;
vector<vector<pair<int, int>>> adj;
using pii = pair<int, int>;

void dijkstra(int s, vector<int> & d, vector<int> & p) {
    int n = adj.size();
    d.assign(n, INF);
    p.assign(n, -1);
    d[s] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, s});
    while (!q.empty()) {
        int v = q.top().second;
        int d_v = q.top().first;
        q.pop();
        if (d_v != d[v]) continue;
        for (auto edge : adj[v]) {
            int to = edge.first;
            int len = edge.second;
            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                p[to] = v;
                q.push({d[to], to});
            }
        }
    }
}

Özünü yoxla
Server məsələsini həll et.

Floyd-Warshall alqoritmi haqqında danış.

for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (d[i][k] < INF && d[k][j] < INF)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

Özünü yoxla
Qədim Azərbaycan məsələsini həll et.

Əlavə faydalı resurslar

• CSES Kitabında 11-16-cı fəsillər (maraqlananlar üçün bütün Qraflar bölməsi).
• USACO Guide Silver səhifəsində Depth First Search (DFS), Flood Fill və Introduction to Tree Algorithms bölmələri.
• USACO Guide Gold səhifəsində Breadth First Search (BFS), Topological Sort və Shortest Paths with Non-Negative Edge Weights bölmələri.
• cp-algorithms saytında BFS, DFS, Dijkstra, Floyd-Warshall, Cycle.