图论是计算机科学和数学中非常重要的一个分支，涉及到图的性质、结构以及相关的算法。以下是对图论的基础知识、常用算法及其相关代码的整理，帮助你为CSP备考做好准备。
一、图的基本概念
1.1 图的定义
在数学中，图是一个由顶点（或节点）和边组成的集合。图可用以下形式表示：
- 无向图：边没有方向，表示为 G(V,E)，其中 V 是顶点集合， E 是边集合。
- 有向图：边有方向，表示为有序对。
1.2 图的表示方式
-
邻接矩阵：使用二维数组表示图，其中 matrix[i][j] 存储边 (i, j) 的权值（无边则为∞或0）。
const int MAXN = 100; // 最大顶点数量 int graph[MAXN][MAXN]; // 邻接矩阵 -
邻接表：使用链表或向量表示图列表，适用于稀疏图。
#include <vector> using namespace std; struct Edge { int to, weight; }; vector<Edge> graph[MAXN]; // 邻接表
1.3 图的基本术语
- 路径：顶点的有序序列，其中任何两顶点之间都有边连接。
- 无环图：没有环的图（例如树）。
- 连通图：对于任意两个顶点之间都有路径相连。
- 强连通图：在有向图中，对于任意两个顶点 u 和 v， u 到 v 和 v 到 u 都有路径。
二、图的遍历
2.1 深度优先搜索 (DFS)
DFS 是一种用于遍历或搜索树或图的算法。其核心思想是尽可能深地搜索图的分支。
void DFS(int v, vector<bool> &visited) {
visited[v] = true; // 标记为已访问
// 访问该节点，比如输出其值
for (auto &edge : graph[v]) {
if (!visited[edge.to]) { // 如果未被访问
DFS(edge.to, visited);
}
}
}2.2 广度优先搜索 (BFS)
BFS 是一种基于队列的数据结构进行图的遍历。
#include <queue>
void BFS(int start) {
queue<int> q;
vector<bool> visited(MAXN, false);
q.push(start);
visited[start] = true;
while (!q.empty()) {
int v = q.front();
q.pop();
// 访问该节点，比如输出其值
for (auto &edge : graph[v]) {
if (!visited[edge.to]) {
visited[edge.to] = true;
q.push(edge.to);
}
}
}
}三、最短路径算法
3.1 Dijkstra 算法
用于找出非负权图中单源到所有其他顶点的最短路径。
#include <set>
void Dijkstra(int start) {
vector<int> dist(MAXN, INT_MAX); // 初始化距离
dist[start] = 0;
set<pair<int, int>> s; // 维护一个集合用于寻找最小距离
s.insert({0, start});
while (!s.empty()) {
int u = s.begin()->second; // 获取当前点
s.erase(s.begin()); // 移除点
for (auto &edge : graph[u]) {
int v = edge.to;
int weight = edge.weight;
// 放松操作
if (dist[u] + weight < dist[v]) {
s.erase({dist[v], v});
dist[v] = dist[u] + weight;
s.insert({dist[v], v});
}
}
}
}3.2 Bellman-Ford 算法
用于找出含有负权边的图的单源最短路径。
void BellmanFord(int start) {
vector<int> dist(MAXN, INT_MAX);
dist[start] = 0;
for (int i = 0; i < MAXN - 1; ++i) {
for (auto &edge : all_edges) { // all_edges 是图中所有边的集合
int u = edge.from;
int v = edge.to;
int weight = edge.weight;
// 放松操作
if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
}
}
}
}四、最小生成树
4.1 Prim 算法
用于找出无向连通图的最小生成树。
#include <vector>
#include <set>
void Prim(int start) {
vector<int> key(MAXN, INT_MAX);
vector<bool> inMST(MAXN, false);
key[start] = 0;
set<pair<int, int>> pq; // (权重, 顶点)
pq.insert({0, start});
while (!pq.empty()) {
int u = pq.begin()->second;
pq.erase(pq.begin());
inMST[u] = true;
for (auto &edge : graph[u]) {
int v = edge.to;
int weight = edge.weight;
if (!inMST[v] && weight < key[v]) {
pq.erase({key[v], v});
key[v] = weight;
pq.insert({key[v], v});
}
}
}
}4.2 Kruskal 算法
也是用于找出无向图的最小生成树，基于边的选择。
struct Edge {
int u, v, weight;
};
bool cmp(Edge a, Edge b) {
return a.weight < b.weight;
}
int find(int v, vector<int> &parent) {
if (parent[v] != v) {
parent[v] = find(parent[v], parent);
}
return parent[v];
}
void Kruskal() {
vector<Edge> edges; // 存放所有边
sort(edges.begin(), edges.end(), cmp);
vector<int> parent(MAXN);
for (int i = 0; i < MAXN; ++i) {
parent[i] = i; // 初始化
}
for (auto &edge : edges) {
int u = edge.u, v = edge.v;
if (find(u, parent) != find(v, parent)) {
parent[find(u, parent)] = find(v, parent); // 连接两个部分
// 可以在这里记录选中的边
}
}
}五、图的最大流问题
5.1 Ford-Fulkerson 算法
用于计算从源点到汇点的最大流。
#include <vector>
#include <queue>
#include <climits>
bool bfs(int s, int t, vector<vector<int>> &rGraph, vector<int> &parent) {
vector<bool> visited(MAXN, false);
queue<int> q;
q.push(s);
visited[s] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 0; v < MAXN; ++v) {
if (!visited[v] && rGraph[u][v] > 0) { // 如果未访问且有残量
q.push(v);
visited[v] = true;
parent[v] = u;
}
}
}
return visited[t]; // 返回汇点是否可达
}
int FordFulkerson(int s, int t) {
vector<vector<int>> rGraph(MAXN, vector<int>(MAXN, 0));
// rGraph[i][j] = originalCapacity[i][j];
int max_flow = 0;
vector<int> parent(MAXN);
while (bfs(s, t, rGraph, parent)) {
int path_flow = INT_MAX;
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;
}六、图的拓扑排序
拓扑排序用于有向无环图（DAG）的节点排序，使得每个有向边 u→v，u 在前，v 在后。
#include <algorithm>
#include <vector>
void topologicalSortUtil(int v, vector<bool> &visited, stack<int> &Stack) {
visited[v] = true;
for (auto &edge : graph[v]) {
if (!visited[edge.to]) {
topologicalSortUtil(edge.to, visited, Stack);
}
}
Stack.push(v);
}
void topologicalSort() {
stack<int> Stack;
vector<bool> visited(MAXN, false);
for (int i = 0; i < MAXN; ++i) {
if (!visited[i]) {
topologicalSortUtil(i, visited, Stack);
}
}
while (!Stack.empty()) {
cout << Stack.top() << " ";
Stack.pop();
}
}七、常见的图论
问题
7.1 判断图的连通性
可以通过 DFS 或 BFS 来检查图是否连通。
7.2 图的最小路径问题
使用 Dijkstra 或 Bellman-Ford 算法来求解。
7.3 找出图中的桥
使用 DFS 进行 DFS 遍历，并记录时间戳，判断边是否为桥。
void findBridgesUtil(int u, vector<int> &disc, vector<int> &low, vector<bool> &visited, int parent) {
visited[u] = true;
disc[u] = low[u] = ++time;
for (auto &edge : graph[u]) {
int v = edge.to;
if (!visited[v]) {
findBridgesUtil(v, disc, low, visited, u);
low[u] = min(low[u], low[v]);
if (low[v] > disc[u]) {
cout << "Bridge found: " << u << " - " << v << endl;
}
} else if (v != parent) {
low[u] = min(low[u], disc[v]);
}
}
}八、总结
以上是图论的基本概念、算法及其实现方法，涵盖了常见的图论知识点。这些内容对于理解和解决图论相关问题非常重要，在 C++ 程序设计和竞赛中，图论是一个必不可少的部分。
标签：vector,parent,int,基础,C++,edge,MAXN,visited From： https://blog.csdn.net/weixin_73139914/article/details/143025925