图论1C图论是计算机科学中研究图结构及其应用的数学分支在算法设计、网络分析、人工智能等领域具有广泛的应用。本文将深入剖析图论的核心概念包括图的表示、遍历算法DFS和BFS并提供可运行的C代码示例帮助读者从原理到实践全面掌握图论基础。## 图的基本概念与表示图由顶点Vertex和边Edge组成通常表示为G(V, E)其中V是顶点集E是边集。根据边的方向性图分为有向图和无向图根据边是否带权重分为有权图和无权图。在C中图的表示方法主要有两种-邻接矩阵使用二维数组int graph[n][n]graph[i][j]表示顶点i到j的边是否存在或权重。适用于稠密图但空间复杂度为O(V²)。-邻接表使用vectorint adj[n]或vectorvectorint adj每个顶点维护一个相邻顶点列表。适用于稀疏图空间复杂度为O(VE)。邻接表是实际开发中最常用的表示方法因为大多数图都是稀疏的。下面是一个使用邻接表表示有向图的C代码示例cpp#include iostream#include vectorusing namespace std;// 使用邻接表表示有向图class Graph {private: int V; // 顶点数 vectorvectorint 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 SearchDFS是一种沿着一条路径尽可能深入搜索的算法直到无法继续才回溯。其核心原理是使用栈递归或显式栈来跟踪路径确保每个顶点只被访问一次。### 算法原理1. 从起始顶点开始标记为已访问。2. 递归地访问当前顶点的每个未访问邻接顶点。3. 如果当前顶点没有未访问的邻接顶点则回溯到上一个顶点。4. 重复直到所有可达顶点都被访问。DFS的时间复杂度为O(VE)空间复杂度为O(V)递归栈深度。它常用于拓扑排序、连通分量检测、迷宫求解等场景。### C实现示例下面是一个完整的DFS遍历实现包含递归版本和迭代版本使用显式栈cpp#include iostream#include vector#include stackusing namespace std;// 深度优先搜索类class DFSGraph {private: int V; vectorvectorint adj; // 递归辅助函数 void DFSUtil(int v, vectorbool 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) { vectorbool visited(V, false); cout DFS Recursive (start start ): ; DFSUtil(start, visited); cout endl; } // 迭代DFS使用显式栈 void DFSIterative(int start) { vectorbool visited(V, false); stackint 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 SearchBFS是一种逐层扩展搜索的算法类似于树的层序遍历。其核心原理是使用队列来管理待访问的顶点确保按距离递增顺序遍历。### 算法原理1. 从起始顶点开始标记为已访问并加入队列。2. 从队列中取出一个顶点访问其所有未访问的邻接顶点标记后加入队列。3. 重复直到队列为空。BFS的时间复杂度同样为O(VE)空间复杂度为O(V)队列大小。它常用于最短路径无权图、连通分量、网络广播等场景。### C实现示例下面是一个完整的BFS实现包含从单源点开始的遍历cpp#include iostream#include vector#include queueusing namespace std;// 广度优先搜索类class BFSGraph {private: int V; vectorvectorint 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) { vectorbool visited(V, false); queueint 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到所有顶点的最短距离 vectorint BFSWithDistance(int start) { vectorint distance(V, -1); // -1表示不可达 queueint 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); // 计算并打印距离 vectorint 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等的前提。在实际开发中选择合适的图表示和遍历策略能显著提升算法效率例如邻接表用于稀疏图邻接矩阵用于需要快速边查询的稠密图。希望本文能为读者在图论学习的道路上打下坚实基础。
