高级图论
高级图论算法包括二分图匹配、欧拉回路、强连通分量和双连通分量。这些算法是解决竞赛编程中复杂图论问题的关键。
二分图与匹配
二分图可以分为两个不相交的集合，边只连接来自不同集合的顶点。
二分图检测和最大匹配
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class BipartiteChecker {
private:
vector<vector<int>> graph;
vector<int> color;
int n;
public:
BipartiteChecker(int vertices) : n(vertices) {
graph.resize(n);
color.assign(n, -1);
}
void addEdge(int u, int v) {
graph[u].push_back(v);
graph[v].push_back(u);
}
bool isBipartite() {
for (int start = 0; start < n; start++) {
if (color[start] == -1) {
queue<int> q;
q.push(start);
color[start] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
if (color[v] == -1) {
color[v] = 1 - color[u];
q.push(v);
} else if (color[v] == color[u]) {
return false;
}
}
}
}
}
return true;
}
};
int main() {
BipartiteChecker checker(6);
checker.addEdge(0, 3);
checker.addEdge(0, 4);
checker.addEdge(1, 3);
checker.addEdge(1, 5);
checker.addEdge(2, 4);
checker.addEdge(2, 5);
if (checker.isBipartite()) {
cout << "图是二分图！" << endl;
} else {
cout << "图不是二分图！" << endl;
}
return 0;
}使用BFS染色法检查顶点是否可以分为两个集合，集合内部没有边。
强连通分量 (SCC)
强连通分量是一个最大顶点集合，使得分量中每个顶点都能到达分量中的其他所有顶点。
Tarjan算法求强连通分量
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class TarjanSCC {
private:
vector<vector<int>> graph;
vector<int> dfn, low, sccId;
vector<bool> inStack;
stack<int> st;
int timer, sccCount;
void tarjan(int u) {
dfn[u] = low[u] = ++timer;
st.push(u);
inStack[u] = true;
for (int v : graph[u]) {
if (dfn[v] == 0) {
// 未访问的顶点
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (inStack[v]) {
// 指向当前SCC中顶点的后向边
low[u] = min(low[u], dfn[v]);
}
}
// 如果u是SCC的根
if (dfn[u] == low[u]) {
int v;
do {
v = st.top();
st.pop();
inStack[v] = false;
sccId[v] = sccCount;
} while (v != u);
sccCount++;
}
}
public:
TarjanSCC(int n) : graph(n), dfn(n, 0), low(n, 0),
sccId(n, -1), inStack(n, false),
timer(0), sccCount(0) {}
void addEdge(int u, int v) {
graph[u].push_back(v);
}
void findSCC() {
for (int i = 0; i < graph.size(); i++) {
if (dfn[i] == 0) {
tarjan(i);
}
}
}
int getSCCCount() { return sccCount; }
vector<int> getSCCIds() { return sccId; }
// 构建缩点图
vector<vector<int>> buildCondensationGraph() {
vector<vector<int>> condensed(sccCount);
vector<set<int>> edges(sccCount);
for (int u = 0; u < graph.size(); u++) {
for (int v : graph[u]) {
if (sccId[u] != sccId[v]) {
edges[sccId[u]].insert(sccId[v]);
}
}
}
for (int i = 0; i < sccCount; i++) {
for (int v : edges[i]) {
condensed[i].push_back(v);
}
}
return condensed;
}
};
int main() {
cout << "Tarjan强连通分量算法测试:" << endl;
TarjanSCC tarjan(8);
// 构建包含强连通分量的有向图
tarjan.addEdge(0, 1);
tarjan.addEdge(1, 2);
tarjan.addEdge(2, 0); // SCC: {0, 1, 2}
tarjan.addEdge(2, 3);
tarjan.addEdge(3, 4);
tarjan.addEdge(4, 5);
tarjan.addEdge(5, 3); // SCC: {3, 4, 5}
tarjan.addEdge(5, 6);
tarjan.addEdge(6, 7); // SCC: {6}, {7}
tarjan.findSCC();
cout << "强连通分量数量: " << tarjan.getSCCCount() << endl;
vector<int> sccIds = tarjan.getSCCIds();
cout << "SCC分配:" << endl;
for (int i = 0; i < sccIds.size(); i++) {
cout << "顶点 " << i << " -> SCC " << sccIds[i] << endl;
}
auto condensed = tarjan.buildCondensationGraph();
cout << "\n缩点图边:" << endl;
for (int i = 0; i < condensed.size(); i++) {
cout << "SCC " << i << " -> ";
for (int v : condensed[i]) {
cout << "SCC " << v << " ";
}
cout << endl;
}
return 0;
}Tarjan算法使用带时间戳的DFS在O(V+E)时间内找到强连通分量。它维护一个顶点栈，使用low-link值来识别SCC的根。
欧拉图与欧拉回路
欧拉回路是恰好经过每条边一次的闭合路径。当且仅当每个顶点的度数都是偶数时，图才有欧拉回路。
Hierholzer算法求欧拉回路
#include <iostream>
#include <vector>
#include <stack>
#include <list>
using namespace std;
class EulerianCircuit {
private:
vector<list<int>> graph;
int n;
public:
EulerianCircuit(int vertices) : n(vertices), graph(vertices) {}
void addEdge(int u, int v) {
graph[u].push_back(v);
graph[v].push_back(u);
}
bool hasEulerianCircuit() {
// 检查所有顶点的度数是否为偶数
for (int i = 0; i < n; i++) {
if (graph[i].size() % 2 != 0) {
return false;
}
}
return true;
}
vector<int> findEulerianCircuit() {
if (!hasEulerianCircuit()) {
return {};
}
vector<int> circuit;
stack<int> currPath;
// 从顶点0开始
currPath.push(0);
while (!currPath.empty()) {
int curr = currPath.top();
if (!graph[curr].empty()) {
// 取下一条边
int next = graph[curr].front();
graph[curr].pop_front();
// 删除反向边
graph[next].remove(curr);
currPath.push(next);
} else {
// 没有更多边，添加到回路
circuit.push_back(curr);
currPath.pop();
}
}
return circuit;
}
void printCircuit(const vector<int>& circuit) {
if (circuit.empty()) {
cout << "不存在欧拉回路！" << endl;
return;
}
cout << "欧拉回路: ";
for (int i = circuit.size() - 1; i >= 0; i--) {
cout << circuit[i];
if (i > 0) cout << " -> ";
}
cout << endl;
}
};
int main() {
cout << "Hierholzer欧拉回路算法测试:" << endl;
// 创建有欧拉回路的图
EulerianCircuit ec(5);
// 构建环图: 0-1-2-3-4-0 并添加额外边
ec.addEdge(0, 1);
ec.addEdge(1, 2);
ec.addEdge(2, 3);
ec.addEdge(3, 4);
ec.addEdge(4, 0);
ec.addEdge(0, 2); // 额外边使度数为偶数
if (ec.hasEulerianCircuit()) {
cout << "图有欧拉回路！" << endl;
vector<int> circuit = ec.findEulerianCircuit();
ec.printCircuit(circuit);
} else {
cout << "图没有欧拉回路！" << endl;
}
return 0;
}Hierholzer算法通过构建路径和合并环来找到欧拉回路。它沿着边前进直到没有更多边可用，然后回溯寻找额外的环。