[toc]
## Các khái niệm
Đồ thị 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 đó. Được mô tả hình thức:
$$
G = (V, E)
$$
Trong đó:
- $V$ gọi là tập các đỉnh (Vertices) và $E$ gọi là tập các cạnh (Edges). Có thể coi $E$ là tập các cặp $(u,v)$ với $u, v \in V$.

### Đồ thị vô hướng
Đồ thị $G$ là đồ thị vô hướng khi $u$ nối với $v$ cũng là $v$ nối với $u$, $(u, v) = (v,u)$.

### Đồ thị có hướng
Đồ thị $G$ là đồ thị có hướng khi $u$ nối với $v$ khác $v$ nối với $u$, $(u, v) \neq (v,u)$.

## Biểu diễn đồ thị
### Ma trận kề
- Ma trận kề của đồ thị $𝐺$, ký hiệu $𝐵(𝐺)$, là một ma trận nhị phân cấp $𝑁 \times 𝑁$: $𝐵 = (𝐵_{𝑖,𝑗})$ với $𝐵_{𝑖,𝑗}$ được định nghĩa:
+ Với đồ thị không có trọng số
+ $𝐵_{𝑖,𝑗} = 1$ nếu có cạnh nối $𝑖$ tới $𝑗$
+ $𝐵_{𝑖,𝑗} = 0$ trong trường hợp ngược lại
+ Với đồ thị có trọng số
+ $𝐵_{𝑖,𝑗} = x$ nếu có cạnh nối $𝑖$ tới $𝑗$ với trọng số $x$
+ $𝐵_{𝑖,𝑗} = 0$ nếu không có cạnh nối $i$ tới $j$
- Trong c++ ta dùng mảng 2 chiều để biểu diễn ma trận kề.

### Danh sách kề
- Là danh sách các mảng hoặc danh sách liên kết, trong đó mỗi phần tử tương ứng với một đỉnh trong đồ thị. Mỗi phần tử trong danh sách này chứa thông tin về các đỉnh kề của đỉnh tương ứng đó.
- Trong C++ ta sử dụng một mảng `vector` để biểu diễn danh sách kề.

### Danh sách cạnh
- Là danh sách các cặp đỉnh, mỗi cặp đỉnh tương ứng với một cạnh trong đồ thị. Mỗi cạnh được biểu diễn bằng hai đỉnh mà nó kết nối.


## Duyệt đồ thị
### Theo chiều sâu (Depth-First Search - DFS)
Dựa trên ý tưởng quay lui. Ta sẽ đi toàn bộ đường, sau đó khi không thể đi được nữa ta sẽ quay lui để tìm đường khác.

vector <int> adj[MAX_N]; // danh sách kề
bool lab[MAX_N]; // mảng xác định một đỉnh đã được xét nếu là 1, chưa nếu là 0
void DFS(int u){
    // xử lý đỉnh u (tùy theo yêu cầu đề)
    lab[u] = 1; // đánh dấu đỉnh u đã được xét
    for (int i=0; i<adj[u].size(); i++){ // duyệt qua những đỉnh kề với đỉnh u đang xét
        int v = adj[u][i]; // v là đỉnh kề u
        if (lab[v] == 0){ // nếu đỉnh v chưa được xét
            DFS(v); // xét tiếp đỉnh v tiếp theo
        }
    }
}

### Theo chiều rộng (Breadth-First Search - BFS)
Ta sẽ tìm tất cả các đỉnh kề $s$, sau đó tiếp tục từ các đỉnh đó sẽ đến các đỉnh kề. Sử dụng `queue` để lưu các đỉnh sẽ được thăm.

vector <int> adj[MAX_N]; // danh sách kề
bool lab[MAX_N]; // mảng xác định một đỉnh đã được xét nếu là 1, chưa nếu là 0
void BFS(int s){
    queue <int> q;
    q.push(s); // đưa đỉnh bắt đầu vào hàng đợi
    // xử lý đỉnh s
    lab[s] = 1; // đánh dấu s đã được xét
    while(s.size() > 0){ // lặp khi hàng đợi khác rỗng
        int u = q.front(); // lấy ra phần tử đầu hàng đợi
        for (int i=0; i<adj[u].size(); i++){
            int v = adj[u][i];
            if (lab[v] == 0){ // nếu v chưa được xét
                // xử lý đỉnh v
                lab[v] = 1; // đánh dẫu đỉnh v đã được xét
                q.push(v); // đưa đỉnh kề chưa được xét vào hàng đợi để xét tiếp trong tương lai
            }
        }
    }
}


[Minh họa thuật toán ở đây](https://visualgo.net/en/dfsbfs)
## Một số bài toán về đồ thị
### Tìm đường đi ngắn nhất
#### Dijkstra
Thuật toán này đã được học ở môn Cấu Trúc Rời Rạc, chúng ta đã làm nhiều nên mình không cần nói chi tiết ở đây :v.

Thuật toán tìm đường đi ngắn nhất từ $1$ đỉnh đến các đỉnh còn lại trong đồ thị.
Độ phức tạp: $O(N\log(N))$

const int mN = 2e5 + 10; // khởi tạo giới hạn ban đầu
const long long oo = 1e18 + 10ll; // định nghĩa dương vô cùng
typedef pair<long long, int> pli; // định nghĩa lại kiểu dữ liệu để tiện hơn
int numNode, numEdge; // khai báo số đỉnh, số cạnh
long long d[mN]; // khởi tạo mảng khoảng cách
vector <pli> adj[mN]; // khai báo danh sách kề

void dijkstra(int start){ // gọi hàm dijkstra với đỉnh bắt đầu là start 
    priority_queue <pli, vector<pli>, greater<pli>> pq; // khai báo hàng đợi ưu tiên sắp xếp với ưu tiên trọng số giảm dần
    int u, v;
    long long du, uv;

    for (int i = 1; i <= numNode; ++i) d[i] = oo; // khởi tạo khoảng cách ban đầu là dương vô cùng
    d[start] = 0; // cho đỉnh bắt đầu có khoảng cách là 0
    pq.push(pli(0ll, start)); // đưa trọng số khoảng cách của đỉnh bắt đầu vào trong

    while (pq.size()) { // trong khi vẫn còn đỉnh trong hàng đợi
        u = pq.top().second; // lấy ra đỉnh u để xét tiếp các cạnh kế tiếp
        du = pq.top().first; // lấy ra khoảng cách ngắn nhất từ start đên u
        pq.pop(); // xóa ra khỏi hàng đợi ưu tiên
        if (du != d[u]) continue; // nếu đã xét từ trước thì không cần xét tiếp
        for (int i = 0; v=adj[u][i].second; i++) { // lấy đỉnh kề của u là v
            uv = adj[u][i].first; // lấy trọng số kề của u
            if (d[v] > du + uv) { // nếu trọng số khoảng cách của đỉnh v lớn hơn tổng khoảng cách từ đỉnh nguồn đến u và trọng số cạnh u đến v thì cập nhật lại trọng số khoảng cách mới cho đỉnh v
                d[v] = du + uv;
                pq.push(pli(d[v], v)); // đưa vào hàng đợi để xét tiếp các đỉnh kế với v
            }
        }
    }
}


### Tìm cây khung nhỏ nhất/lớn nhất
2 thuật toán này cũng đã quá quen với chúng ta ở môn Cấu trúc rời rạc.
#### Kruskal
Ta sẽ sử dụng cấu trúc dữ liệu [Disjoint set union](https://vnoi.info/wiki/algo/data-structures/disjoint-set-union.md) để có thể nối các cạnh vào thành cây khung và các cây khung với nhau.

int par[maxN]; 
//Lưu node gốc của tập hợp
//Nếu node đó là gốc thì mảng thể hiện số lượng node có trong tập hợp.
int root(int x){
    //tìm gốc của node đồng thời tối ưu cho những lần sau
    if(par[x] < 0? x:(par[x] = root(par[x])))
}

void union(int x, int y){
    //nếu đã chung gốc => chung tập hợp, không cần nối
    if((x = root(x) == (y = root(y)) return;
    //nếu số lượng ở tập x nhỏ hơn y, ta nối x vào y và ngược lại
    if(par[x] < par[y]) swap(x, y);
    par[x] += par[y];
    par[y] = x;
}

struct edge{
    //danh sách cạnh 
    int u, v, w;
    edge(int uu = 0, int vv = 0, int ww = 0){
        u = uu;
        v = vv;
        w = ww;
    }
    //overload
    bool operator < (edge& x){
        return this -> w < x.w;
    }
    bool operator <= (edge& x){
        return this -> w <= x.w;
    }
    bool operator > (edge& x){
        return this -> w > x.w;
    }
    bool operator >= (edge& x){
        return this -> w >= x.w;
    }
};
pair<vector<edge>, int> kruskal(vector<edge>& el){
    sort(el.begin(), el.end());
    vector<edge> spanningTree;
    for(int i = 1; i <= n; i++){
        par[i] = -1;
    }
    int edges = 0;
    //số cạnh trong cây khung = n - 1, chỉ cần chạy tới đó
    int totalWeight = 0;
    for(auto e: el){
        //nếu chung tập hợp, bỏ qua
        if(root(e.u) == root(e.v)) continue;
        totalWeight += e.w;
        union(e.u, e.v);
        spanningTree.push_back(e);
        edges++;
        if(edges == n - 1) break;
    }
    return make_pair(spanningTree, totalWeight);
}


#### Prim

typedef pair<int, int> ii; // định nghĩa kiểu dữ liệu để thuận tiện gọi hơn
const int mN = 2e5 + 10; // khởi tạo giới hạn
const int oo = 1e9 + 10ll; // khởi tạo dương vô cùng
int numNode, numEdge, d[mN]; // số đỉnh, số cạnh, trọng số khoảng cách
vector <ii> adj[mN]; // khai báo danh sách cạnh kề

int prim(int u) { // bắt đầu random ở một đỉnh bất kỳ
    int totalWeight = 0, v, du, uv; // khai báo
    priority_queue<ii, vector<ii>, greater<ii>> pq; // tạo một hàng đợi ưu tiên đề lấy trọng số nhỏ nhất để ưu tiên lấy cạnh đó ra
    for (int i = 1; i <= numNode; i++) d[i] = oo; // khởi tạo mọi đỉnh có khoảng cách dương vô cùng
    pq.push(ii(0, u)); // đưa đỉnh bắt đầu vào hàng đợi 
    d[u] = 0; // cho đỉnh bắt đầu khoảng cách là 0
    while (pq.size()) { // khi còn đỉnh để xét
        u = pq.top().second; // lấy ra đỉnh u để xét tiếp các cạnh kế tiếp
        du = pq.top().first; // lấy ra trọng số cạnh hiện tại
        pq.pop();  // xóa ra khỏi hàng đợi ưu tiên
        if (du != d[u]) continue; // nếu đã xét từ trước thì không cần xét tiếp
        totalWeight += du; // lấy cạnh thêm vào tăng đúng 1 lượng trọng số cạnh
        d[u] = 0; // xóa đỉnh u bằng cách gán trọng số bằng 0
        for (int i = 0; i < (int) adj[u].size(); i++) {
            v = adj[u][i].second; // xét đỉnh kế tiếp
            uv = adj[u][i].first; // xét cạnh kề
            if (d[v] > uv) { // nếu cạnh trước đó gán cho v chưa phải cạnh nhỏ nhất
                d[v] = uv; // cập nhật cạnh nhỏ nhất (u, v) cho tập cạnh
                pq.push({d[v], v}); // đưa vào hàng đợi để xét tiếp
            }
        }
    }
    return totalWeight; // trả về tổng số cạnh
}