C++ 图论简介与实现\n\n图论是计算机科学中一个重要的领域，用于研究图数据结构以及图算法。图由节点（顶点）和连接节点的边组成，可以用于表示各种关系和网络结构。在本篇博客中，我们将介绍C++中常用的图论算法，并给出相应的代码实现。\n\n## 图的表示\n\n图可以用多种方式进行表示，常见的有邻接矩阵和邻接链表。在C++中，我们可以使用二维数组或者容器来表示图。\n\n### 邻接矩阵表示\n\n邻接矩阵是一个二维数组，用于表示图中每个节点之间的连接关系。如果节点i和节点j之间有一条边，则邻接矩阵中的第i行第j列和第j行第i列的元素为1，否则为0。\n\ncpp\nconst int MAX_NODES = 100;\nint adjMatrix[MAX_NODES][MAX_NODES];\n\nvoid addEdge(int u, int v) {\n adjMatrix[u][v] = adjMatrix[v][u] = 1;\n}\n\n\n### 邻接链表表示\n\n邻接链表是一种更灵活的图表示方法，它使用一个数组或者容器来存储每个节点的邻居节点。在C++中，我们可以使用vector或者list来实现邻接链表。\n\ncpp\nconst int MAX_NODES = 100;\nvector<int> adjList[MAX_NODES];\n\nvoid addEdge(int u, int v) {\n adjList[u].push_back(v);\n adjList[v].push_back(u);\n}\n\n\n## 图的遍历\n\n图的遍历是指以某个节点为起点，依次访问图中的所有节点。常见的图遍历算法有深度优先搜索（DFS）和广度优先搜索（BFS）。\n\n### 深度优先搜索\n\n深度优先搜索是一种递归的图遍历算法，它从起点开始，依次访问起点的邻居节点，然后再访问邻居节点的邻居节点，直到遍历完所有的节点。\n\ncpp\nbool visited[MAX_NODES];\n\nvoid dfs(int u) {\n visited[u] = true;\n cout << u << " ";\n\n for (int v : adjList[u]) {\n if (!visited[v]) {\n dfs(v);\n }\n }\n}\n\n\n### 广度优先搜索\n\n广度优先搜索是一种非递归的图遍历算法，它从起点开始，依次访问起点的邻居节点，然后再访问邻居节点的邻居节点，直到遍历完所有的节点。广度优先搜索使用队列来保存待访问的节点。\n\ncpp\nbool visited[MAX_NODES];\n\nvoid bfs(int u) {\n queue<int> q;\n visited[u] = true;\n q.push(u);\n\n while (!q.empty()) {\n int v = q.front();\n q.pop();\n cout << v << " ";\n\n for (int w : adjList[v]) {\n if (!visited[w]) {\n visited[w] = true;\n q.push(w);\n }\n }\n }\n}\n\n\n## 图的最短路径\n\n最短路径是指在图中找到两个节点之间最短的路径。常见的最短路径算法有Dijkstra算法和Bellman-Ford算法。\n\n### Dijkstra算法\n\nDijkstra算法是一种贪心算法，用于求解带权图中的最短路径。它从起点开始，依次更新起点到其他节点的最短路径，并选择当前最短路径的节点作为下一个节点。\n\ncpp\nconst int INF = INT_MAX;\n\nvoid dijkstra(int start) {\n vector<int> dist(MAX_NODES, INF);\n dist[start] = 0;\n priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;\n pq.push({0, start});\n\n while (!pq.empty()) {\n int u = pq.top().second;\n pq.pop();\n\n for (int v : adjList[u]) {\n int weight = 1; // 假设边的权重都为1\n if (dist[u] + weight < dist[v]) {\n dist[v] = dist[u] + weight;\n pq.push({dist[v], v});\n }\n }\n }\n}\n\n\n### Bellman-Ford算法\n\nBellman-Ford算法是一种动态规划算法，用于求解带权图中的最短路径。它从起点开始，依次更新起点到其他节点的最短路径，直到没有更新操作为止。\n\ncpp\nconst int INF = INT_MAX;\n\nvoid bellmanFord(int start) {\n vector<int> dist(MAX_NODES, INF);\n dist[start] = 0;\n\n for (int i = 0; i < MAX_NODES - 1; i++) {\n for (int u = 0; u < MAX_NODES; u++) {\n for (int v : adjList[u]) {\n int weight = 1; // 假设边的权重都为1\n if (dist[u] + weight < dist[v]) {\n dist[v] = dist[u] + weight;\n }\n }\n }\n }\n}\n\n\n## 总结\n\n图论在计算机科学中有着广泛的应用，涉及到图的表示、遍历和最短路径等问题。本篇博客介绍了C++中常用的图论算法，并给出了相应的代码实现。希望对读者能有所帮助。