C++图论全解

C++图论基础概念

图论是数学和计算机科学中研究图结构的学科。图由顶点（节点）和边组成，用于表示对象之间的关系。在C++中，图可以通过多种方式实现，包括邻接矩阵、邻接表等。

图的分类包括有向图和无向图，加权图和非加权图。有向图的边有方向，无向图的边没有方向。加权图的边带有权值，非加权图的边没有权值。

图的表示方法

邻接矩阵

邻接矩阵是使用二维数组表示图的方法。对于有n个顶点的图，使用n×n的矩阵。矩阵中的值表示顶点之间是否存在边，或边的权值。

const int MAX = 100;
int adjMatrix[MAX][MAX];

// 初始化邻接矩阵
void initializeMatrix(int n) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
adjMatrix[i][j] = 0;
}
}
}

// 添加边
void addEdge(int u, int v, int weight = 1) {
adjMatrix[u][v] = weight;
adjMatrix[v][u] = weight; // 无向图需要双向设置
}

邻接表

邻接表使用链表或动态数组表示图的连接关系。每个顶点维护一个列表，存储与之相连的顶点。

#include <vector>
using namespace std;

const int MAX = 100;
vector<int> adjList[MAX];

// 添加边
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u); // 无向图需要双向添加
}

图的遍历算法

深度优先搜索（DFS）

DFS通过递归或栈实现，沿着图的深度遍历节点。

#include <stack>
#include <vector>
using namespace std;

vector<bool> visited(MAX, false);

void DFS(int start) {
stack<int> s;
s.push(start);
visited[start] = true;

while (!s.empty()) {
int u = s.top();
s.pop();
for (int v : adjList[u]) {
if (!visited[v]) {
visited[v] = true;
s.push(v);
}
}
}
}

广度优先搜索（BFS）

BFS通过队列实现，按层次遍历节点。

#include <queue>
#include <vector>
using namespace std;

vector<bool> visited(MAX, false);

void BFS(int start) {
queue<int> q;
q.push(start);
visited[start] = true;

while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adjList[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}

最短路径算法

Dijkstra算法

Dijkstra算法用于求解单源最短路径，适用于非负权图。

#include <queue>
#include <vector>
#include <climits>
using namespace std;

const int INF = INT_MAX;

void Dijkstra(int start, int n) {
vector<int> dist(n, INF);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

dist[start] = 0;
pq.push({0, start});

while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
for (auto &edge : adjList[u]) {
int v = edge.first;
int weight = edge.second;
if (dist[v] > dist[u] + weight) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
}

Floyd-Warshall算法

Floyd-Warshall算法用于求解所有顶点对之间的最短路径。

const int INF = INT_MAX;

void FloydWarshall(int n) {
vector<vector<int>> dist(n, vector<int>(n, INF));

for (int i = 0; i < n; ++i) {
dist[i][i] = 0;
}

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] != INF && dist[k][j] != INF) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
}

最小生成树算法

Prim算法

Prim算法用于求解加权无向图的最小生成树。

#include <queue>
#include <vector>
#include <climits>
using namespace std;

const int INF = INT_MAX;

void Prim(int start, int n) {
vector<int> key(n, INF);
vector<bool> inMST(n, false);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

key[start] = 0;
pq.push({0, start});

while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
inMST[u] = true;
for (auto &edge : adjList[u]) {
int v = edge.first;
int weight = edge.second;
if (!inMST[v] && key[v] > weight) {
key[v] = weight;
pq.push({key[v], v});
}
}
}
}

Kruskal算法

Kruskal算法通过并查集实现最小生成树。

#include <algorithm>
#include <vector>
using namespace std;

struct Edge {
int u, v, weight;
bool operator<(Edge const &other) {
return weight < other.weight;
}
};

vector<Edge> edges;
vector<int> parent;

int find_set(int v) {
if (v == parent[v]) return v;
return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) parent[b] = a;
}

void Kruskal(int n) {
parent.resize(n);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}

sort(edges.begin(), edges.end());
vector<Edge> result;
for (Edge e : edges) {
if (find_set(e.u) != find_set(e.v)) {
result.push_back(e);
union_sets(e.u, e.v);
}
}
}

拓扑排序

拓扑排序用于有向无环图（DAG），输出顶点的线性序列。

#include <stack>
#include <vector>
using namespace std;

vector<bool> visited(MAX, false);
stack<int> s;

void topologicalSortUtil(int u) {
visited[u] = true;
for (int v : adjList[u]) {
if (!visited[v]) {
topologicalSortUtil(v);
}
}
s.push(u);
}

void topologicalSort(int n) {
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
topologicalSortUtil(i);
}
}
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
}

强连通分量（SCC）

Kosaraju算法用于求解有向图的强连通分量。

#include <stack>
#include <vector>
using namespace std;

vector<bool> visited(MAX, false);
stack<int> s;

void fillOrder(int u) {
visited[u] = true;
for (int v : adjList[u]) {
if (!visited[v]) {
fillOrder(v);
}
}
s.push(u);
}

void DFSUtil(int u, vector<bool> &visited) {
visited[u] = true;
cout << u << " ";
for (int v : adjList[u]) {
if (!visited[v]) {
DFSUtil(v, visited);
}
}
}

void Kosaraju(int n) {
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
fillOrder(i);
}
}

vector<vector<int>> reversedAdj(n);
for (int u = 0; u < n; ++u) {
for (int v : adjList[u]) {
reversedAdj[v].push_back(u);
}
}

fill(visited.begin(), visited.end(), false);
while (!s.empty()) {
int u = s.top();
s.pop();
if (!visited[u]) {
DFSUtil(u, visited);
cout << endl;
}
}
}

网络流算法

Ford-Fulkerson算法

Ford-Fulkerson算法用于求解网络流中的最大流问题。

#include <queue>
#include <vector>
#include <climits>
using namespace std;

const int INF = INT_MAX;

bool BFS(vector<vector<int>> &rGraph, int s, int t, vector<int> &parent) {
vector<bool> visited(rGraph.size(), false);
queue<int> q;
q.push(s);
visited[s] = true;
parent[s] = -1;

while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 0; v < rGraph.size(); ++v) {
if (!visited[v] && rGraph[u][v] > 0) {
q.push(v);
parent[v] = u;
visited[v] = true;
}
}
}
return visited[t];
}

int FordFulkerson(vector<vector<int>> &graph, int s, int t) {
vector<vector<int>> rGraph = graph;
vector<int> parent(graph.size());
int max_flow = 0;

while (BFS(rGraph, s, t, parent)) {
int path_flow = INF;
for (int v = t; v != s; v = parent[v]) {
int u = parent[v];
path_flow = min(path_flow, rGraph[u][v]);
}
for (int v = t; v != s; v = parent[v]) {
int u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow;
}
max_flow += path_flow;
}
return max_flow;
}

欧拉回路与哈密顿回路

欧拉回路

欧拉回路是经过图中每一条边且每一条边仅经过一次的回路。

#include <stack>
#include <vector>
using namespace std;

void EulerianUtil(int u, vector<vector<int>> &adj, stack<int> &stk) {
while (!adj[u].empty()) {
int v = adj[u].back();
adj[u].pop_back();
EulerianUtil(v, adj, stk);
}
stk.push(u);
}

void EulerianCircuit(int n) {
vector<vector<int>> adj(n);
stack<int> stk;
EulerianUtil(0, adj, stk);
while (!stk.empty()) {
cout << stk.top() << " ";
stk.pop();
}
}

哈密顿回路

哈密顿回路是经过图中每一个顶点且每一个顶点仅经过一次的回路。

#include <vector>
using namespace std;

bool isSafe(int v, vector<vector<int>> &graph, vector<int> &path, int pos) {
if (graph[path[pos – 1]][v] == 0) return false;
for (int i = 0; i < pos; ++i) {
if (path[i] == v) return false;
}
return true;
}

bool hamCycleUtil(vector<vector<int>> &graph, vector<int> &path, int pos) {
if (pos == graph.size()) {
return graph[path[pos – 1]][path[0]] == 1;
}
for (int v = 1; v < graph.size(); ++v) {
if (isSafe(v, graph, path, pos)) {
path[pos] = v;
if (hamCycleUtil(graph, path, pos + 1)) {
return true;
}
path[pos] = -1;
}
}
return false;
}

void hamCycle(vector<vector<int>> &graph) {
vector<int> path(graph.size(), -1);
path[0] = 0;
if (!hamCycleUtil(graph, path, 1)) {
cout << "No Hamiltonian Cycle exists" << endl;
return;
}
for (int i : path) {
cout << i << " ";
}
cout << path[0] << endl;
}

图的着色问题

图的着色问题是为图的顶点着色，使得相邻顶点颜色不同。

#include <vector>
using namespace std;

bool isSafe(int v, vector<vector<int>> &graph, vector<int> &color, int c) {
for (int i = 0; i < graph.size(); ++i) {
if (graph[v][i] && c == color[i]) {
return false;
}
}
return true;
}

bool graphColoringUtil(vector<vector<int>> &graph, int m, vector<int> &color, int v) {
if (v == graph.size()) return true;
for (int c = 1; c <= m; ++c) {
if (isSafe(v, graph, color, c)) {
color[v] = c;
if (graphColoringUtil(graph, m, color, v + 1)) {
return true;
}
color[v] = 0;
}
}
return false;
}

void graphColoring(vector<vector<int>> &graph, int m) {
vector<int> color(graph.size(), 0);
if (!graphColoringUtil(graph, m, color, 0)) {
cout << "No solution exists" << endl;
return;
}
for (int c : color) {
cout << c << " ";
}
cout << endl;
}

二分图匹配

二分图匹配用于解决二分图中的最大匹配问题。

#include <vector>
using namespace std;

bool bpm(vector<vector<bool>> &bpGraph, int u, vector<bool> &seen, vector<int> &matchR) {
for (int v = 0; v < bpGraph[0].size(); ++v) {
if (bpGraph[u][v] && !seen[v]) {
seen[v] = true;
if (matchR[v] < 0 || bpm(bpGraph, matchR[v], seen, matchR)) {
matchR[v] = u;
return true;
}
}
}
return false;
}

int maxBPM(vector<vector<bool>> &bpGraph) {
vector<int> matchR(bpGraph[0].size(), -1);
int result = 0;
for (int u = 0; u < bpGraph.size(); ++u) {
vector<bool> seen(bpGraph[0].size(), false);
if (bpm(bpGraph, u, seen, matchR)) {
result++;
}
}
return result;
}

图的动态规划应用

旅行商问题（TSP）

旅行商问题是经典的动态规划问题，求解访问所有城市并返回起点的最短路径。

#include <vector>
#include <climits>
using namespace std;

const int INF = INT_MAX;

int TSP(vector<vector<int>> &graph, int s) {
int n = graph.size();
vector<vector<int>> dp(1 << n, vector<int>(n, INF));
dp[1 << s][s] = 0;

for (int mask = 0; mask < (1 << n); ++mask) {
for (int u = 0; u < n; ++u) {
if (!(mask & (1 << u))) continue;
for (int v = 0; v < n; ++v) {
if (mask & (1 << v)) continue;
int new_mask = mask | (1 << v);
dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + graph[u][v]);
}
}
}

int final_mask = (1 << n) – 1;
int res = INF;
for (int u = 0; u < n; ++u) {
if (u == s) continue;
res = min(res, dp[final_mask][u] + graph[u][s]);
}
return res;
}

图的割点与桥

Tarjan算法

Tarjan算法用于求解图的割点和桥。

#include <vector>
using namespace std;

vector<int> disc, low;
vector<bool> visited;
vector<vector<int>> adj;
int time = 0;

void findBridges(int u, int parent) {
visited[u] = true;
disc[u] = low[u] = ++time;
for (int v : adj[u]) {
if (!visited[v]) {
findBridges(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > disc[u]) {
cout << u << " " << v << endl;
}
} else if (v != parent) {
low[u] = min(low[u], disc[v]);
}
}
}

void findArticulationPoints(int u, int parent) {
visited[u] = true;
disc[u] = low[u] = ++time;
int children = 0;
for (int v : adj[u]) {
if (!visited[v]) {
children++;
findArticulationPoints(v, u);
low[u] = min(low[u], low[v]);
if (parent != -1 && low[v] >= disc[u]) {
cout << u << endl;
}
} else if (v != parent) {
low[u] = min(low[u], disc[v]);
}
}
if (parent == -1 && children > 1) {
cout << u << endl;
}
}

图的平面性检测

平面图是可以画在平面上且边不相交的图。

#include <vector>
using namespace std;

bool isPlanar(vector<vector<int>> &graph) {
int n = graph.size();
if (n < 5) return true;
int e = 0;
for (int u = 0; u < n; ++u) {
e += graph[u].size();
}
e /= 2;
return e <= 3 * n – 6;
}

图的同构检测

图的同构是指两个图在顶点重标号后完全相同。

#include <vector>
#include <algorithm>
using namespace std;

bool areIsomorphic(vector<vector<int>> &graph1, vector<vector<int>> &graph2) {
if (graph1.size() != graph2.size()) return false;
int n = graph1.size();
vector<int> perm(n);
for (int i = 0; i < n; ++i) {
perm[i] = i;
}
do {
bool ok = true;
for (int u = 0; u < n && ok; ++u) {
for (int v = 0; v < n && ok; ++v) {
if (graph1[u][v] != graph2[perm[u]][perm[v]]) {
ok = false;
}
}
}
if (ok) return true;
} while (next_permutation(perm.begin(), perm.end()));
return false;
}

图的随机生成

生成随机图用于测试图算法。

#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

vector<vector<int>> generateRandomGraph(int n, double p) {
vector<vector<int>> graph(n, vector<int>(n, 0));
srand(time(0));
for (int u = 0; u < n; ++u) {
for (int v = u + 1; v < n; ++v) {
if ((rand() % 100) < p * 100) {
graph[u][v] = graph[v][u] = 1;
}
}
}
return graph;
}

图的序列化与反序列化

将图结构序列化为字符串或文件，便于存储和传输。

#include <fstream>
#include <sstream>
#include <vector>
using namespace std;

void serializeGraph(vector<vector<int>> &graph, const string &filename) {
ofstream out(filename);
int n = graph.size();
out << n << endl;
for (int u = 0; u < n; ++u) {
for (int v = 0; v < n; ++v) {
out << graph[u][v] << " ";
}
out << endl;
}
out.close();
}

vector<vector<int>> deserializeGraph(const string &filename) {
ifstream in(filename);
int n;
in >> n;
vector<vector<int>> graph(n, vector<int>(n));
for (int u = 0; u < n; ++u) {
for (int v = 0; v < n; ++v) {
in >> graph[u][v];
}
}
in.close();
return graph;
}

图的并行算法

利用多线程加速图算法。

#include <thread>
#include <vector>
using namespace std;

void parallelBFS(int start, vector<bool> &visited, vector<vector<int>> &adj) {
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}

void runParallelBFS(vector<vector<int>> &adj, int num_threads) {
int n = adj.size();
vector<bool> visited(n, false);
vector<thread> threads;
for (int i = 0; i < num_threads; ++i) {
threads.emplace_back(parallelBFS, i, ref(visited), ref(adj));
}
for (auto &t : threads) {
t.join();
}
}

图的机器学习应用

图神经网络（GNN）用于图数据的机器学习。

#include <vector>
using namespace std;

class GNN {
public:
vector<vector<float>> forward(vector<vector<int>> &graph, vector<vector<float>> &features) {
int n = graph.size();
vector<vector<float>> output(n, vector<float>(features[0].size(), 0.0f));
for (int u = 0; u < n; ++u) {
for (int v = 0; v < n; ++v) {
if (graph[u][v]) {
for (int k = 0; k < features[0].size(); ++k) {
output[u][k] += features[v][k];
}
}
}
}
return output;
}
};

图的可视化

使用图形库可视化图结构。

#include <graphviz/gvc.h>
#include <vector>
using namespace std;

void visualizeGraph(vector<vector<int>> &graph) {
GVC_t *gvc = gvContext();
Agraph_t *g = agopen("g", Agundirected, 0);
for (int u = 0; u < graph.size(); ++u) {
agnode(g, const_cast<char *>(to_string(u).c_str()), 1);
}
for (int u = 0; u < graph.size(); ++u) {
for (int v = u + 1; v < graph.size(); ++v) {
if (graph[u][v]) {
Agedge_t *e = agedge(g, agnode(g, const_cast<char *>(to_string(u).c_str()), 0),
agnode(g, const_cast<char *>(to_string(v).c_str()), 0), 0, 1);
}
}
}
gvLayout(gvc, g, "dot");
gvRender(gvc, g, "png", fopen("graph.png", "w"));
gvFreeLayout(gvc, g);
agclose(g);
gvFreeContext(gvc);
}

图的优化技巧

优化图算法的性能和内存使用。

• 使用位压缩存储邻接矩阵
• 使用稀疏矩阵存储稀疏图
• 预分配内存避免频繁动态分配
• 使用并行算法加速计算
• 使用缓存友好的数据结构

#include <vector>
using namespace std;

vector<vector<bool>> compressAdjMatrix(vector<vector<int>> &graph) {
int n = graph.size();
vector<vector<bool>> compressed(n, vector<bool>(n, false));
for (int u = 0; u < n; ++u) {
for (int v = 0; v < n; ++v) {
compressed[u][v] = graph[u][v] != 0;
}
}
return compressed;
}

图的常见问题与解决方案

内存不足

对于大型图，使用邻接表而非邻接矩阵。考虑使用稀疏矩阵或分布式存储。

性能瓶颈

对于密集计算，使用并行算法或GPU加速。优化数据结构和算法复杂度。

动态图处理

对于频繁变化的图，使用增量算法或专门的数据结构如邻接表。

图的扩展应用

• 社交网络分析
• 路由算法
• 推荐系统
• 生物信息学
• 计算机视觉
• 自然语言处理

图论竞赛题目

常见图论竞赛题目类型：

图论学习资源

推荐学习资源：

• 《算法导论》图论章节
• 《图论及其应用》
• 《Network Flows》
• 《Algorithm Design》
• 在线OJ平台图论题目
• 图论专题课程

总结

C++图论涵盖广泛，从基础表示到高级算法，应用于多个领域。掌握图论算法需要理解数据结构、算法设计和优化技巧。通过实践和理论学习，可以深入理解图论并解决实际问题。

点个赞吧