[Hướng dẫn] Cơ bản về đồ thị

doreamonhihi

 Khi nói đến đồ thị, đa số chúng ta sẽ nghĩ đến đồ thị hàm số được học ở chương trình phổ thông hay là các đồ thị số liệu báo cáo Tuy nhiên, trong thực tế, đồ thị không chỉ là những biểu đồ hay đồ thị hàm số mà còn là 1 ngành riêng được gọi là lý thuyết đồ thị. Bạn đã bao giờ thắc mắc những mini map trong các game chiến thuật thời gian thực hay các đường đi trong game được tạo nên từ gì chưa ? Trong bài viết này, mình sẽ không đi quá sâu vào những lý thuyết ở trong ngành khoa học máy tính hay toán học mà sẽ ở mức độ vừa phải đủ để có thể áp dụng cho việc làm game và lập trình đa số các ứng dụng sau này

 Chú ý: Để có thể hiểu được tối đa bài viết, mình khuyến khích các bạn nên đọc trước về C/ C++ và nắm một số kiến thức cơ bản (biết trước rồi càng tốt   ):

- Nhập, xuất.

- Biến, mảng, con trỏ.

- Vector (thư viện STL của C++, tất nhiên có thể có lựa chọn khác là cài bằng mảng thường hoặc có thể tự cài bằng mảng động qua việc dùng con trỏ, nhưng việc đó sẽ còn phức tạp hơn và nếu không cẩn thận sẽ khiến chương trình chạy lỗi.

I. Định nghĩa:

- Một đồ thị G(V, E) là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối với các đỉnh đó, trong đó V (Vertices) là tập các đỉnh, còn E (Edges) là tập các cạnh.

- Mỗi cạnh thuộc E trong đồ thị được biểu diễn bởi 2 đỉnh (u, v) với u, v là các đỉnh thuộc V.

- Phân loại:

1. G được gọi là đơn đồ thị nếu giữa hai đỉnh u, v của V có nhiều nhất là 1 cạnh trong E nối từ u tới v.

2. G được gọi là đa đồ thị nếu giữa hai đỉnh u, v của V có thể có nhiều hơn 1 cạnh trong E nối từ u tới v (Hiển nhiên đơn đồ thị cũng là đa đồ thị).

3. G được gọi là đồ thịvô hướng nếu các cạnh trong E là không định hướng, tức là cạnh nối hai đỉnh u, v bất kỳ cũng là cạnh nối hai đỉnh v, u. Hay nói cách khác, tập E gồm các cặp (u, v) không tính thứ tự (u, v)≡(v, u)
4. G được gọi là đồ thị có hướng nếu các cạnh trong E là có định hướng, có thể có cạnh nối từ đỉnh u tới đỉnh v nhưng chưa chắc đã có cạnh nối từđỉnh v tới đỉnh u. Hay nói cách khác, tập E gồm các cặp (u, v) có tính thứ tự: (u, v) ≠ (v, u). Trong đồ thị có hướng, các cạnh được gọi là các cung. Đồ thị vô hướng cũng có thể coi là đồ thị có hướng nếu như ta coi cạnh nối hai đỉnhu, v bất kỳ tương đương với hai cung (u, v) và (v, u).

(Theo Lý thuyết đồ thị - Lê Minh Hoàng)

II - Một số khái niệm:

• Đối với đồ thị vô hướng G = (V, E). Xét một cạnh e ∈ E, nếu e = (u, v) thì ta nói hai đỉnh u và v là kề nhau (adjacent) và cạnh e này liên thuộc (incident) với đỉnh u và đỉnh v.

• Với một đỉnh v trong đồ thị, ta định nghĩa bậc (degree) của v, ký hiệu deg(v) là số cạnh liênthuộc với v. Dễ thấy rằng trên đơn đồ thị thì số cạnh liên thuộc với v cũng là số đỉnh kề với v.

(Theo Lý thuyết đồ thị - Lê Minh Hoàng)

III - Biểu diễn:

 Có 3 cách biểu diễn:

- Ma trận kề

- Danh sách kề

- Danh sách cạnh

 Trong bài viết này, dựa vào tính phổ biến và hiệu quả, mình sẽ chỉ trình bày 2 cách đầu tiên.

1.Ma trận kề:

- Sử dụng 1 ma trận vuông n x n nhằm biểu diễn cạnh (u, v) tồn tại trong đồ thị.
- Trong đồ thị đơn, G[u][v]=1 nếu tồn tại cạnh nối từ đỉnh u tới đỉnh v, ngược lại = 0. Còn trong đồ thị đa, G[u][v] = số cạnh nối từ đỉnh u tới đỉnh v.

- Nếu ma trận biểu diễn đồ thị vô hướng thì tổng các số trên hàng i = tổng các số trên cột i = bậc của đỉnh i. Đồng thời lúc đó, ma trận trở thành ma trận đối xứng (G[u][v]=G[v][u])

- Nếu ma trận biểu diễn đồ thị có hướng thì
+ Tổng các số trên hàng i = Bán bậc ra của đỉnh i

+ Tổng các số trên cột i = Bán bậc vào của đỉnh i

 Cài đặt (đối với đơn đồ thị có hướng)

#include<stdio.h>
void Init(int **&G, int m)
{
    G=new int*[m]();
    for (int i=0; i<m; i++)
        G[i]=new int[m]();
}
void Input(int **&G, int n)
{
    while (n--)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        G[u][v]=1;
    }
}
int main()
{
    int **G;
    int m, n;
    scanf("%d %d", &m, &n);
    Init(G, m);
    Input(G, n);
}

Chú ý:
- Với đồ thị vô hướng, chỉ cần thêm G[u][v]=G[v][u]=1. Với đa đồ thị thì G[u][v] là số cạnh nối từ u đến v

- Do đây là đơn đồ thị nên có thể dùng mảng bool, trong trường hợp đa đồ thị thì thay mảng bool = int để có thể biểu diễn số lượng cạnh nối từ u đến v.

- Dấu "()" trong G=new int*[m]() và G[i]=new int[m]() dùng để khởi tạo mảng với giá trị = 0 (nếu không thì khi khởi tạo sẽ là giá trị ngẫu nhiên, sẽ mất công phải gán lại G[u][v]=0 cho những cạnh (u, v) không tồn tại).

2. Danh sách kề:

- Tuy ma trận kề có ưu điểm là dễ cài đặt và dễ hiểu, nhưng có nhược điểm vô cùng lớn là tốn bộ nhớ và thời gian (do sẽ phải duyệt cạnh không tồn tại nữa).
- Để khắc phục vấn đề trên, trong trường hợp mà số lượng đỉnh lớn thì ta có thể sử dụng danh sách kề để chỉ để lưu những cạnh tồn tại.

Cài đặt (đối với đơn đồ thị có hướng)

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector< vector<int> > G;
    int m, n;
    cin>>m>>n;
    G.assign(m, vector<int> (0, 0));
    while (n--)
    {
        int u, v;
        cin>>u>>v;
        G[u].push_back(v);
    }
}

Chú ý:

- Ngoài cách dùng vector, các bạn có thể dùng mảng động tạo bằng con trỏ hoặc danh sách liên kết tạo bằng con trỏ. Tuy nhiên những cách đó khá phức tạp (đặc biệt là mảng động tạo bằng con trỏ, nếu không cẩn thận sẽ làm tăng thời gian chạy chương trình và có thể dẫn đến TLE đối với những bạn nào tham gia các cuộc thi lập trình thi đấu).

- Nếu bạn đọc không hiểu, hãy tưởng tượng mảng 2 chiều m x n đơn giản là m mảng 1 chiều kích thước n ô. Với mỗi mảng G[u] ta có các G[u][i] là các đỉnh có cạnh nối với u. Mỗi đỉnh v có cạnh nối với u sẽ được push_back( đẩy vào) mảng G[v]
- Với đồ thị vô hướng , thêm G[v].push_back(u) sau G[u].push_back(v)

Dang_Khoa

Đồ thị thường áp dụng vào trường hợp nào trong làm game vậy em, nếu suy từ vấn đề sang giải pháp thì sẽ dễ hình dung hơn

doreamonhihi

Dang_Khoa said:

Đồ thị thường áp dụng vào trường hợp nào trong làm game vậy em, nếu suy từ vấn đề sang giải pháp thì sẽ dễ hình dung hơn

Em định có lap khác thì viết cụ thể hơn phần ứng dụng ở bài sau (phần tìm đường đi, cũng là ứng dụng cụ thể dễ hiểu nhất của đồ thị) (mới trả lại lap cho bên bán để hoàn tiền )