图论1（c++）

图论1（C++）

图论是计算机科学中研究图结构及其应用的数学分支，在算法设计、网络分析、人工智能等领域具有广泛的应用。本文将深入剖析图论的核心概念，包括图的表示、遍历算法（DFS和BFS），并提供可运行的C++代码示例，帮助读者从原理到实践全面掌握图论基础。## 图的基本概念与表示图由顶点（Vertex）和边（Edge）组成，通常表示为G=(V, E)，其中V是顶点集，E是边集。根据边的方向性，图分为有向图和无向图；根据边是否带权重，分为有权图和无权图。在C++中，图的表示方法主要有两种：-邻接矩阵：使用二维数组int graph[n][n]，graph[i][j]表示顶点i到j的边是否存在或权重。适用于稠密图，但空间复杂度为O(V²)。-邻接表：使用vector<int> adj[n]或vector<vector<int>> adj，每个顶点维护一个相邻顶点列表。适用于稀疏图，空间复杂度为O(V+E)。邻接表是实际开发中最常用的表示方法，因为大多数图都是稀疏的。下面是一个使用邻接表表示有向图的C++代码示例：cpp#include <iostream>#include <vector>using namespace std;// 使用邻接表表示有向图class Graph {private: int V; // 顶点数 vector<vector<int>> adj; // 邻接表public: // 构造函数：初始化顶点数和邻接表 Graph(int vertices) : V(vertices) { adj.resize(V); } // 添加有向边：从u到v void addEdge(int u, int v) { adj[u].push_back(v); // 将v加入u的邻接表 } // 打印图的邻接表 void printGraph() { cout << "Graph Adjacency List:" << endl; for (int i = 0; i < V; ++i) { cout << "Vertex " << i << ": "; for (int neighbor : adj[i]) { cout << neighbor << " "; } cout << endl; } }};int main() { // 创建一个包含5个顶点的图 Graph g(5); // 添加边 g.addEdge(0, 1); g.addEdge(0, 4); g.addEdge(1, 2); g.addEdge(1, 3); g.addEdge(2, 3); g.addEdge(3, 4); // 打印图 g.printGraph(); return 0;}这段代码演示了如何用邻接表构建一个有向图。运行后，输出将显示每个顶点的邻接列表，例如顶点0连接1和4。## 深度优先搜索（DFS）原理与实现深度优先搜索（Depth-First Search，DFS）是一种沿着一条路径尽可能深入搜索的算法，直到无法继续才回溯。其核心原理是使用栈（递归或显式栈）来跟踪路径，确保每个顶点只被访问一次。### 算法原理1. 从起始顶点开始，标记为已访问。2. 递归地访问当前顶点的每个未访问邻接顶点。3. 如果当前顶点没有未访问的邻接顶点，则回溯到上一个顶点。4. 重复直到所有可达顶点都被访问。DFS的时间复杂度为O(V+E)，空间复杂度为O(V)（递归栈深度）。它常用于拓扑排序、连通分量检测、迷宫求解等场景。### C++实现示例下面是一个完整的DFS遍历实现，包含递归版本和迭代版本（使用显式栈）：cpp#include <iostream>#include <vector>#include <stack>using namespace std;// 深度优先搜索类class DFSGraph {private: int V; vector<vector<int>> adj; // 递归辅助函数 void DFSUtil(int v, vector<bool>& visited) { // 标记当前顶点为已访问并打印 visited[v] = true; cout << v << " "; // 递归访问所有未访问的邻接顶点 for (int neighbor : adj[v]) { if (!visited[neighbor]) { DFSUtil(neighbor, visited); } } }public: DFSGraph(int vertices) : V(vertices) { adj.resize(V); } void addEdge(int u, int v) { adj[u].push_back(v); // 有向图 } // 递归DFS（从顶点0开始） void DFSRecursive(int start) { vector<bool> visited(V, false); cout << "DFS Recursive (start=" << start << "): "; DFSUtil(start, visited); cout << endl; } // 迭代DFS（使用显式栈） void DFSIterative(int start) { vector<bool> visited(V, false); stack<int> s; s.push(start); cout << "DFS Iterative (start=" << start << "): "; while (!s.empty()) { int v = s.top(); s.pop(); // 如果顶点未访问，则标记并处理 if (!visited[v]) { visited[v] = true; cout << v << " "; // 将邻接顶点逆序入栈，保持与递归相同的顺序 for (auto it = adj[v].rbegin(); it != adj[v].rend(); ++it) { if (!visited[*it]) { s.push(*it); } } } } cout << endl; }};int main() { // 创建一个图 DFSGraph g(6); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(2, 4); g.addEdge(2, 5); g.addEdge(3, 4); // 执行两种DFS g.DFSRecursive(0); g.DFSIterative(0); return 0;}运行此代码，输出将显示DFS从顶点0开始的遍历顺序，递归和迭代版本结果一致（例如：0 1 3 4 2 5）。注意迭代版本中逆序入栈是为了模拟递归的访问顺序。## 广度优先搜索（BFS）原理与实现广度优先搜索（Breadth-First Search，BFS）是一种逐层扩展搜索的算法，类似于树的层序遍历。其核心原理是使用队列来管理待访问的顶点，确保按距离递增顺序遍历。### 算法原理1. 从起始顶点开始，标记为已访问并加入队列。2. 从队列中取出一个顶点，访问其所有未访问的邻接顶点，标记后加入队列。3. 重复直到队列为空。BFS的时间复杂度同样为O(V+E)，空间复杂度为O(V)（队列大小）。它常用于最短路径（无权图）、连通分量、网络广播等场景。### C++实现示例下面是一个完整的BFS实现，包含从单源点开始的遍历：cpp#include <iostream>#include <vector>#include <queue>using namespace std;// 广度优先搜索类class BFSGraph {private: int V; vector<vector<int>> adj;public: BFSGraph(int vertices) : V(vertices) { adj.resize(V); } void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); // 无向图，添加双向边 } // 从顶点start开始进行BFS void BFS(int start) { vector<bool> visited(V, false); queue<int> q; // 初始化：标记起始顶点并加入队列 visited[start] = true; q.push(start); cout << "BFS (start=" << start << "): "; while (!q.empty()) { int v = q.front(); q.pop(); cout << v << " "; // 遍历所有未访问的邻接顶点 for (int neighbor : adj[v]) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } cout << endl; } // 带距离计算的BFS（返回从start到所有顶点的最短距离） vector<int> BFSWithDistance(int start) { vector<int> distance(V, -1); // -1表示不可达 queue<int> q; distance[start] = 0; q.push(start); while (!q.empty()) { int v = q.front(); q.pop(); for (int neighbor : adj[v]) { if (distance[neighbor] == -1) { distance[neighbor] = distance[v] + 1; q.push(neighbor); } } } return distance; }};int main() { // 创建一个无向图 BFSGraph g(6); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(2, 4); g.addEdge(2, 5); g.addEdge(3, 4); // 执行BFS g.BFS(0); // 计算并打印距离 vector<int> dist = g.BFSWithDistance(0); cout << "Distances from vertex 0:" << endl; for (int i = 0; i < dist.size(); ++i) { cout << "Distance to " << i << ": " << dist[i] << endl; } return 0;}运行此代码，BFS输出将从0开始按层次遍历（例如：0 1 2 3 4 5），距离数组显示每个顶点到0的最短边数（如顶点4距离为2）。## 总结本文深入剖析了图论的核心概念和基础算法，重点讲解了图的邻接表表示、深度优先搜索（DFS）和广度优先搜索（BFS）的原理与实现。通过可运行的C++代码示例，读者可以直观理解两种遍历算法的差异：DFS适合探索路径的深度和回溯，常用于拓扑排序、连通分量等问题；BFS则按层次扩展，特别适合求解无权图的最短路径。掌握这些基础是学习更高级图算法（如Dijkstra、Kruskal、Floyd-Warshall等）的前提。在实际开发中，选择合适的图表示和遍历策略能显著提升算法效率，例如邻接表用于稀疏图，邻接矩阵用于需要快速边查询的稠密图。希望本文能为读者在图论学习的道路上打下坚实基础。