Đồ thị, BFS và DFS

#ifndef DO_THI_H
#define DO_THI_H

#include <stddef.h>

/* Cách 1: ma trận kề, dùng mảng phẳng để cấp phát một lần. */
typedef struct {
    int   *m;        /* m[u * V + v] khác 0 nếu có cạnh u tới v */
    size_t V;
} MaTran;

/* Cách 2: danh sách kề dạng CSR, tức mảng phẳng thay vì con trỏ.
   dinh[u] tới dinh[u+1] là khoảng chỉ số trong ke chứa láng giềng của u.
   Cách này tiết kiệm và thân thiện bộ nhớ đệm hơn danh sách liên kết. */
typedef struct {
    size_t *dinh;    /* V + 1 phần tử */
    int    *ke;      /* 2E phần tử với đồ thị vô hướng */
    int    *trong_so;
    size_t  V, E;
} DoThi;

#endif

#include <stdlib.h>
#include <string.h>

/* Dựng CSR từ danh sách cạnh. Hai lượt: đếm bậc, rồi điền.
   O(V + E) thời gian, không cấp phát tạm nào ngoài mảng bậc. */
int dt_dung(DoThi *g, size_t V, const int *u, const int *v, size_t E)
{
    g->dinh = calloc(V + 1, sizeof *g->dinh);
    g->ke   = malloc(2 * E * sizeof *g->ke);

    if (g->dinh == NULL || g->ke == NULL) {
        free(g->dinh); free(g->ke);

        return -1;
    }

    g->V = V;
    g->E = E;

    /* Lượt 1: đếm bậc của từng đỉnh, ghi vào dinh[i+1] */
    for (size_t i = 0; i < E; ++i) {
        ++g->dinh[(size_t)u[i] + 1];
        ++g->dinh[(size_t)v[i] + 1];
    }

    /* Tổng tiền tố: dinh[i] thành chỉ số bắt đầu của đỉnh i */
    for (size_t i = 0; i < V; ++i)
        g->dinh[i + 1] += g->dinh[i];

    /* Lượt 2: điền, dùng một mảng con trỏ ghi tạm */
    size_t *vi_tri = malloc(V * sizeof *vi_tri);

    if (vi_tri == NULL) { free(g->dinh); free(g->ke); return -1; }

    memcpy(vi_tri, g->dinh, V * sizeof *vi_tri);

    for (size_t i = 0; i < E; ++i) {
        g->ke[vi_tri[u[i]]++] = v[i];
        g->ke[vi_tri[v[i]]++] = u[i];
    }

    free(vi_tri);

    return 0;
}

#include <stdlib.h>

/* BFS từ đỉnh nguon. Ghi khoảng cách theo số cạnh vào kc,
   và đỉnh cha trên đường đi ngắn nhất vào cha.
   Trả về 0 nếu ổn, -1 nếu hết bộ nhớ. O(V + E). */
int bfs(const DoThi *g, int nguon, int *kc, int *cha)
{
    size_t *hang_doi = malloc(g->V * sizeof *hang_doi);

    if (hang_doi == NULL) return -1;

    for (size_t i = 0; i < g->V; ++i) { kc[i] = -1; cha[i] = -1; }

    size_t dau = 0, cuoi = 0;

    kc[nguon]        = 0;
    hang_doi[cuoi++] = (size_t)nguon;

    while (dau < cuoi) {
        size_t u = hang_doi[dau++];

        for (size_t i = g->dinh[u]; i < g->dinh[u + 1]; ++i) {
            int v = g->ke[i];

            if (kc[v] != -1) continue;      /* đã thăm */

            kc[v]            = kc[u] + 1;
            cha[v]           = (int)u;
            hang_doi[cuoi++] = (size_t)v;
        }
    }

    free(hang_doi);

    return 0;
}

/* Bản đệ quy, ngắn và tự nhiên. */
static void dfs_de_quy(const DoThi *g, size_t u, int *da_tham)
{
    da_tham[u] = 1;

    printf("%zu ", u);

    for (size_t i = g->dinh[u]; i < g->dinh[u + 1]; ++i) {
        int v = g->ke[i];

        if (!da_tham[v])
            dfs_de_quy(g, (size_t)v, da_tham);
    }
}

/* Bản lặp, dùng ngăn xếp tường minh. Không sợ tràn ngăn xếp. */
int dfs_lap(const DoThi *g, int nguon, int *da_tham)
{
    size_t *nx = malloc(g->V * sizeof *nx);

    if (nx == NULL) return -1;

    size_t n = 0;

    nx[n++] = (size_t)nguon;

    while (n > 0) {
        size_t u = nx[--n];

        if (da_tham[u]) continue;      /* có thể vào ngăn xếp nhiều lần */

        da_tham[u] = 1;
        printf("%zu ", u);

        /* Đẩy ngược để lấy ra theo đúng thứ tự láng giềng */
        for (size_t i = g->dinh[u + 1]; i-- > g->dinh[u]; ) {
            int v = g->ke[i];

            if (!da_tham[v]) nx[n++] = (size_t)v;
        }
    }

    free(nx);

    return 0;
}

/* Gán mỗi đỉnh một số hiệu thành phần. Trả về số thành phần.
   O(V + E). */
int thanh_phan(const DoThi *g, int *tp)
{
    for (size_t i = 0; i < g->V; ++i) tp[i] = -1;

    int so_tp = 0;

    for (size_t s = 0; s < g->V; ++s) {
        if (tp[s] != -1) continue;      /* đã thuộc một thành phần */

        /* BFS từ s, gán mọi đỉnh tới được số hiệu so_tp */
        size_t *hd  = malloc(g->V * sizeof *hd);

        if (hd == NULL) return -1;

        size_t dau = 0, cuoi = 0;

        tp[s]      = so_tp;
        hd[cuoi++] = s;

        while (dau < cuoi) {
            size_t u = hd[dau++];

            for (size_t i = g->dinh[u]; i < g->dinh[u + 1]; ++i) {
                int v = g->ke[i];

                if (tp[v] == -1) { tp[v] = so_tp; hd[cuoi++] = (size_t)v; }
            }
        }

        free(hd);
        ++so_tp;
    }

    return so_tp;
}

/* Mỗi điểm ảnh là một đỉnh, hai điểm kề nhau và cùng màu thì có cạnh.
   Tìm thành phần liên thông chính là tìm các vùng màu.
   Đây là thuật toán tô loang trong mọi phần mềm vẽ. */
static void to_loang(int *anh, int W, int H, int x, int y,
                     int mau_cu, int mau_moi)
{
    if (mau_cu == mau_moi) return;      /* nếu không thì lặp vô hạn */

    /* Bản lặp, tránh tràn ngăn xếp với vùng lớn */
    int   *nx = malloc((size_t)W * H * sizeof *nx);
    size_t n  = 0;

    if (nx == NULL) return;

    nx[n++] = y * W + x;

    while (n > 0) {
        int p = nx[--n];
        int px = p % W, py = p / W;

        if (px < 0 || px >= W || py < 0 || py >= H) continue;
        if (anh[p] != mau_cu) continue;

        anh[p] = mau_moi;

        if (px > 0)     nx[n++] = p - 1;
        if (px < W - 1) nx[n++] = p + 1;
        if (py > 0)     nx[n++] = p - W;
        if (py < H - 1) nx[n++] = p + W;
    }

    free(nx);
}

/* Đồ thị VÔ HƯỚNG: có chu trình nếu gặp một đỉnh đã thăm
   mà không phải đỉnh cha trực tiếp. */
static int co_chu_trinh_vo_huong(const DoThi *g, size_t u, int cha,
                                 int *da_tham)
{
    da_tham[u] = 1;

    for (size_t i = g->dinh[u]; i < g->dinh[u + 1]; ++i) {
        int v = g->ke[i];

        if (!da_tham[v]) {
            if (co_chu_trinh_vo_huong(g, (size_t)v, (int)u, da_tham))
                return 1;
        } else if (v != cha) {
            return 1;      /* cạnh ngược, tức có chu trình */
        }
    }

    return 0;
}

/* Đồ thị CÓ HƯỚNG: cần ba trạng thái, không phải hai.
     0 = chưa thăm
     1 = đang trong ngăn xếp đệ quy
     2 = đã xong

   Gặp một đỉnh ở trạng thái 1 nghĩa là quay lại chính nhánh đang đi,
   tức có chu trình. Gặp trạng thái 2 thì không sao. */
static int co_chu_trinh_co_huong(const DoThi *g, size_t u, int *trang_thai)
{
    trang_thai[u] = 1;

    for (size_t i = g->dinh[u]; i < g->dinh[u + 1]; ++i) {
        int v = g->ke[i];

        if (trang_thai[v] == 1) return 1;              /* chu trình */

        if (trang_thai[v] == 0 &&
            co_chu_trinh_co_huong(g, (size_t)v, trang_thai))
            return 1;
    }

    trang_thai[u] = 2;      /* xong nhánh này */

    return 0;
}

/* Cách 1: Kahn, dùng bậc vào và một hàng đợi.
   Trả về số đỉnh đã xếp. Nhỏ hơn V nghĩa là có chu trình. */
size_t to_po_kahn(const DoThi *g, int *ra)
{
    size_t *bac_vao = calloc(g->V, sizeof *bac_vao);
    size_t *hd      = malloc(g->V * sizeof *hd);

    if (bac_vao == NULL || hd == NULL) { free(bac_vao); free(hd); return 0; }

    for (size_t u = 0; u < g->V; ++u)
        for (size_t i = g->dinh[u]; i < g->dinh[u + 1]; ++i)
            ++bac_vao[g->ke[i]];

    size_t dau = 0, cuoi = 0;

    for (size_t u = 0; u < g->V; ++u)
        if (bac_vao[u] == 0) hd[cuoi++] = u;

    size_t k = 0;

    while (dau < cuoi) {
        size_t u = hd[dau++];

        ra[k++] = (int)u;

        for (size_t i = g->dinh[u]; i < g->dinh[u + 1]; ++i)
            if (--bac_vao[g->ke[i]] == 0)
                hd[cuoi++] = (size_t)g->ke[i];
    }

    free(bac_vao);
    free(hd);

    return k;      /* k < V nghĩa là có chu trình */
}

/* Cách 2: DFS, ghi đỉnh vào kết quả theo HẬU thứ tự rồi đảo ngược. */
static void to_po_dfs(const DoThi *g, size_t u, int *trang_thai,
                      int *ra, size_t *k)
{
    trang_thai[u] = 1;

    for (size_t i = g->dinh[u]; i < g->dinh[u + 1]; ++i)
        if (trang_thai[g->ke[i]] == 0)
            to_po_dfs(g, (size_t)g->ke[i], trang_thai, ra, k);

    trang_thai[u] = 2;
    ra[(*k)--]    = (int)u;      /* điền từ CUỐI mảng về đầu */
}