图（Graph）数据结构
图（Graph）是一种重要的数据结构，用于表示事物之间的关系。它由一组顶点（Vertex）和连接这些顶点的边（Edge）组成。图常常用来描述物体之间复杂的关系，如网络、社交媒体、交通系统等。
图的基本定义
顶点（Vertex）：也称为节点，是图中的基本单位。
边（Edge）：连接两个顶点的线，表示它们之间的关系或连接。
- 无向图（Undirected Graph）：边没有方向，意味着如果顶点 A 与顶点 B 有一条边，那么 A 和 B 之间是对称的关系。
- 有向图（Directed Graph，简称 Digraph）：边有方向，意味着如果顶点 A 与顶点 B 之间有一条边（A → B），则从 A 到 B 有方向，但从 B 到 A 不一定有边。
权重（Weight）：边可能带有权重，表示两个顶点之间的关系的强度（如交通网络中的距离、社交网络中的亲密度等）。
图的表示方法
图可以通过多种方式进行表示，常见的表示方法有：
邻接矩阵（Adjacency Matrix）：
- 用一个二维矩阵来表示图，矩阵的行和列分别对应顶点，矩阵中的值表示顶点之间是否有边（如果有边，则为非零值；如果没有边，则为零值）。
- 优点：查找任意两个顶点之间是否有边非常方便（时间复杂度 O(1)）。
- 缺点：对于稀疏图来说，空间浪费严重，因为无论边的数量多少，矩阵大小始终是顶点数的平方。
邻接矩阵示例：
A B C D A 0 1 0 0 B 0 0 1 0 C 0 0 0 1 D 1 0 0 0邻接表（Adjacency List）：
- 用一个数组或链表数组来表示图，数组中的每个元素表示一个顶点，链表则存储与该顶点直接相连的顶点。
- 优点：空间利用高效，适用于稀疏图。
- 缺点：查找是否有一条边需要遍历相邻的顶点，时间复杂度为 O(d)，其中 d 是该顶点的度数。
邻接表示例：
A -> [B] B -> [C] C -> [D] D -> [A]边列表（Edge List）：
- 用一组边的集合来表示图，每条边是一个由两个顶点组成的二元组，表示这两个顶点之间有一条边。
- 优点：存储简单，适用于图的边操作。
- 缺点：不适合快速查找边的连接性或邻接关系。
边列表示例：
(A, B) (B, C) (C, D) (D, A)
图的分类
- 无向图（Undirected Graph）：
- 边没有方向，表示顶点之间的双向关系。即如果顶点 A 与顶点 B 之间有一条边，那么从 A 到 B 和从 B 到 A 都可以走。
- 有向图（Directed Graph）：
- 边有方向，表示顶点之间的单向关系。即如果从顶点 A 到顶点 B 有一条边（A → B），那么不能从 B 到 A 移动，除非存在一条单独的边（B → A）。
- 加权图（Weighted Graph）：
- 图的边具有权重，表示两个顶点之间的关系强度，通常在优化路径问题（如最短路径问题）时使用。
- 无权图（Unweighted Graph）：
- 图的边没有权重，表示顶点之间简单的连接关系。
- 连通图（Connected Graph）：
- 如果图是无向图，且图中的任意两个顶点之间都有路径相连，则称图是连通的。
- 非连通图（Disconnected Graph）：
- 如果图是无向图，且存在至少一对顶点没有路径相连，则称图是非连通的。
- 树（Tree）：
- 树是一个特殊的图，没有环且连通。树的一个重要性质是，树中有 n 个节点时，有 n-1 条边。
图的基本操作
图的基本操作包括：
添加顶点：向图中添加一个新的顶点。
删除顶点：从图中删除一个顶点及其所有相连的边。
添加边：向图中添加一条边（无向图时，需要在两个方向上都添加边）。
删除边：从图中删除一条边。
遍历图：
- 深度优先搜索（DFS，Depth-First Search）：从一个顶点出发，沿着边一直深入，直到无法继续深入为止，再回溯到上一个节点，继续寻找未访问的邻接节点。
- 广度优先搜索（BFS，Breadth-First Search）：从一个顶点出发，首先访问该顶点的所有邻接顶点，然后再访问它们的邻接顶点。
图的应用
图广泛应用于各个领域，以下是一些典型应用：
- 社交网络：每个人可以看作图中的一个顶点，人与人之间的关系可以看作图中的一条边。社交网络中的很多问题，如朋友推荐、社交圈分析、影响力传播等，都可以通过图来建模。
- 路径搜索：在地图应用中，可以将城市视为图的顶点，道路视为边，通过图算法（如 Dijkstra 算法、A* 算法等）来找到最短路径。
- 电路设计：电路中的元件和连接可以用图来表示，通过图的分析可以优化电路布局。
- 任务调度：在某些任务之间存在依赖关系时，可以将任务表示为图，通过图的分析来找出执行顺序。
- 网页排名（PageRank）：搜索引擎中的网页排名算法就是通过图来计算网页的相对重要性。
图的遍历算法
图的遍历是图算法中的基础，包括 深度优先搜索（DFS） 和 广度优先搜索（BFS）。
- 深度优先搜索（DFS）：
- 通过递归的方式进行搜索，优先深入到图的深层。
- 时间复杂度：O(V + E)，V 是顶点数，E 是边数。
- 广度优先搜索（BFS）：
- 通过队列的方式进行搜索，优先访问与当前节点距离较近的节点。
- 时间复杂度：O(V + E)，V 是顶点数，E 是边数。
总结
图是一种非常灵活且强大的数据结构，能够很好地表示和处理各种关系和依赖。它的应用范围广泛，涵盖了网络、社交、地图、任务调度等多个领域。掌握图的基本操作、遍历算法及其优化技巧，对于解决复杂问题至关重要。
图的代码实现（邻接表表示法）
#include <iostream>
using namespace std;
// 链表结构，表示邻接表中的节点
struct Node {
int vertex; // 目标顶点
Node* next; // 指向下一个邻接节点
};
// 图的类
class Graph {
private:
int V; // 顶点数
Node** adjList; // 邻接表，数组中每个元素是指向链表的指针
public:
// 构造函数
Graph(int V) {
this->V = V;
adjList = new Node*[V]; // 动态分配邻接表
for (int i = 0; i < V; i++) {
adjList[i] = nullptr; // 初始化为空
}
}
// 添加边（无向图）
void addEdge(int v, int w) {
Node* newNode = new Node{w, adjList[v]};
adjList[v] = newNode;
// 若是无向图，双向添加
newNode = new Node{v, adjList[w]};
adjList[w] = newNode;
}
// 深度优先搜索 (DFS)
void DFS(int start) {
bool* visited = new bool[V]();
DFSHelper(start, visited);
delete[] visited;
}
private:
void DFSHelper(int v, bool* visited) {
visited[v] = true;
cout << v << " ";
Node* node = adjList[v];
while (node) {
if (!visited[node->vertex]) {
DFSHelper(node->vertex, visited);
}
node = node->next;
}
}
public:
// 广度优先搜索 (BFS)
void BFS(int start) {
bool* visited = new bool[V]();
int* queue = new int[V]; // 队列数组
int front = 0, rear = 0;
queue[rear++] = start;
visited[start] = true;
while (front < rear) {
int v = queue[front++];
cout << v << " ";
// 遍历邻接表
Node* node = adjList[v];
while (node) {
if (!visited[node->vertex]) {
visited[node->vertex] = true;
queue[rear++] = node->vertex;
}
node = node->next;
}
}
delete[] visited;
delete[] queue;
}
// 析构函数（释放邻接表）
~Graph() {
for (int i = 0; i < V; i++) {
Node* node = adjList[i];
while (node) {
Node* temp = node;
node = node->next;
delete temp;
}
}
delete[] adjList;
}
};
// 主函数
int main() {
Graph g(6);
// 添加边
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 4);
g.addEdge(3, 5);
// 执行 DFS
cout << "DFS Traversal: ";
g.DFS(0);
cout << endl;
// 执行 BFS
cout << "BFS Traversal: ";
g.BFS(0);
cout << endl;
return 0;
}
代码讲解
1. 图的表示：
- 我们使用 邻接表（邻接链表）来表示图。每个顶点的邻接表是一个指向
int数组的指针。该数组存储该顶点的邻接节点和指向下一个邻接节点的指针。 addEdge(int v, int w)函数将一条从v到w的边加入到图中。在每次添加一条边时，我们为v分配一个新的邻接节点，并将该节点链接到v的邻接表中。
2. 深度优先搜索（DFS）算法：
- DFS 使用递归的方式（通过一个辅助函数
DFSHelper）进行遍历。我们用一个visited数组来记录哪些节点已被访问。 - 在 DFS 中，我们访问当前节点后，递归地访问它的所有邻接节点。
DFSHelper辅助函数会遍历当前节点的邻接表，对于每个未访问的邻接节点，递归调用DFSHelper。
3. 广度优先搜索（BFS）算法：
- BFS 使用一个队列来按层访问每个节点。我们首先将起始节点入队，然后逐个访问队列中的节点，访问时将它们的邻接节点入队。
BFSHelper辅助函数使用一个队列（queue数组）来模拟队列的行为，保证按顺序访问每一层的节点。
4. 内存管理：
- 在实现中，我们手动使用
new动态分配内存，并且在适当的位置使用delete[]来释放内存。 - 例如，
visited数组、queue队列、newAdjNode邻接节点都使用了new，因此在结束时要手动释放内存。
输出示例
DFS Traversal starting from vertex 0: 0 1 3 5 4 2
BFS Traversal starting from vertex 0: 0 1 2 3 4 5
