C++ 图的保姆级讲解
一、前言
在 C++ 编程中，图是一种用于描述对象之间复杂关系的重要数据结构。它由顶点和边组成，边可以是有向的或者无向的。
二、图的基本概念
- 顶点（Vertex）：图中的节点，表示对象或实体。
- 边（Edge）：连接顶点的线段，表示顶点之间的关系。
- 有向边：具有明确的起点和终点。
- 无向边：没有明确的起点和终点，两个顶点之间的关系是相互的。
三、图的表示方式
- 邻接矩阵
- 原理：使用一个二维数组来表示顶点之间的连接关系。
- 优点：查询某个顶点与其他顶点的连接情况非常快速。
- 缺点：空间复杂度较高，对于稀疏图（边的数量相对较少的图）会浪费大量空间。
- 示例：
const int MAX_VERTICES = 100;
int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES]; // 假设最多有 100 个顶点
// 初始化邻接矩阵
for (int i = 0; i < MAX_VERTICES; ++i) {
for (int j = 0; j < MAX_VERTICES; ++j) {
adjacencyMatrix[i][j] = 0; // 初始化为 0，表示没有边连接
}
}
// 假设添加一条从顶点 1 到顶点 2 的边
adjacencyMatrix[1][2] = 1;
- 邻接表
- 原理：为每个顶点创建一个链表，链表中存储与该顶点相邻的顶点。
- 优点：节省空间，尤其对于稀疏图。
- 缺点：查询特定顶点的相邻顶点相对复杂。
- 示例：
struct Node {
int vertex;
Node* next;
};
class Graph {
private:
int numVertices;
Node** adjacencyList;
public:
Graph(int numVertices) {
this->numVertices = numVertices;
adjacencyList = new Node*[numVertices];
for (int i = 0; i < numVertices; ++i) {
adjacencyList[i] = NULL;
}
}
void addEdge(int source, int destination) {
Node* newNode = new Node;
newNode->vertex = destination;
newNode->next = adjacencyList[source];
adjacencyList[source] = newNode;
// 如果是无向图，还需要添加反向的边
newNode = new Node;
newNode->vertex = source;
newNode->next = adjacencyList[destination];
adjacencyList[destination] = newNode;
}
// 其他相关操作
};
- 链式前向星
- 原理：使用数组存储边，通过指针将边连接起来。
- 优点：空间效率较高，同时能较方便地进行遍历和操作。
- 示例：
const int MAX_EDGES = 1000; // 假设最大边数
struct Edge {
int from, to, next;
};
Edge edges[MAX_EDGES];
int head[MAX_VERTICES]; // 记录每个顶点的第一条边在 edges 数组中的索引
int edgeCount = 0;
// 添加边的函数
void addEdge(int from, int to) {
edges[edgeCount].from = from;
edges[edgeCount].to = to;
edges[edgeCount].next = head[from];
head[from] = edgeCount++;
}
// 遍历邻接边
for (int i = head[vertex]; i!= -1; i = edges[i].next) {
int neighbor = edges[i].to;
// 处理邻接顶点
}
四、图的遍历
深度优先搜索（Depth-First Search，DFS）
原理：从起始顶点开始，沿着一条路径尽可能深地访问顶点，直到无法继续，然后回溯。
特点：
- 适合探索图的深度和复杂的分支结构。
- 可能会陷入过深的路径，导致在某些情况下效率较低。
- 常用于解决与路径搜索、连通性判断等问题。
示例：
bool visited[MAX_VERTICES]; // 全局数组用于标记顶点是否已访问
void dfs(int vertex, Graph graph) {
visited[vertex] = true;
// 处理当前顶点
Node* current = graph.adjacencyList[vertex];
while (current!= NULL) {
if (!visited[current->vertex]) {
dfs(current->vertex, graph);
}
current = current->next;
}
}
广度优先搜索（Breadth-First Search，BFS）
原理：从起始顶点开始，逐层地访问相邻顶点，先访问距离起始顶点近的顶点。
特点：
- 适合寻找最短路径或最小步数问题。
- 从初始点扩散，不会像深搜一样陷入过深的情况。
- 常用于解决与最短距离、层次遍历等相关的问题。
示例：
#include <queue>
void bfs(int startVertex, Graph graph) {
bool visited[MAX_VERTICES] = {false};
queue<int> queue;
visited[startVertex] = true;
queue.push(startVertex);
while (!queue.empty()) {
int currentVertex = queue.front();
queue.pop();
// 处理当前顶点
Node* current = graph.adjacencyList[currentVertex];
while (current!= NULL) {
if (!visited[current->vertex]) {
visited[current->vertex] = true;
queue.push(current->vertex);
}
current = current->next;
}
}
}
作者制作不易，点个赞吧(^▽^)，把作品的热度顶顶！
© 2024 本内容版权归梅耀元所有，未经授权请勿转载。