广度优先搜索算法c语言实现（广度优先搜索代码c语言实现）



深度优先搜索的实现时递归，搜索算法的原理就是枚举，利⽤计算机的⾼效，在加上⼈类制定的规则，枚举出所有的可能情况，找到可⾏的解或最有的解。

深度优先搜索时图遍历的⼀种，⽤⼀句话概括就是“⼀直往下⾛，⾛不通就回头，换路再⾛，直到⽆路可⾛”具体

算法描述：

选择⼀个起始点u作为当前结点，执⾏操作

a.访问当前结点，并标记该结点以被访问，然后跳到b；

b.如果存在⼀个和当前结点相邻并且尚未访问的结点u，则将u设为当前结点，继续执⾏a

c.如果不存在这样的u结点，则进⾏回溯，回溯的过程就是回退当前结点

上述所说的当前结点需要使⽤栈来维护，每次访问新的结点加⼊栈，回溯的时候就出栈。

例如：给定⼀个n个结点的⽆向图，要求访问到的结点⼊栈，回溯的时候出栈，求输出整个过程的遍历序列。

遍历规则：

1、如果当前结点的相邻结点已经被访问，则不能再访问

2、每次从当前结点到相邻结点中寻⼀个编号最⼩的没有访问的结点进⾏访问

如图1所示，对上图以深度优先的⽅式进⾏遍历，起点是 0；

算法实现：

1、visit1[MAXN]数组是⼀个bool数组，⽤来标记某个结点是否被访问，初始化为false；已经访问过的结点执⾏

回溯

2、visit1[u] = true；对未访问结点u标记为访问状态

3、dfs_add(u);⽤来u存储到访问序列中，函数实现:

4、adj[MAXN][MAXN]是图的邻接矩阵，⽤0或1来代表点是否连通。程序如下：

adj[u][v] = 1代表u和v之间存在⼀条边；adj[u][v] = 0代表没有边

给出n（n<=10）, 求n！ = n*(n-1).....3*2*1，f(n) = n!,f(n) = n*f(n-1)(n>0).

满⾜递归的特性，深搜可以从n结点到0结束，结束的返回值为1;

https://blog.csdn.net/A_66/article/details/?spm=1001.2014.3001.5501

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/goyykf/41314.html