Graph คืออะไร ?

เขียนทางคณิตศาสตร์ได้ว่า G = (V, E)

ตัวอย่าง Graph ในโลกจริง

Graph ถูกใช้ใน Algorithm และ Competitive Programming จำนวนมาก

Directed vs Undirected Graph

Weighted Graph vs Unweighted Graph

คำศัพท์พื้นฐานของ Graph

แนวคิดเหล่านี้จะถูกใช้ใน Graph Algorithms ต่อไป

ปัญหาในการเก็บข้อมูล Graph

ดังนั้นเราจำเป็นต้องมี Graph Representation

ตัวอย่าง Input ของ Graph

Ubon Srisaket
Buriram Surin 
Buriram Yasothon
Surin Srisaket
Yasothon Ubon

5 4
1 3 
1 2
3 4
2 5

คำถามคือ เราจะเก็บข้อมูลนี้ในโปรแกรมอย่างไร?

วิธีเก็บแบบพื้นฐาน (Naive Approach)

ทำให้ Algorithm บางตัวทำงานช้าลงมาก

วิธีเก็บ Graph ที่นิยมใช้

เราจะเริ่มจากอะไรดี ?

ซึ่งจะเป็นพื้นฐานของ Graph Algorithms ทั้งหมด

Adjacency Matrix

เหมาะกับ Graph ที่มี Edge จำนวนมาก

ตัวอย่าง Graph

//Vertices = {"Annie","Bennie","Cody","Danny","Eddy"}
Vertices = {1,2,3,4,5}

Edges
1 - 2
1 - 3
2 - 3
4 - 5

เราจะเปลี่ยน Graph นี้ให้เป็น Matrix

Matrix Representation

    1 2 3 4
1 [ 0 1 1 0 ]
2 [ 1 0 0 1 ]
3 [ 1 0 0 1 ]
4 [ 0 1 1 0 ]

ค่า 1 หมายถึง มี Edge เชื่อมกัน

คุณสมบัติของ Adjacency Matrix

C++ Implementation

const int MAXN = 100;

int adj[MAXN][MAXN];

int main() {

    int n, m;
    cin >> n >> m;

    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;

        adj[u][v] = 1;
        adj[v][u] = 1;
    }
}

Time & Space Complexity

ถ้า V ใหญ่มาก Matrix จะใช้ memory มาก

ควรใช้ Adjacency Matrix เมื่อไร ?

ต่อไปเราจะเรียนรู้วิธีที่นิยมใช้มากกว่าใน Competitive Programming

Adjacency List

ตัวอย่าง Graph

Vertices = {1,2,3,4}

Edges
1 - 2
1 - 3
2 - 4
3 - 4

เราจะเก็บ Graph นี้ในรูปแบบ Adjacency List

Adjacency List Representation

1 : 2 3
2 : 1 4
3 : 1 4
4 : 2 3

แถวแต่ละแถวคือ Vertex และเพื่อนบ้าน

แนวคิดของ Adjacency List

Vertex 1 → [2,3]
Vertex 2 → [1,4]
Vertex 3 → [1,4]
Vertex 4 → [2,3]

แต่ละ Vertex จะเก็บเฉพาะ Edge ที่มีอยู่จริง

C++ Implementation

const int MAXN = 100;

vector adj[MAXN];

int main(){

    int n, m;
    cin >> n >> m;

    for(int i = 0; i < m; i++){

        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);

    }
}

การวนดูเพื่อนบ้าน

for(int v : adj[u]){
    cout << v << endl;
}

ใช้สำหรับ algorithm เช่น DFS / BFS

Time & Space Complexity

Matrix vs List

ดังนั้น Algorithm ส่วนใหญ่จะใช้ Adjacency List

Graph Connectivity Problem

ปัญหาเหล่านี้สามารถแก้ได้ด้วย Disjoint Set Union

Disjoint Set คืออะไร ?

ตัวอย่าง Disjoint Sets

Set 1 : {1,2,3}
Set 2 : {4,5}
Set 3 : {6}

แต่ละ element จะมี representative

Operations ใน DSU

ใช้ตรวจสอบว่า element อยู่ใน set เดียวกันหรือไม่

การแทน DSU ด้วย Tree

1
|
2
|
3

Root ของ tree คือ representative ของ set

Initialization

const int MAXN = 100005;

int parent[MAXN];

void make_set(int n){

    for(int i=1;i<=n;i++)
        parent[i] = i;

}

ใช้หา root ของ set

Find Operation

int find(int x){

    if(parent[x] == x)
        return x;

    return find(parent[x]);

}

ใช้หา root ของ set

Union Operation

void unite(int a, int b){

    a = find(a);
    b = find(b);

    if(a != b)
        parent[b] = a;

}

ใช้รวมสอง set ให้เป็น set เดียวกัน

ปัญหาของ DSU แบบพื้นฐาน

1
|
2
|
3
|
4
|
5

การทำ find() อาจใช้เวลาถึง O(N)

วิธีแก้ปัญหา

เทคนิคเหล่านี้ทำให้ DSU ทำงานได้เร็วมาก

Path Compression

ก่อน Find

1
|
2
|
3
|
4

หลังจาก Find จะทำให้ node ชี้ไปที่ root โดยตรง

Path Compression Implementation

int find(int x){

    if(parent[x] != x)
        parent[x] = find(parent[x]);

    return parent[x];

}

ทำให้ Tree มีความลึกน้อยลง

Union by Rank

Union by Rank Implementation

int parent[MAXN];
int rank[MAXN];

void unite(int a, int b){

    a = find(a);
    b = find(b);

    if(a != b){

        if(rank[a] < rank[b])
            swap(a,b);

        parent[b] = a;

        if(rank[a] == rank[b])
            rank[a]++;

    }

}

Complexity หลัง Optimization

ซึ่งถือว่า เกือบ O(1) ในทางปฏิบัติ

ตัวอย่างข้อมูลนำเข้า (dsu01.in)

6 3
1 2
2 3
4 5

union(1,2)
union(2,3)
union(4,5)

ผลลัพธ์หลังทำ Union

Set 1 : {1,2,3}
Set 2 : {4,5}
Set 3 : {6}

node ที่มี root เดียวกัน จะอยู่ใน set เดียวกัน

ตัวอย่างโปรแกรม DSU แบบสมบูรณ์

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int parent[MAXN];
int rankv[MAXN];

int find_set(int x){

    if(parent[x] != x)
        parent[x] = find_set(parent[x]);

    return parent[x];
}

void unite(int a,int b){

    a = find_set(a);
    b = find_set(b);

    if(a != b){

        if(rankv[a] < rankv[b])
            swap(a,b);

        parent[b] = a;

        if(rankv[a] == rankv[b])
            rankv[a]++;
    }
}

int main(){

    int N,M;
    cin >> N >> M;

    for(int i=1;i<=N;i++){
        parent[i] = i;
        rankv[i] = 0;
    }

    for(int i=0;i<M;i++){
        int a,b;
        cin >> a >> b;
        unite(a,b);
    }

    map<int, vector<int>> groups;

    for(int i=1;i<=N;i++){
        int r = find_set(i);
        groups[r].push_back(i);
    }

    int id = 1;

    for(auto g : groups){

        cout << "Set " << id++ << " : ";

        for(int x : g.second)
            cout << x << " ";

        cout << endl;
    }

}

Visual Tree of DSU

        1
       / \
      2   3
     /
    4
   /
  5

โครงสร้างของ DSU สามารถมองเป็น ต้นไม้ (Tree) โดย root คือ representative ของ set

Before Path Compression

find(5)

Traversal Path

5 → 4 → 2 → 1

ถ้า tree ลึกมาก การทำ find() จะใช้เวลามากขึ้น

After Path Compression

        1
     / / | \
    2 3  4  5

หลังจากเรียก find() node ทุกตัวจะชี้ตรงไปที่ root

ทำให้การค้นหาครั้งต่อไปเร็วขึ้นมาก