搜索算法
深度优先搜索
一种用于遍历或搜索树或图的算法。它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。
DFS核心思想
深度优先：尽可能深地搜索树的分支
回溯思想：当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点
递归实现：通常用递归方式自然地实现DFS
void dfs(Node* node, vector<bool>& visited) { // 标记当前节点为已访问 visited[node->val] = true; cout << node->val << " "; // 访问所有相邻节点 for (Node* neighbor : node->neighbors) { if (!visited[neighbor->val]) { dfs(neighbor, visited); } } } 递归实现经典运用
//图的连通分量 int countComponents(int n, vector<vector<int>>& edges) { vector<vector<int>> graph(n); vector<bool> visited(n, false); int components = 0; // 构建邻接表 for (auto& edge : edges) { graph[edge[0]].push_back(edge[1]); graph[edge[1]].push_back(edge[0]); } for (int i = 0; i < n; ++i) { if (!visited[i]) { components++; dfs(i, graph, visited); } } return components; } void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) { visited[node] = true; for (int neighbor : graph[node]) { if (!visited[neighbor]) { dfs(neighbor, graph, visited); } } }DFS是解决许多算法问题的强大工具，掌握其核心思想和各种优化技巧对算法能力提升至关重要。
广度优先搜索
一种用于遍历或搜索树或图的算法。它从根节点开始，先访问所有相邻节点，然后再依次访问这些节点的相邻节点，以此类推。
BFS核心思想
层级遍历：按照距离起始节点的层级依次访问
队列结构：使用队列来存储待访问节点
最短路径：在无权图中能找到最短路径
#include <queue> #include <vector> using namespace std; //标准实现 使用队列 void bfs(Node* start) { if (!start) return; queue<Node*> q; vector<bool> visited(NODES_SIZE, false); q.push(start); visited[start->val] = true; while (!q.empty()) { Node* current = q.front(); q.pop(); cout << current->val << " "; // 处理当前节点 // 访问所有相邻节点 for (Node* neighbor : current->neighbors) { if (!visited[neighbor->val]) { visited[neighbor->val] = true; q.push(neighbor); } } } }最短路径（无权图）
int shortestPath(Node* start, Node* end) { if (!start || !end) return -1; if (start == end) return 0; queue<Node*> q; unordered_map<Node*, int> distance; q.push(start); distance[start] = 0; while (!q.empty()) { Node* current = q.front(); q.pop(); for (Node* neighbor : current->neighbors) { if (!distance.count(neighbor)) { distance[neighbor] = distance[current] + 1; if (neighbor == end) { return distance[neighbor]; } q.push(neighbor); } } } return -1; // 不可达 }
注意事项
访问标记：必须在入队时标记，而非出队时
队列大小：处理层级时需要先保存当前队列大小
边界检查：网格类问题注意边界条件
状态表示：复杂状态需要设计良好的哈希函数
BFS是解决最短路径问题和层级遍历问题的利器，掌握其核心思想和各种变种对算法能力提升至关重要。
图的概念
有向图 (强连通分量)
强连通分量是有向图中的一个重要概念，指有向图中任意两个顶点都互相可达的最大子图。理解强连通分量对于分析有向图的结构至关重要。
基本概念
1. 强连通分量定义
强连通：在有向图中，如果从顶点u到v有一条路径，且从v到u也有一条路径，则称u和v强连通
强连通分量：有向图的极大强连通子图
2. 相关性质
每个顶点属于且仅属于一个强连通分量
将每个强连通分量缩为一个顶点，得到的有向图是一个有向无环图(DAG)
应用场景：编译器优化、社交网络分析、电路设计等
// Kosaraju算法（两次DFS） 实现 #include <iostream> #include <vector> #include <stack> #include <algorithm> using namespace std; class Graph { int V; vector<vector<int>> adj; vector<vector<int>> revAdj; void fillOrder(int v, vector<bool>& visited, stack<int>& st) { visited[v] = true; for (int u : adj[v]) { if (!visited[u]) { fillOrder(u, visited, st); } } st.push(v); } void DFSUtil(int v, vector<bool>& visited, vector<int>& component) { visited[v] = true; component.push_back(v); for (int u : revAdj[v]) { if (!visited[u]) { DFSUtil(u, visited, component); } } } public: Graph(int V) : V(V), adj(V), revAdj(V) {} void addEdge(int v, int w) { adj[v].push_back(w); revAdj[w].push_back(v); } vector<vector<int>> findSCCs() { stack<int> st; vector<bool> visited(V, false); // 第一次DFS，填充栈 for (int i = 0; i < V; i++) { if (!visited[i]) { fillOrder(i, visited, st); } } // 重置visited数组 fill(visited.begin(), visited.end(), false); vector<vector<int>> sccs; // 第二次DFS，按照栈的顺序处理逆图 while (!st.empty()) { int v = st.top(); st.pop(); if (!visited[v]) { vector<int> component; DFSUtil(v, visited, component); sccs.push_back(component); } } return sccs; } };// Tarjan算法（一次DFS） #include <iostream> #include <vector> #include <stack> #include <algorithm> using namespace std; class Graph { int V; vector<vector<int>> adj; void tarjanSCCUtil(int u, vector<int>& disc, vector<int>& low, stack<int>& st, vector<bool>& inStack, vector<vector<int>>& sccs, int& time) { disc[u] = low[u] = ++time; st.push(u); inStack[u] = true; for (int v : adj[u]) { if (disc[v] == -1) { // v未被访问 tarjanSCCUtil(v, disc, low, st, inStack, sccs, time); low[u] = min(low[u], low[v]); } else if (inStack[v]) { // v在栈中 low[u] = min(low[u], disc[v]); } } // 发现强连通分量 if (low[u] == disc[u]) { vector<int> component; while (st.top() != u) { int v = st.top(); component.push_back(v); inStack[v] = false; st.pop(); } component.push_back(u); inStack[u] = false; st.pop(); sccs.push_back(component); } } public: Graph(int V) : V(V), adj(V) {} void addEdge(int v, int w) { adj[v].push_back(w); } vector<vector<int>> tarjanSCC() { vector<int> disc(V, -1), low(V, -1); vector<bool> inStack(V, false); stack<int> st; vector<vector<int>> sccs; int time = 0; for (int i = 0; i < V; i++) { if (disc[i] == -1) { tarjanSCCUtil(i, disc, low, st, inStack, sccs, time); } } return sccs; } };实际应用: 有向图的缩点（将SCC缩为单个顶点）
Graph buildCondensedGraph(Graph& g, vector<vector<int>>& sccs) { // 创建顶点映射：原始顶点 -> 缩点后的顶点编号 vector<int> vertexToComponent(g.V); for (int i = 0; i < sccs.size(); i++) { for (int v : sccs[i]) { vertexToComponent[v] = i; } } // 构建缩点后的图 Graph condensed(sccs.size()); unordered_set<string> edges; // 避免重复边 for (int u = 0; u < g.V; u++) { for (int v : g.adj[u]) { int compU = vertexToComponent[u]; int compV = vertexToComponent[v]; if (compU != compV) { string edge = to_string(compU) + "-" + to_string(compV); if (!edges.count(edge)) { condensed.addEdge(compU, compV); edges.insert(edge); } } } } return condensed; }强连通分量分析是图算法中的重要工具，掌握Kosaraju和Tarjan这两种经典算法，能够有效解决许多有向图相关问题。
无向图 (双连通分量)
双连通分量是无向图中的一个重要概念，指没有"关节点"（割点）的最大连通子图。理解双连通分量对于分析网络可靠性、电路设计等问题至关重要。
基本概念
1. 双连通分量定义
关节点（割点）：删除该顶点会增加图的连通分量数量
桥（割边）：删除该边会增加图的连通分量数量
双连通分量：不含关节点的极大连通子图
2. 相关性质
任意两个顶点之间至少存在两条不相交的路径
双连通分量之间通过关节点连接
应用场景：网络容错分析、交通网络规划、电路板设计
// Tarjan算法求双连通分量
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Graph {
int V;
vector<vector<int>> adj;
void BCCUtil(int u, vector<int>& disc, vector<int>& low,
stack<pair<int, int>>& st, vector<bool>& isAP,
vector<vector<pair<int, int>>>& bccs, int& time, int parent = -1) {
int children = 0;
disc[u] = low[u] = ++time;
for (int v : adj[u]) {
if (disc[v] == -1) { // v未被访问
children++;
st.push({u, v});
BCCUtil(v, disc, low, st, isAP, bccs, time, u);
low[u] = min(low[u], low[v]);
// u是关节点（两种情况）
if ((parent == -1 && children > 1) || (parent != -1 && low[v] >= disc[u])) {
isAP[u] = true;
// 输出双连通分量
vector<pair<int, int>> component;
while (st.top() != make_pair(u, v)) {
component.push_back(st.top());
st.pop();
}
component.push_back(st.top());
st.pop();
bccs.push_back(component);
}
}
else if (v != parent && disc[v] < disc[u]) { // 处理回边
low[u] = min(low[u], disc[v]);
st.push({u, v});
}
}
}
public:
Graph(int V) : V(V), adj(V) {}
void addEdge(int v, int w) {
adj[v].push_back(w);
adj[w].push_back(v);
}
pair<vector<bool>, vector<vector<pair<int, int>>>> findBCCs() {
vector<int> disc(V, -1), low(V, -1);
vector<bool> isAP(V, false);
stack<pair<int, int>> st;
vector<vector<pair<int, int>>> bccs;
int time = 0;
for (int i = 0; i < V; i++) {
if (disc[i] == -1) {
BCCUtil(i, disc, low, st, isAP, bccs, time);
// 处理剩余边
vector<pair<int, int>> component;
bool hasEdge = false;
while (!st.empty()) {
hasEdge = true;
component.push_back(st.top());
st.pop();
}
if (hasEdge) {
bccs.push_back(component);
}
}
}
return {isAP, bccs};
}
};
//查找桥（割边）算法
vector<pair<int, int>> findBridges(Graph& g) {
vector<int> disc(g.V, -1), low(g.V, -1);
vector<pair<int, int>> bridges;
int time = 0;
for (int i = 0; i < g.V; i++) {
if (disc[i] == -1) {
bridgeUtil(i, -1, disc, low, bridges, time, g);
}
}
return bridges;
}
void bridgeUtil(int u, int parent, vector<int>& disc, vector<int>& low,
vector<pair<int, int>>& bridges, int& time, Graph& g) {
disc[u] = low[u] = ++time;
for (int v : g.adj[u]) {
if (disc[v] == -1) { // v未被访问
bridgeUtil(v, u, disc, low, bridges, time, g);
low[u] = min(low[u], low[v]);
// 发现桥
if (low[v] > disc[u]) {
bridges.push_back({u, v});
}
}
else if (v != parent) { // 处理回边
low[u] = min(low[u], disc[v]);
}
}
}无向图的双连通分量分析是图论中的重要工具，掌握Tarjan算法及其变种能够有效解决网络可靠性、关键节点识别等问题。理解算法的核心思想和实现细节对解决实际问题至关重要
回路
欧拉回路
欧拉回路和欧拉路径是图论中的重要概念，分别指图中经过每条边恰好一次并回到起点的回路，和经过每条边恰好一次的路径。
基本概念
1. 定义
欧拉回路：图中经过每条边恰好一次并回到起点的闭合路径
欧拉路径：图中经过每条边恰好一次的路径（不一定闭合）
欧拉图：存在欧拉回路的图
半欧拉图：存在欧拉路径但不存在欧拉回路的图
2. 判定条件
对于无向图：
| 类型 | 连通性 | 顶点度数条件 |
|---|---|---|
| 欧拉回路 | 连通 | 所有顶点度数为偶数 |
| 欧拉路径 | 连通 | 恰好两个顶点度数为奇数（起点和终点） |
对于有向图：
| 类型 | 连通性 | 顶点度数条件 |
|---|---|---|
| 欧拉回路 | 强连通 | 每个顶点入度等于出度 |
| 欧拉路径 | 单向连通 | 一个顶点出度=入度+1（起点），一个顶点入度=出度+1（终点），其余入度=出度 |
算法实现
//Hierholzer算法（寻找欧拉回路/路径）
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Graph {
int V;
vector<vector<int>> adj;
public:
Graph(int V) : V(V), adj(V) {}
void addEdge(int u, int v) {
adj[u].push_back(v);
}
void removeEdge(int u, int v) {
auto it = find(adj[u].begin(), adj[u].end(), v);
if (it != adj[u].end()) {
adj[u].erase(it);
}
}
vector<int> findEulerianCircuit() {
vector<int> circuit;
stack<int> currPath;
int currVertex = 0; // 可以选择任意顶点作为起点
currPath.push(currVertex);
while (!currPath.empty()) {
if (!adj[currVertex].empty()) {
currPath.push(currVertex);
int nextVertex = adj[currVertex].back();
adj[currVertex].pop_back();
currVertex = nextVertex;
} else {
circuit.push_back(currVertex);
currVertex = currPath.top();
currPath.pop();
}
}
reverse(circuit.begin(), circuit.end());
return circuit;
}
};欧拉回路和路径在DNA测序、网络路由、物流配送等领域有广泛应用。掌握Hierholzer算法及其实现细节，能够有效解决许多实际问题。理解欧拉图的性质和判定条件是应用这些算法的基础。
哈米尔顿回路
哈密尔顿回路是图论中的一个重要概念，指经过图中每个顶点恰好一次并最终回到起点的闭合路径。与欧拉回路（经过每条边一次）不同，哈密尔顿回路关注的是顶点的遍历。
基本概念
1. 定义
哈密尔顿路径：经过图中每个顶点恰好一次的路径
哈密尔顿回路：闭合的哈密尔顿路径（起点=终点）
哈密尔顿图：包含哈密尔顿回路的图
2. 判定条件
哈密尔顿回路的判定是NP完全问题，没有已知的多项式时间算法。但有一些充分条件和必要条件：
充分条件：
Dirac定理：对于n≥3的简单图，若每个顶点度数≥n/2，则是哈密尔顿图
Ore定理：对于n≥3的简单图，若任意两个不相邻顶点u,v满足deg(u)+deg(v)≥n，则是哈密尔顿图
必要条件：
图必须是连通的
没有度数为1的顶点
删除任意k个顶点后，剩余子图的连通分量不超过k个
算法实现
//回溯法（基础实现）
#include <iostream>
#include <vector>
using namespace std;
class Graph {
int V;
vector<vector<int>> adj;
bool hamCycleUtil(vector<int>& path, int pos) {
if (pos == V) {
// 检查最后一个顶点是否与第一个顶点相连
return adj[path[pos-1]][path[0]] == 1;
}
for (int v = 1; v < V; v++) {
if (isSafe(v, path, pos)) {
path[pos] = v;
if (hamCycleUtil(path, pos+1))
return true;
path[pos] = -1; // 回溯
}
}
return false;
}
bool isSafe(int v, vector<int>& path, int pos) {
// 检查当前顶点是否与上一个顶点相连
if (adj[path[pos-1]][v] == 0)
return false;
// 检查是否已经包含在路径中
for (int i = 0; i < pos; i++)
if (path[i] == v)
return false;
return true;
}
public:
Graph(int V) : V(V), adj(V, vector<int>(V, 0)) {}
void addEdge(int u, int v) {
adj[u][v] = 1;
adj[v][u] = 1;
}
bool hamCycle() {
vector<int> path(V, -1);
path[0] = 0; // 从顶点0开始
if (!hamCycleUtil(path, 1)) {
cout << "不存在哈密尔顿回路" << endl;
return false;
}
printSolution(path);
return true;
}
void printSolution(vector<int>& path) {
cout << "哈密尔顿回路: ";
for (int i = 0; i < V; i++)
cout << path[i] << " ";
cout << path[0] << endl;
}
};哈密尔顿回路问题在运筹学、电路设计、生物信息学等领域有重要应用。虽然它是NP难问题，但通过合理的算法选择和优化技巧，可以有效地解决中小规模的实际问题。
并查集
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。它支持两种基本操作：
查找（Find）：确定元素属于哪个子集
合并（Union）：将两个子集合并成一个集合
基本概念
1. 核心操作
| 操作 | 功能描述 |
|---|---|
makeSet(x) |
创建仅包含x的新集合 |
find(x) |
返回x所在集合的代表元素 |
union(x, y) |
合并x和y所在的集合 |
2. 关键思想
代表元：每个集合选择一个元素作为代表
树形结构：用树表示集合，根节点为代表元
路径压缩：优化查找操作
按秩合并：优化合并操作
//基础实现（带路径压缩和按秩合并）
class DSU {
private:
vector<int> parent;
vector<int> rank; // 秩(树高度的上界)
public:
DSU(int n) {
parent.resize(n);
rank.resize(n, 0);
// 初始化每个元素为自己的父节点
for (int i = 0; i < n; 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) return; // 已在同一集合
// 按秩合并
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
};并查集是解决动态连通性问题的利器，在社交网络分析、图像处理、网络连接等领域有广泛应用。掌握其核心思想和优化技巧，能够高效解决许多实际问题。