图的遍历 之 深搜dfs

DFS 遍历 深度优先搜索是一个递归过程，有回退过程。 对一个无向连通图，在访问图中某一起始顶点 u 后，由 u 出发，访问它的某一邻接顶点 v1 ；再从 v1 出发，访 问与 v1 邻接但还没有访问过的顶点 v2 ；然后再从 v2 出发，进行类似的访问； … ；如此进行下去，直至到达 所有邻接顶点都被访问过的某个顶点 x 为止；接着，回 退一步，回退到前一次刚访问过的顶点，看是否还有其 它没有被访问过的邻接顶点，如果有，则访问此顶点， 之后再从此顶点出发，进行与前述类似的访问；如果没 有，就再回退一步进行类似的访问。 重复上述过程，直到该连通图中所有顶点都被访问过为 止。 深搜过程：

 

深搜算法实现：

 

代码如下： 1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 char maps[10][11]; 5 bool vis[1000]; 6 int q,m; 7 void dfs(int a){ 8 vis[a]=1; 9 if(a<q) 10 printf("%c --> ",a+64); 11 else printf("%c",a+64); 12 for(int i=1;i<=q;i++) 13 { 14 if(maps[a][i]==1&&vis[i]==0) 15 dfs(i); 16 } 17 } 18 int main() 19 { 20 21 char a,b; 22 cin>>q>>m; 23 for(int i=1;i<=m;i++) 24 { 25 cin>>a>>b; 26 maps[a-64][b-64]=1; 27 maps[b-64][a-64]=1; 28 } 29 dfs(1); 30 }

 

转载于:https://www.cnblogs.com/sssy/p/6682520.html