培训机构推荐,seo的基本步骤顺序正确的是,国内服务器免备案方法,制作网站服务器搜索算法
深度优先搜索 一种用于遍历或搜索树或图的算法。它沿着树的深度遍历树的节点#xff0c;尽可能深的搜索树的分支。 DFS核心思想 深度优先#xff1a;尽可能深地搜索树的分支 回溯思想#xff1a;当节点v的所在边都已被探寻过#xff0c;搜索将回溯到发现节点v的…搜索算法
深度优先搜索 一种用于遍历或搜索树或图的算法。它沿着树的深度遍历树的节点尽可能深的搜索树的分支。 DFS核心思想 深度优先尽可能深地搜索树的分支 回溯思想当节点v的所在边都已被探寻过搜索将回溯到发现节点v的那条边的起始节点 递归实现通常用递归方式自然地实现DFS void dfs(Node* node, vectorbool visited) {// 标记当前节点为已访问visited[node-val] true;cout node-val ;// 访问所有相邻节点for (Node* neighbor : node-neighbors) {if (!visited[neighbor-val]) {dfs(neighbor, visited);}}
}递归实现 经典运用 //图的连通分量
int countComponents(int n, vectorvectorint edges) {vectorvectorint graph(n);vectorbool 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, vectorvectorint graph, vectorbool visited) {visited[node] true;for (int neighbor : graph[node]) {if (!visited[neighbor]) {dfs(neighbor, graph, visited);}}
} DFS是解决许多算法问题的强大工具掌握其核心思想和各种优化技巧对算法能力提升至关重要。 广度优先搜索 一种用于遍历或搜索树或图的算法。它从根节点开始先访问所有相邻节点然后再依次访问这些节点的相邻节点以此类推。 BFS核心思想 层级遍历按照距离起始节点的层级依次访问 队列结构使用队列来存储待访问节点 最短路径在无权图中能找到最短路径 #include queue
#include vectorusing namespace std;//标准实现 使用队列
void bfs(Node* start) {if (!start) return;queueNode* q;vectorbool 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;queueNode* q;unordered_mapNode*, 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 algorithmusing namespace std;class Graph {int V;vectorvectorint adj;vectorvectorint revAdj;void fillOrder(int v, vectorbool visited, stackint st) {visited[v] true;for (int u : adj[v]) {if (!visited[u]) {fillOrder(u, visited, st);}}st.push(v);}void DFSUtil(int v, vectorbool visited, vectorint 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);}vectorvectorint findSCCs() {stackint st;vectorbool 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);vectorvectorint sccs;// 第二次DFS按照栈的顺序处理逆图while (!st.empty()) {int v st.top();st.pop();if (!visited[v]) {vectorint component;DFSUtil(v, visited, component);sccs.push_back(component);}}return sccs;}
}; // Tarjan算法一次DFS
#include iostream
#include vector
#include stack
#include algorithmusing namespace std;class Graph {int V;vectorvectorint adj;void tarjanSCCUtil(int u, vectorint disc, vectorint low, stackint st, vectorbool inStack, vectorvectorint 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]) {vectorint 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);}vectorvectorint tarjanSCC() {vectorint disc(V, -1), low(V, -1);vectorbool inStack(V, false);stackint st;vectorvectorint 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, vectorvectorint sccs) {// 创建顶点映射原始顶点 - 缩点后的顶点编号vectorint vertexToComponent(g.V);for (int i 0; i sccs.size(); i) {for (int v : sccs[i]) {vertexToComponent[v] i;}}// 构建缩点后的图Graph condensed(sccs.size());unordered_setstring 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 algorithmusing namespace std;class Graph {int V;vectorvectorint adj;void BCCUtil(int u, vectorint disc, vectorint low, stackpairint, int st, vectorbool isAP,vectorvectorpairint, 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;// 输出双连通分量vectorpairint, 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);}pairvectorbool, vectorvectorpairint, int findBCCs() {vectorint disc(V, -1), low(V, -1);vectorbool isAP(V, false);stackpairint, int st;vectorvectorpairint, int bccs;int time 0;for (int i 0; i V; i) {if (disc[i] -1) {BCCUtil(i, disc, low, st, isAP, bccs, time);// 处理剩余边vectorpairint, 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};}
};//查找桥割边算法
vectorpairint, int findBridges(Graph g) {vectorint disc(g.V, -1), low(g.V, -1);vectorpairint, 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, vectorint disc, vectorint low,vectorpairint, 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 algorithmusing namespace std;class Graph {int V;vectorvectorint 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);}}vectorint findEulerianCircuit() {vectorint circuit;stackint 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 vectorusing namespace std;class Graph {int V;vectorvectorint adj;bool hamCycleUtil(vectorint 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, pos1))return true;path[pos] -1; // 回溯}}return false;}bool isSafe(int v, vectorint 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, vectorint(V, 0)) {}void addEdge(int u, int v) {adj[u][v] 1;adj[v][u] 1;}bool hamCycle() {vectorint path(V, -1);path[0] 0; // 从顶点0开始if (!hamCycleUtil(path, 1)) {cout 不存在哈密尔顿回路 endl;return false;}printSolution(path);return true;}void printSolution(vectorint 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:vectorint parent;vectorint 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];}}
}; 并查集是解决动态连通性问题的利器在社交网络分析、图像处理、网络连接等领域有广泛应用。掌握其核心思想和优化技巧能够高效解决许多实际问题。
