พื้นฐาน Graph

Graph เป็นโครงสร้างข้อมูลที่ประกอบด้วย โหนด (Vertices/Nodes) และ เส้นเชื่อม (Edges) ใช้แทนความสัมพันธ์ระหว่างสิ่งต่างๆ

องค์ประกอบของ Graph

• Vertex (V) หรือ Node: จุดในกราฟ
• Edge (E): เส้นเชื่อมระหว่างสอง vertices

ประเภทของ Graph

ประเภท	คำอธิบาย
Undirected	Edge ไม่มีทิศทาง (สองทาง)
Directed	Edge มีทิศทาง (ทางเดียว)
Weighted	Edge มีน้ำหนัก/ค่าใช้จ่าย
Unweighted	Edge ไม่มีน้ำหนัก
Simple	ไม่มี self-loop และ multiple edges
Connected	มีเส้นทางเชื่อมทุก vertex
Tree	Connected graph ที่ไม่มี cycle
DAG	Directed Acyclic Graph

การเก็บข้อมูล Graph

1. Adjacency Matrix

เก็บเป็น 2D array ขนาด $V \times V$

int n = 5; // จำนวน vertices
vector<vector<int>> adj(n, vector<int>(n, 0));

// เพิ่ม edge (u, v)
void addEdge(int u, int v) {
    adj[u][v] = 1;
    adj[v][u] = 1; // สำหรับ undirected graph
}

// ตรวจสอบว่ามี edge (u, v) หรือไม่
bool hasEdge(int u, int v) {
    return adj[u][v] != 0;
}

ข้อดี:

• ตรวจสอบ edge ใช้เวลา $O(1)$
• เหมาะกับ Dense Graph

ข้อเสีย:

• ใช้ memory $O(V^2)$
• ไม่เหมาะกับ Sparse Graph

2. Adjacency List (แนะนำ)

เก็บ list ของ neighbors สำหรับแต่ละ vertex

int n = 5;
vector<vector<int>> adj(n);

// เพิ่ม edge (u, v)
void addEdge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u); // สำหรับ undirected graph
}

// Weighted graph
vector<vector<pair<int, int>>> adjW(n);

void addWeightedEdge(int u, int v, int w) {
    adjW[u].push_back({v, w});
    adjW[v].push_back({u, w});
}

ข้อดี:

• ใช้ memory $O(V + E)$
• เหมาะกับ Sparse Graph (ส่วนใหญ่ในการแข่งขัน)

ข้อเสีย:

• ตรวจสอบ edge ใช้เวลา $O(degree)$

3. Edge List

เก็บ list ของ edges ทั้งหมด

struct Edge {
    int u, v, w; // from, to, weight
};

vector<Edge> edges;

void addEdge(int u, int v, int w) {
    edges.push_back({u, v, w});
}

ใช้สำหรับ:

• Algorithm ที่ต้องเรียง edges (Kruskal’s MST)
• Bellman-Ford Algorithm

Input Reading

Undirected Unweighted Graph

5 6
1 2
1 3
2 3
2 4
3 5
4 5

int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1);

for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
}

Directed Weighted Graph

5 6
1 2 10
1 3 5
2 3 2
2 4 1
3 5 7
4 5 4

int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> adj(n + 1);

for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back({v, w});
    // adj[v].push_back({u, w}); // ถ้าเป็น undirected
}

คำศัพท์สำคัญ

Degree

จำนวน edges ที่เชื่อมกับ vertex

// Undirected graph
int degree(int v) {
    return adj[v].size();
}

// Directed graph
int inDegree[n], outDegree[n];

for (int u = 0; u < n; u++) {
    for (int v : adj[u]) {
        outDegree[u]++;
        inDegree[v]++;
    }
}

Path & Walk

• Walk: ลำดับของ vertices ที่ติดกันมี edge เชื่อม
• Path: Walk ที่ไม่ผ่าน vertex ซ้ำ
• Cycle: Path ที่เริ่มและจบที่ vertex เดียวกัน

Connected Components

กลุ่มของ vertices ที่มีเส้นทางเชื่อมถึงกัน

vector<bool> visited(n + 1, false);
int components = 0;

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

// นับ connected components
for (int i = 1; i <= n; i++) {
    if (!visited[i]) {
        dfs(i);
        components++;
    }
}

ประเภท Graph พิเศษ

Tree

Graph ที่:

• มี $n$ vertices และ $n-1$ edges
• Connected และไม่มี cycle
• มี unique path ระหว่างทุกคู่ vertex

// Tree จะมี edges = vertices - 1
bool isTree(int n, int m) {
    if (m != n - 1) return false;
    // ตรวจสอบว่า connected
    dfs(1);
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) return false;
    }
    return true;
}

Bipartite Graph

Graph ที่แบ่ง vertices ได้เป็น 2 กลุ่ม โดย edges เชื่อมระหว่างกลุ่มเท่านั้น

vector<int> color(n + 1, -1);

bool isBipartite(int start) {
    queue<int> q;
    q.push(start);
    color[start] = 0;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : adj[u]) {
            if (color[v] == -1) {
                color[v] = 1 - color[u];
                q.push(v);
            } else if (color[v] == color[u]) {
                return false; // มี odd cycle
            }
        }
    }
    return true;
}

DAG (Directed Acyclic Graph)

Directed graph ที่ไม่มี cycle

ใช้ใน:

• Topological Sort
• Dynamic Programming on DAG
• Dependency Resolution

Handshaking Lemma

ผลรวมของ degree ทั้งหมด = 2 × จำนวน edges

$\sum_{v \in V} deg(v) = 2|E|$

สรุป

วิธีเก็บ	Memory	Check Edge	Add Edge	Use Case
Adj Matrix	$O(V^2)$	$O(1)$	$O(1)$	Dense Graph
Adj List	$O(V+E)$	$O(deg)$	$O(1)$	Sparse Graph
Edge List	$O(E)$	$O(E)$	$O(1)$	Kruskal’s, Bellman-Ford

💡 Tip: ส่วนใหญ่ในการแข่งขันใช้ Adjacency List เพราะ graph มักจะเป็น sparse