圖（Graph）的概念

定義圖（Graph）是一種非線性數據結構，用於表示對象（稱為頂點或節點）之間的關系。它由兩個集合構成：

頂點集 V (Vertices)：包含圖中的所有頂點。
邊集 E (Edges)：包含頂點之間連接的所有邊，每條邊可以是無向的（即任意方向均可通行）或有向的（具有起點和終點）。

術語

無向圖：邊沒有方向，例如 (u, v) 與 (v, u) 是相同的邊。
有向圖：邊具有方向，(u, v) 和 (v, u) 表示不同的方向關系。
權圖：邊可能帶有權重，代表從一個頂點到另一個頂點的成本或距離。
鄰接：如果兩個頂點通過一條邊相連，則它們互為鄰接頂點。

表示方法

鄰接矩陣：使用二維數組來存儲圖，數組的行和列對應頂點，數組的值表示兩個頂點之間是否有邊（通常為佈爾值，如果是權圖則為權值）。
鄰接表：每個頂點維護一個列表，列表中存儲的是與其相鄰的其他頂點（對於有向圖，可能會區分出入度和出度鄰接表）。

C 實現基礎示例

以下是一個簡單的無向圖使用鄰接表實現的C 代碼框架：

#include <iostream>
#include <vector>
// 定義一個結構體表示頂點
struct Vertex {
    int id;
    std::vector<int> neighbors; // 鄰接頂點列表
};
// 定義一個類表示圖
class Graph {
public:
    Graph(int numVertices) : vertices(numVertices) {}
    void addEdge(int src, int dest) { // 添加無向邊
        vertices[src].neighbors.push_back(dest);
        vertices[dest].neighbors.push_back(src);
    }
private:
    std::vector<Vertex> vertices;
};
int main() {
    Graph g(5); // 創建一個含有5個頂點的圖
    g.addEdge(0, 1); // 添加邊 (0, 1)
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    // ... 更多邊的添加
    // 輸出某個頂點的鄰接頂點
    for (auto neighbor : g.vertices[0].neighbors) {
        std::cout << "Vertex 0 is connected to vertex: " << neighbor << std::endl;
    }
    return 0;
}

這隻是最基礎的實現方式，實際應用中還需要考慮內存管理、各種圖遍歷算法（如深度優先搜索DFS、廣度優先搜索BFS）、最小生成樹算法（如Prim、Kruskal）、最短路徑算法（如Dijkstra、Floyd-Warshall）等復雜情況。在權圖中，通常會在鄰接表或者鄰接矩陣的基礎上增加權重信息的存儲。

數據結構——圖表

圖（Graph）的概念

C 實現基礎示例