搜索算法

深度優先搜索

一種用于遍歷或搜索樹或圖的算法。它沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。

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; // 不可達
}

?

注意事項

1. 訪問標記：必須在入隊時標記，而非出隊時

2. 隊列大小：處理層級時需要先保存當前隊列大小

3. 邊界檢查：網格類問題注意邊界條件

4. 狀態表示：復雜狀態需要設計良好的哈希函數

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]++;}}
};

?并查集是解決動態連通性問題的利器，在社交網絡分析、圖像處理、網絡連接等領域有廣泛應用。掌握其核心思想和優化技巧，能夠高效解決許多實際問題。