图是由节点（顶点）和连接节点的边组成的一种非线性数据结构。它用于表示不同对象之间的关系或网络结构。图可以用于建模和解决许多现实世界中的问题，例如社交网络分析、路线规划、图像处理等。

在图中，节点表示实体或对象，而边表示节点之间的关系。边可以是有向的（具有方向）或无向的（没有方向），并可以具有权重或标签来表示边的属性或距离。

有几种常见的图数据结构，包括：

邻接矩阵（Adjacency Matrix）：邻接矩阵是一个二维数组，用于表示图中节点之间的连接关系。矩阵的行和列分别代表图中的节点，矩阵元素表示节点之间的边或连接。如果节点 i 和节点 j 之间有边存在，则邻接矩阵的 (i, j) 位置上的值为 1 或权重值，否则为 0 或表示不存在的标记。邻接矩阵适用于稠密图，但对于大型稀疏图来说会占用较多的内存空间
邻接列表（Adjacency List）：邻接列表使用链表或数组的列表来表示节点及其相邻节点的关系。每个节点都有一个列表，列出与其直接相连的节点。邻接列表适用于稀疏图，因为它只需要存储节点的相邻节点信息，可以节省内存空间。
关联矩阵（Incidence Matrix）：关联矩阵使用二维矩阵表示节点和边之间的关系。矩阵的行代表节点，列代表边，矩阵元素表示节点和边之间的关联关系。如果节点 i 是边 j 的起点，则矩阵的 (i, j) 位置上的值为 1 或权重值，如果节点 i 是边 j 的终点，则该位置上的值为 -1。关联矩阵适用于有向图以及边有多个属性的图。
哈希表或字典（Hash Table or Dictionary）：链表表示法是一种灵活的图数据结构，使用节点和边的链表来表示图。每个节点包含节点的信息以及指向其相邻节点的指针。边也可以作为链表节点的一部分存储。链表表示法适用于动态图或需要频繁地添加和删除节点和边的情况。

图的邻接矩阵

在C++中，可以使用二维数组来表示图的邻接矩阵。以下是一个简单的示例代码，展示了如何使用邻接矩阵表示有向图：

#include <iostream>
#include <vector>// 定义图类
class Graph {
private:int numVertices;  // 图中的节点数std::vector<std::vector<int>> adjacencyMatrix;  // 邻接矩阵public:// 构造函数Graph(int numVertices) : numVertices(numVertices) {// 初始化邻接矩阵为全零adjacencyMatrix.resize(numVertices, std::vector<int>(numVertices, 0));}// 添加边void addEdge(int src, int dest) {// 在邻接矩阵中设置边的连接关系adjacencyMatrix[src][dest] = 1;}// 打印邻接矩阵void printAdjacencyMatrix() {for (int i = 0; i < numVertices; ++i) {for (int j = 0; j < numVertices; ++j) {std::cout << adjacencyMatrix[i][j] << " ";}std::cout << std::endl;}}
};int main() {// 创建一个包含5个节点的有向图Graph graph(5);// 添加边graph.addEdge(0, 1);graph.addEdge(0, 4);graph.addEdge(1, 2);graph.addEdge(1, 3);graph.addEdge(2, 3);graph.addEdge(3, 4);// 打印邻接矩阵graph.printAdjacencyMatrix();return 0;
}

上述代码中，首先定义了一个Graph类，其中包含私有成员变量numVertices表示节点数，以及adjacencyMatrix用于存储邻接矩阵。构造函数初始化邻接矩阵为全零。

通过addEdge函数可以向图中添加边，该函数会在邻接矩阵中设置对应位置的值为 1 来表示节点之间的连接关系。

最后，通过printAdjacencyMatrix函数可以打印邻接矩阵的内容。运行结果为：

请注意，上述代码只展示了有向图的邻接矩阵表示方法。如果需要表示无向图，可以将邻接矩阵设置为对称矩阵，即在设置边连接关系时同时设置两个对称位置的值为 1。

图的邻接表

在C++中，可以使用链表来实现图的邻接表。每个节点通过一个链表存储其相邻节点的信息。以下是一个简单的示例代码，展示了如何使用链表实现图的邻接表表示：

#include <iostream>// 定义图节点的结构
struct Node {int dest;       // 相邻节点的目标Node* next;     // 指向下一个相邻节点的指针
};// 定义图类
class Graph {
private:int numVertices;    // 图中的节点数Node** adjacencyList;   // 邻接表public:// 构造函数Graph(int numVertices) : numVertices(numVertices) {adjacencyList = new Node*[numVertices]();// 初始化邻接表为空for (int i = 0; i < numVertices; ++i) {adjacencyList[i] = nullptr;}}// 添加边void addEdge(int src, int dest) {// 创建新的节点Node* newNode = new Node;newNode->dest = dest;newNode->next = nullptr;// 将新节点插入到src节点的邻接列表头部newNode->next = adjacencyList[src];adjacencyList[src] = newNode;// 对于无向图，还需插入反向边newNode = new Node;newNode->dest = src;newNode->next = nullptr;newNode->next = adjacencyList[dest];adjacencyList[dest] = newNode;}// 打印邻接表void printAdjacencyList() {for (int i = 0; i < numVertices; ++i) {Node* currentNode = adjacencyList[i];std::cout << "顶点 " << i << " 的邻接列表: ";while (currentNode != nullptr) {std::cout << currentNode->dest << " ";currentNode = currentNode->next;}std::cout << std::endl;}}// 析构函数，释放内存~Graph() {for (int i = 0; i < numVertices; ++i) {Node* currentNode = adjacencyList[i];while (currentNode != nullptr) {Node* nextNode = currentNode->next;delete currentNode;currentNode = nextNode;}}delete[] adjacencyList;}
};int main() {// 创建一个包含5个节点的无向图Graph graph(5);// 添加边graph.addEdge(0, 1);graph.addEdge(0, 4);graph.addEdge(1, 2);graph.addEdge(1, 3);graph.addEdge(2, 3);graph.addEdge(3, 4);// 打印邻接表graph.printAdjacencyList();return 0;
}

以下是使用邻接表表示图的示例代码：

#include <iostream>
#include <vector>class Graph {
private:int numVertices;                // 图中的节点数std::vector<std::vector<int>> adjList;   // 邻接表public:// 构造函数Graph(int numVertices) : numVertices(numVertices) {adjList.resize(numVertices);}// 添加边void addEdge(int src, int dest) {adjList[src].push_back(dest);adjList[dest].push_back(src);   // 对于无向图，需要添加反向的边}// 打印邻接表void printGraph() {for (int i = 0; i < numVertices; ++i) {std::cout << "节点 " << i << " 的相邻节点：";for (int neighbor : adjList[i]) {std::cout << neighbor << " ";}std::cout << std::endl;}}
};int main() {// 创建一个包含5个节点的图Graph graph(5);// 添加边graph.addEdge(0, 1);graph.addEdge(0, 2);graph.addEdge(1, 3);graph.addEdge(2, 3);graph.addEdge(2, 4);graph.addEdge(3, 4);// 打印邻接表graph.printGraph();return 0;
}

在上述代码中，我们定义了一个Graph类来表示图。使用邻接表作为内部数据结构，使用std::vector<std::vector<int>> adjList来存储图的邻接表，其中每个向量表示节点的相邻节点列表。

addEdge函数用于向图中添加边，它将目标节点添加到源节点的相邻节点列表中，并对于无向图，还需要添加反向的边。

printGraph函数用于打印图的邻接表。它遍历每个节点，并输出其相邻节点列表。

在示例代码中，我们创建了一个包含5个节点的图，并添加了一些边。然后，通过调用printGraph函数，打印图的邻接表。

这种邻接表表示法对于稀疏图（边相对较少）非常高效，可以快速查找每个节点的相邻节点，并节省存储空间。