C++-----图

一、图的结构

在 C++ 中，图可以用多种结构表示，常见的有邻接矩阵和邻接表。

邻接矩阵

使用二维数组 adjMatrix 来表示图中顶点之间的连接关系。对于无向图，如果 adjMatrix[i][j] 不为零，则表示顶点 i 和顶点 j 之间存在边；对于有权图，adjMatrix[i][j] 的值可以表示边的权重。对于无权图，可以用 1 表示有边，0 表示无边。

#include <iostream>
#include <vector>class GraphAdjMatrix {
private:int numVertices;std::vector<std::vector<int>> adjMatrix;
public:// 构造函数，初始化邻接矩阵GraphAdjMatrix(int vertices) : numVertices(vertices), adjMatrix(vertices, std::vector<int>(vertices, 0)) {}// 添加边void addEdge(int src, int dest, int weight = 1) {if (src >= 0 && src < numVertices && dest >= 0 && dest < numVertices) {adjMatrix[src][dest] = weight;// 对于无向图，添加反向边adjMatrix[dest][src] = weight; }}// 打印邻接矩阵void print() {for (int i = 0; i < numVertices; ++i) {for (int j = 0; j < numVertices; ++j) {std::cout << adjMatrix[i][j] << " ";}std::cout << std::endl;}}
};

邻接表

使用一个数组或向量，其中每个元素存储一个链表或向量，存储与该顶点相连的顶点。对于有权图，可以存储一个包含顶点和权重的结构体或 pair。

#include <iostream>
#include <vector>class GraphAdjList {
private:int numVertices;std::vector<std::vector<int>> adjList;
public:// 构造函数，初始化邻接表GraphAdjList(int vertices) : numVertices(vertices), adjList(vertices) {}// 添加边void addEdge(int src, int dest) {adjList[src].push_back(dest);// 对于无向图，添加反向边adjList[dest].push_back(src); }// 打印邻接表void print() {for (int i = 0; i < numVertices; ++i) {std::cout << i << " -> ";for (int neighbor : adjList[i]) {std::cout << neighbor << " ";}std::cout << std::endl;}}
};

二、图的遍历

图的遍历有深度优先搜索（DFS）和广度优先搜索（BFS）两种常见方法。

深度优先搜索 (DFS)

DFS 是一种递归算法，从起始顶点开始，尽可能深地访问图的分支。

#include <iostream>
#include <vector>class GraphDFS {
private:int numVertices;std::vector<std::vector<int>> adjList;std::vector<bool> visited;// 辅助函数，进行深度优先搜索void dfsUtil(int vertex) {visited[vertex] = true;std::cout << vertex << " ";for (int neighbor : adjList[vertex]) {if (!visited[neighbor]) {dfsUtil(neighbor);}}}
public:GraphDFS(int vertices) : numVertices(vertices), adjList(vertices), visited(vertices, false) {}// 添加边void addEdge(int src, int dest) {adjList[src].push_back(dest);// 对于无向图，添加反向边adjList[dest].push_back(src); }// 执行深度优先搜索void dfs(int startVertex) {dfsUtil(startVertex);}
};

广度优先搜索 (BFS)

BFS 是一种迭代算法，从起始顶点开始，逐层访问图的顶点。

#include <iostream>
#include <vector>
#include <queue>class GraphBFS {
private:int numVertices;std::vector<std::vector<int>> adjList;std::vector<bool> visited;public:GraphBFS(int vertices) : numVertices(vertices), adjList(vertices), visited(vertices, false) {}// 添加边void addEdge(int src, int dest) {adjList[src].push_back(dest);// 对于无向图，添加反向边adjList[dest].push_back(src); }// 执行广度优先搜索void bfs(int startVertex) {std::queue<int> q;visited[startVertex] = true;q.push(startVertex);while (!q.empty()) {int vertex = q.front();q.pop();std::cout << vertex << " ";for (int neighbor : adjList[vertex]) {if (!visited[neighbor]) {visited[neighbor] = true;q.push(neighbor);}}}}
};

三、最短路径算法

有多种最短路径算法，以下是 Dijkstra 算法的实现。

Dijkstra 算法

用于求解单源最短路径问题，适用于边权为非负的图。

#include <iostream>
#include <vector>
#include <queue>
#include <climits>class GraphDijkstra {
private:int numVertices;std::vector<std::vector<std::pair<int, int>>> adjList; // pair: (neighbor, weight)std::vector<int> dijkstra(int src) {std::vector<int> dist(numVertices, INT_MAX);dist[src] = 0;std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;pq.push({0, src});while (!pq.empty()) {int u = pq.top().second;pq.pop();for (auto neighbor : adjList[u]) {int v = neighbor.first;int weight = neighbor.second;if (dist[u] + weight < dist[v]) {dist[v] = dist[u] + weight;pq.push({dist[v], v});}}}return dist;}
public:GraphDijkstra(int vertices) : numVertices(vertices), adjList(vertices) {}// 添加边void addEdge(int src, int dest, int weight) {adjList[src].push_back({dest, weight});}// 打印从源点出发的最短路径void printShortestPaths(int src) {std::vector<int> dist = dijkstra(src);for (int i = 0; i < numVertices; ++i) {std::cout << "Distance from " << src << " to " << i << " is " << dist[i] << std::endl;}}
};

四、搜索网页算法（PageRank 算法）

PageRank 算法用于评估网页的重要性。

#include <iostream>
#include <vector>
#include <cmath>class WebGraphPageRank {
private:int numPages;std::vector<std::vector<bool>> adjMatrix;std::vector<double> pageRank;double dampingFactor = 0.85;double tolerance = 0.0001;bool isConverged(const std::vector<double>& oldPR, const std::vector<double>& newPR) {for (int i = 0; i < numPages; ++i) {if (std::abs(oldPR[i] - newPR[i]) > tolerance) {return false;}}return true;}void updatePageRank() {std::vector<double> newPR(numPages, 0);for (int i = 0; i < numPages; ++i) {for (int j = 0; j < numPages; ++j) {if (adjMatrix[j][i]) {int outDegree = 0;for (int k = 0; k < numPages; ++k) {if (adjMatrix[j][k]) outDegree++;}newPR[i] += pageRank[j] / outDegree;}}newPR[i] = (1 - dampingFactor) / numPages + dampingFactor * newPR[i];}pageRank = newPR;}public:WebGraphPageRank(int pages) : numPages(pages), adjMatrix(pages, std::vector<bool>(pages, false)), pageRank(pages, 1.0 / pages) {}// 添加网页之间的链接void addLink(int src, int dest) {if (src >= 0 && src < numPages && dest >= 0 && dest < numPages) {adjMatrix[src][dest] = true;}}// 计算 PageRankvoid computePageRank() {std::vector<double> prevPR = pageRank;do {updatePageRank();} while (!isConverged(prevPR, pageRank));}// 打印 PageRank 值void printPageRank() {for (int i = 0; i < numPages; ++i) {std::cout << "Page " << i << " : " << pageRank[i] << std::endl;}}
};

解释

• 图的结构表示：

  • 邻接矩阵：使用二维数组，易于理解和实现，对于稠密图空间效率较高，但对于稀疏图会浪费空间。
  • 邻接表：使用数组加链表（或向量），对于稀疏图空间效率更高，但查找边时可能需要遍历链表。

• 图的遍历：

  • DFS：使用递归方式，先访问当前顶点，然后递归访问其邻居，直到无法继续深入，再回溯。
  • BFS：使用队列，先访问当前顶点，将邻居入队，按入队顺序依次访问，实现层次遍历。

• 最短路径算法（Dijkstra）：

  • 利用优先队列（最小堆）存储距离源点的距离，不断选取距离最小的顶点，更新其邻居的距离。

• 搜索网页算法（PageRank）：

  • 基于网页之间的链接关系，迭代更新每个网页的重要性得分，直到收敛。根据链接的入度和出度，结合阻尼因子计算得分。

使用示例

int main() {// 邻接矩阵示例GraphAdjMatrix g1(5);g1.addEdge(0, 1, 10);g1.addEdge(0, 2, 20);g1.addEdge(1, 2, 30);g1.addEdge(2, 3, 40);g1.print();// 邻接表示例GraphAdjList g2(5);g2.addEdge(0, 1);g2.addEdge(0, 2);g2.addEdge(1, 2);g2.addEdge(2, 3);g2.print();// DFS 示例GraphDFS g3(5);g3.addEdge(0, 1);g3.addEdge(0, 2);g3.addEdge(1, 2);g3.addEdge(2, 3);std::cout << "DFS: ";g3.dfs(0);std::cout << std::endl;// BFS 示例GraphBFS g4(5);g4.addEdge(0, 1);g4.addEdge(0, 2);g4.addEdge(1, 2);g4.addEdge(2, 3);std::cout << "BFS: ";g4.bfs(0);std::cout << std::endl;// Dijkstra 算法示例GraphDijkstra g5(5);g5.addEdge(0, 1, 10);g5.addEdge(0, 2, 20);g5.addEdge(1, 2, 30);g5.addEdge(2, 3, 40);g5.printShortestPaths(0);// PageRank 算法示例WebGraphPageRank wg(5);wg.addLink(0, 1);wg.addLink(0, 2);wg.addLink(1, 2);wg.addLink(2, 0);wg.addLink(2, 3);wg.addLink(3, 4);wg.addLink(4, 0);wg.computePageRank();wg.printPageRank();return 0;
}

总结

• 图是一种强大的数据结构，可用于解决许多现实世界的问题，如网络路由、社交网络分析、网页搜索等。
• 选择合适的图表示方法（邻接矩阵或邻接表）取决于图的稀疏程度。
• 不同的遍历算法（DFS 和 BFS）适用于不同的场景，DFS 适合寻找路径和解决可达性问题，BFS 适合寻找最短路径和层次遍历。
• 最短路径算法（如 Dijkstra）可以找到图中源点到其他点的最短路径，适用于边权非负的情况。
• 搜索网页算法（如 PageRank）可评估网页的重要性，通过不断迭代更新得分，考虑网页之间的链接结构。