# • DFS: ### • 全名:Depth-First-Search,中文名:深度优先搜索。 ### • 算法简要过程:对每一个可能的分支路径深入到不能再深入为止,而且每个节 点只能访问一次。简单的说就是一次性走到无路可走再返回上一步在往下走到无路可走 ## 图的dfs  ### 模板 `void dfs(答案,搜索层数,其他参数){ if(层数==maxdeep){ 更新答案; return; } (剪枝) for(枚举下一层可能的状态){ 更新全局变量表示状态的变量; dfs(答案+新状态增加的价值,层数+1,其他参数); 还原全局变量表示状态的变量; } }` ## 进入正题 #### 1.dfs遍历图 之前的图大家也看了，我们发现dfs可以遍历一张图 从图中某个顶点v出发，首先访问v;访问结点v的第一个邻接点，以这个邻接点vt作为一个新节点，访问vt所有邻接点。直到以vt出发的所有节点都被访问到，回溯到v的下一个未被访问过的邻接点，以这个邻结点为新节点，重复上述步骤，直到图中所有与v相通的所有节点都被访问到。若此时图中仍有未被访问的结点，则另选图中的一个未被访问的顶点作为起始点。重复该过程，直到图中的所有节点均被访问过。  用一个b数组记录该点是否被访问过。 ` #include<bits/stdc++.h> using namespace std; struct Edge { int to,w,next; }edge[100001]; int k,n,m,x,y,z,sum=0,b[100001],head[100001]; inline void add(int u,int v,int w)//领接链表建图 { edge[++k].to=v; edge[k].w=w; edge[k].next=head[u]; head[u]=k; } void dfs(int u)//dfs遍历,u表示当前所在的起点编号 { sum++; if(sum==n)return; for(register int i=head[u];i;i=edge[i].next) if(!b[edge[i].to]) { b[edge[i].to]=1; dfs(i); } } int main() { scanf("%d%d",&n,&m); for(register int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z); } for(register int i=1;i<=n;i++) if(!b[i])dfs(i); return 0; } `