🕸️ 圖論學習指南

什麼是圖？

圖（Graph）是一種由頂點（Vertex）和邊（Edge）組成的非線性資料結構，用於表示物件之間的關係。

圖的類型

• 無向圖（Undirected Graph）：邊沒有方向，A-B 等同於 B-A
• 有向圖（Directed Graph）：邊有方向，A→B 不同於 B→A
• 加權圖（Weighted Graph）：邊具有權重（距離、成本等）
• 有環圖（Cyclic Graph）：存在至少一個環
• 無環圖（Acyclic Graph）：不存在環

圖的表示方法

1. 鄰接矩陣（Adjacency Matrix）

2. 鄰接串列（Adjacency List）

圖的演算法

程式碼範例 - BFS 與 DFS

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

class Graph {
private:
    int V;
    vector<vector<int>> adj;
    
public:
    Graph(int v) : V(v), adj(v) {}
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);  // 無向圖
    }
    
    // BFS 廣度優先搜尋
    void BFS(int start) {
        vector<bool> visited(V, false);
        queue<int> q;
        
        visited[start] = true;
        q.push(start);
        
        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            cout << curr << " ";
            
            for (int neighbor : adj[curr]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
        cout << endl;
    }
    
    // DFS 深度優先搜尋
    void DFS(int start) {
        vector<bool> visited(V, false);
        DFSUtil(start, visited);
        cout << endl;
    }
    
private:
    void DFSUtil(int curr, vector<bool>& visited) {
        visited[curr] = true;
        cout << curr << " ";
        
        for (int neighbor : adj[curr]) {
            if (!visited[neighbor]) {
                DFSUtil(neighbor, visited);
            }
        }
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.addEdge(3, 4);
    
    cout << "BFS (從 0 開始): ";
    g.BFS(0);  // 0 1 2 3 4
    
    cout << "DFS (從 0 開始): ";
    g.DFS(0);  // 0 1 3 4 2
    
    return 0;
}