图（Graph）的概念

定义 图（Graph）是一种非线性数据结构，用于表示对象（称为顶点或节点）之间的关系。它由两个集合构成：

1. 顶点集 V (Vertices)：包含图中的所有顶点。
2. 边集 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）等复杂情况。在权图中，通常会在邻接表或者邻接矩阵的基础上增加权重信息的存储。