图海寻径——图相关算法的奇幻探索之旅
一、图的表示
1. 邻接矩阵 (Adjacency Matrix)
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
class GraphMatrix {
private:
int numVertices;
vector<vector<int>> adjMatrix;
const static int INFINITY = numeric_limits<int>::max();
public:
GraphMatrix(int vertices) : numVertices(vertices), adjMatrix(vertices, vector<int>(vertices, INFINITY)) {}
void addEdge(int u, int v, int weight) {
if (u >= 0 && u < numVertices && v >= 0 && v < numVertices) {
adjMatrix[u][v] = weight;
adjMatrix[v][u] = weight; // 如果是无向图，则需要双向设置
}
}
void BFS(int startVertex);
void DFSUtil(int vertex, vector<bool>& visited);
void DFS();
};
void GraphMatrix::BFS(int startVertex) {
vector<bool> visited(numVertices, false);
queue<int> q;
visited[startVertex] = true;
q.push(startVertex);
while (!q.empty()) {
int current = q.front();
cout << "Visited " << current << endl;
q.pop();
for (int i = 0; i < numVertices; ++i) {
if (adjMatrix[current][i] != INFINITY && !visited[i]) {
visited[i] = true;
q.push(i);
}
}
}
}
void GraphMatrix::DFSUtil(int vertex, vector<bool>& visited) {
visited[vertex] = true;
cout << "Visited " << vertex << endl;
for (int i = 0; i < numVertices; ++i) {
if (adjMatrix[vertex][i] != INFINITY && !visited[i])
DFSUtil(i, visited);
}
}
void GraphMatrix::DFS() {
vector<bool> visited(numVertices, false);
for (int i = 0; i < numVertices; ++i)
if (!visited[i])
DFSUtil(i, visited);
}
2. 邻接表 (Adjacency List)
#include <iostream>
#include <vector>
#include <list>
#include <queue>
using namespace std;
class GraphList {
private:
int numVertices;
vector<list<pair<int, int>>> adjLists;
public:
GraphList(int vertices) : numVertices(vertices), adjLists(vertices) {}
void addEdge(int u, int v, int weight) {
adjLists[u].push_back(make_pair(v, weight));
adjLists[v].push_back(make_pair(u, weight)); // 如果是无向图，则需要双向添加
}
void BFS(int startVertex);
void DFSUtil(int vertex, vector<bool>& visited);
void DFS();
};
void GraphList::BFS(int startVertex) {
vector<bool> visited(numVertices, false);
queue<int> q;
visited[startVertex] = true;
q.push(startVertex);
while (!q.empty()) {
int current = q.front();
cout << "Visited " << current << endl;
q.pop();
for (auto& edge : adjLists[current]) {
int neighbor = edge.first;
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
void GraphList::DFSUtil(int vertex, vector<bool>& visited) {
visited[vertex] = true;
cout << "Visited " << vertex << endl;
for (auto& edge : adjLists[vertex]) {
int neighbor = edge.first;
if (!visited[neighbor])
DFSUtil(neighbor, visited);
}
}
void GraphList::DFS() {
vector<bool> visited(numVertices, false);
for (int i = 0; i < numVertices; ++i)
if (!visited[i])
DFSUtil(i, visited);
}
二、图的遍历算法
（一）深度优先搜索（DFS）
- 核心原理
- 以深度优先为策略，从起始顶点出发，沿着一条路径持续深入探索，直至无法继续或达成特定条件（如找到目标顶点）。随后回溯到前一步，继续探寻其他未访问路径，直至遍历完起始顶点所在连通分量的所有顶点。若图中存在未访问顶点，则选取其一作为新起始点，重复上述流程，直至整个图的所有顶点均被访问。
- 实现方式
- 递归实现：在递归函数中，首先标记当前顶点已访问，接着遍历其邻接顶点，对未访问的邻接顶点递归调用 DFS 函数。以下是使用邻接表存储图的递归 DFS 代码：
class GraphDFS {
private:
vector<bool> visited;
void DFSUtil(Graph& graph, int v) {
visited[v] = true;
cout << v << " ";
for (const Edge& edge : graph.adjList[v]) {
int neighbor = edge.to;
if (!visited[neighbor]) {
DFSUtil(graph, neighbor);
}
}
}
public:
void DFS(Graph& graph) {
visited.resize(graph.numVertices, false);
for (int i = 0; i < graph.numVertices; ++i) {
if (!visited[i]) {
DFSUtil(graph, i);
}
}
}
};
- 应用场景
- 图的连通性检测：执行一次 DFS 遍历，若所有顶点均能被访问到，则图是连通的；反之则不连通。
- 连通分量求解：多次调用 DFS，每次从一个未访问顶点启动，可获取图的各个连通分量。
- 迷宫探索：将迷宫建模为图，迷宫中的格子作为顶点，相邻格子间的通道作为边，DFS 可用于找寻从迷宫入口到出口的路径。
（二）广度优先搜索（BFS）
- 核心原理
- 从给定起始顶点开始，先访问该顶点，接着依次访问其所有未访问的邻接顶点，然后再访问这些邻接顶点的未访问邻接顶点，依此类推，按照层次顺序逐层向外拓展，直至遍历完图中的所有顶点。
- 实现方式
- 借助队列实现。首先将起始顶点入队并标记为已访问，然后循环取出队首顶点，访问其未访问邻接顶点并将这些邻接顶点入队，直至队列为空。以下是使用邻接表存储图的 BFS 示例代码：
class GraphBFS {
public:
void BFS(Graph& graph, int start) {
vector<bool> visited(graph.numVertices, false);
queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int current = q.front();
q.pop();
cout << current << " ";
for (const Edge& edge : graph.adjList[current]) {
int neighbor = edge.to;
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
};
- 应用场景
- 无权图最短路径计算：在 BFS 遍历过程中，从起始顶点到其他顶点的路径长度即为它们在队列中被访问的层数，可用于求解无权图中两点间的最短路径长度及路径。
- 网络爬虫页面遍历：网络爬虫从起始页面出发，按照广度优先顺序遍历链接页面，能够优先抓取与起始页面距离较近的页面，确保信息获取的全面性和层次性。
三、最小生成树算法
（一）普里姆算法（Prim）
- 核心原理
- 从图中任选一个顶点作为起始点，构建初始的最小生成树集合。随后不断从剩余顶点中挑选与当前最小生成树集合相连且权值最小的边所对应的顶点，将其纳入最小生成树集合，持续该过程直至所有顶点均被加入。
- 实现细节
- 维护两个顶点集合，已在最小生成树中的顶点集合
U和未在其中的顶点集合V - U。使用数组key记录每个顶点到当前最小生成树的最小权值边的权值，初始除起始顶点外均设为无穷大，同时用数组parent记录每个顶点在最小生成树中的父顶点。以下是使用邻接表存储图的 Prim 算法代码：
- 维护两个顶点集合，已在最小生成树中的顶点集合
class PrimMST {
public:
int prim(Graph& graph, int start) {
vector<bool> inMST(graph.numVertices, false);
vector<int> key(graph.numVertices, INT_MAX);
vector<int> parent(graph.numVertices, -1);
key[start] = 0;
for (int count = 0; count < graph.numVertices - 1; ++count) {
int minKey = INT_MAX, minIndex = -1;
for (int v = 0; v < graph.numVertices; ++v) {
if (!inMST[v] && key[v] < minKey) {
minKey = key[v];
minIndex = v;
}
}
inMST[minIndex] = true;
for (const Edge& edge : graph.adjList[minIndex]) {
int neighbor = edge.to;
int weight = 1; // 如果是带权图，这里改成对应边的权值
if (!inMST[neighbor] && weight < key[neighbor]) {
key[neighbor] = weight;
parent[neighbor] = minIndex;
}
}
}
int sumWeight = 0;
for (int i = 1; i < graph.numVertices; ++i) {
sumWeight += key[i]; // 累加最小生成树边的权值（这里简单示例，实际带权图边权计算更复杂）
}
return sumWeight;
}
};
- 时间复杂度分析
- 若采用邻接矩阵存储图，时间复杂度为(O(n^2))，其中(n)为顶点数。若运用堆优化，时间复杂度可降至(O((n + m)log n))，其中(m)为边数。
（二）克鲁斯卡尔算法（Kruskal）
- 核心原理
- 首先将图中所有边按照权值从小到大排序，然后依次考察每条边。若选取某条边不会与已选边构成回路，则将其纳入最小生成树，直至选取了(n - 1)条边（(n)为顶点数）。
- 实现细节
- 需要借助并查集数据结构判断边加入后是否形成回路。并查集用于维护顶点的连通性信息，初始每个顶点各自属于独立集合，加入边时判断边的两个顶点是否在同一集合，若不在则合并两个集合。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 边的数据结构
struct Edge {
int src, dest, weight;
};
// 比较函数，用于对边按照权重排序
bool compare(const Edge& a, const Edge& b) {
return a.weight < b.weight;
}
// 并查集 (Union-Find) 的类
class UnionFind {
private:
vector<int> parent, rank;
public:
UnionFind(int size) : parent(size), rank(size, 0) {
for (int i = 0; i < size; ++i)
parent[i] = i;
}
// 查找操作，带有路径压缩
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]); // 路径压缩
return parent[x];
}
// 合并操作，带有按秩合并
void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY])
parent[rootY] = rootX;
else if (rank[rootX] < rank[rootY])
parent[rootX] = rootY;
else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
};
// Kruskal 算法实现
void kruskalMST(vector<Edge>& edges, int V) {
sort(edges.begin(), edges.end(), compare); // 按权重升序排序边
UnionFind uf(V);
vector<Edge> mst;
for (auto& edge : edges) {
int rootSrc = uf.find(edge.src);
int rootDest = uf.find(edge.dest);
if (rootSrc != rootDest) { // 如果不形成环，则加入最小生成树
mst.push_back(edge);
uf.unionSets(rootSrc, rootDest);
}
}
cout << "Edges in the MST:" << endl;
for (auto& e : mst)
cout << e.src << " -- " << e.dest << " == " << e.weight << endl;
}
int main() {
int V = 4; // 顶点数
vector<Edge> edges = {
{0, 1, 10},
{0, 2, 6},
{0, 3, 5},
{1, 3, 15},
{2, 3, 4}
};
kruskalMST(edges, V);
return 0;
}
- 时间复杂度分析
- 时间复杂度主要取决于边的排序操作，通常为(O(mlog m))，其中(m)为边数。在稀疏图中，由于边数相对较少，克鲁斯卡尔算法往往比普里姆算法更具效率。
四、最短路径算法
（一）迪杰斯特拉算法（Dijkstra）
- 核心原理
- 适用于带权有向图（权值非负）。从源点出发，逐步确定到其他顶点的最短路径。维护一个已确定最短路径的顶点集合
S，对于不在S中的顶点v，记录从源点到v的当前最短路径长度d[v]。每次从不在S中的顶点里选取d[v]最小的顶点u加入S，并更新与u相邻顶点的d[v]值。
- 适用于带权有向图（权值非负）。从源点出发，逐步确定到其他顶点的最短路径。维护一个已确定最短路径的顶点集合
- 实现细节
- 初始化时，源点的
d值设为(0)，其余顶点设为无穷大。然后持续重复选取最小d值顶点并更新相邻顶点d值的操作，直至所有顶点均被加入S。以下是使用邻接表存储图的 Dijkstra 算法代码：
- 初始化时，源点的
class DijkstraSP {
public:
vector<int> dijkstra(Graph& graph, int source) {
vector<int> dist(graph.numVertices, INT_MAX);
vector<bool> visited(graph.numVertices, false);
dist[source] = 0;
for (int count = 0; count < graph.numVertices - 1; ++count) {
int minDist = INT_MAX, minIndex = -1;
for (int v = 0; v < graph.numVertices; ++v) {
if (!visited[v] && dist[v] < minDist) {
minDist = dist[v];
minIndex = v;
}
}
visited[minIndex] = true;
for (const Edge& edge : graph.adjList[minIndex]) {
int neighbor = edge.to;
int weight = 1; // 如果是带权图，这里改成对应边的权值
if (!visited[neighbor] && dist[minIndex] + weight < dist[neighbor]) {
dist[neighbor] = dist[minIndex] + weight;
}
}
}
return dist;
}
};
- 时间复杂度分析
- 若采用邻接矩阵存储图，时间复杂度为(O(n^2))，其中(n)为顶点数。若使用堆优化，时间复杂度可降为(O((n + m)log n))，其中
m为边数。
- 若采用邻接矩阵存储图，时间复杂度为(O(n^2))，其中(n)为顶点数。若使用堆优化，时间复杂度可降为(O((n + m)log n))，其中
（二）弗洛伊德算法（Floyd）
- 核心原理
- 可计算出图中任意两个顶点之间的最短路径。基于动态规划思想，对于任意两个顶点(i)和(j)，考虑是否经过中间顶点(k)来更新(i)到(j)的最短路径长度。
- 实现细节
- 使用二维数组
dist存储顶点之间的最短路径长度。初始时，dist[i][j]为图中(i)到(j）的直接边权值（若有边），否则为无穷大。然后通过三层循环，依次以每个顶点k作为中间顶点更新dist[i][j]的值。以下是使用邻接矩阵存储图的 Floyd 算法示例代码：
- 使用二维数组
class FloydSP {
public:
vector<vector<int>> floyd(GraphMatrix& graph) {
int n = graph.numVertices;
vector<vector<int>> dist = graph.adjMatrix;
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (dist[i][k]!= INT_MAX && dist[k][j]!= INT_MAX &&
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
return dist;
}
};
- 时间复杂度分析
- 时间复杂度为(O(n^3))，其中(n)为顶点数。由于时间复杂度较高，适用于顶点数较少的图或者对所有顶点对最短路径都有需求的场景。
五、拓扑排序算法
- 核心原理
- 针对有向无环图（DAG），拓扑排序旨在将图中所有顶点排成一个线性序列，使得对于图中的任意一条有向边((u, v))，在序列中(u)均排在(v)之前。
- 实现方式（基于入度表）
- 首先统计每个顶点的入度，将入度为(0)的顶点入队。然后循环取出队首顶点，将其输出到拓扑序列中，并将其所有邻接点的入度减(1)，若某个邻接点入度变为(0)，则将其入队，直至队列为空。若最终输出的顶点数小于图中顶点总数，则说明图中有环，不存在拓扑排序。以下是拓扑排序的代码：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 边结构体，用于邻接表存储边的信息
struct Edge {
int to; // 边指向的顶点
Edge(int t) : to(t) {}
};
// 图结构体，使用邻接表存储
class Graph {
public:
int numVertices; // 顶点数量
vector<vector<Edge>> adjList; // 邻接表
Graph(int n) : numVertices(n), adjList(n) {}
// 添加边（有向图示例）
void addEdge(int from, int to) {
adjList[from].push_back(Edge(to));
}
};
class TopologicalSort {
public:
vector<int> topologicalSort(Graph& graph) {
int n = graph.numVertices;
// 用于记录每个顶点的入度
vector<int> inDegree(n, 0);
// 计算每个顶点的入度
for (int i = 0; i < n; i++) {
for (const Edge& edge : graph.adjList[i]) {
inDegree[edge.to]++;
}
}
queue<int> zeroDegreeQueue;
// 将入度为0的顶点入队
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
zeroDegreeQueue.push(i);
}
}
vector<int> topologicalOrder;
// 进行拓扑排序
while (!zeroDegreeQueue.empty()) {
int current = zeroDegreeQueue.front();
zeroDegreeQueue.pop();
topologicalOrder.push_back(current);
// 更新相邻顶点的入度，并将入度变为0的顶点入队
for (const Edge& edge : graph.adjList[current]) {
inDegree[edge.to]--;
if (inDegree[edge.to] == 0) {
zeroDegreeQueue.push(edge.to);
}
}
}
// 若排序后的顶点数小于图中顶点总数，则说明图中有环，不存在拓扑排序
if (topologicalOrder.size() < n) {
cout << "图中存在环，无法进行拓扑排序" << endl;
return {};
}
return topologicalOrder;
}
};
int main() {
Graph graph(6);
graph.addEdge(5, 2);
graph.addEdge(5, 0);
graph.addEdge(4, 0);
graph.addEdge(4, 1);
graph.addEdge(2, 3);
graph.addEdge(3, 1);
TopologicalSort ts;
vector<int> result = ts.topologicalSort(graph);
if (!result.empty()) {
cout << "拓扑排序结果为: ";
for (int vertex : result) {
cout << vertex << " ";
}
cout << endl;
}
return 0;
}
原文地址：https://blog.csdn.net/2301_79965256/article/details/144327680
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！