首页 > 代码库 > 深度优先搜索两个实例
深度优先搜索两个实例
参考算法导论第三版中译本,DFS的Pseudocode如下:
1 DFS(G) 2 for each vertex u ∈ G.V 3 u.color = WHITE 4 u.π = NIL 5 time = 0 6 for each vertex u ∈ G.V 7 if u.color == WHITE 8 DFS-VISIT(G.u) 9 10 DFS-VISIT(G,u) 11 time = time +1 //white vertex u has just been discoverd 12 u.d = time 13 u.color = GRAY 14 for each v ∈ G:adj[u] //explore edge (u,v) 15 if v.color == WHITE 16 v.π = u 17 DFS-VISIT(G,v) 18 u.color = BLACK //blacken u, it is finished 19 time = time + 1 20 u.f = time
以上代码中,以深度优先算法对结点进行遍历,在遍历一个结点后给其盖上一个时间戳,记录其在整个遍历过程中所处的位置顺序。
在搜索算法中,DFS按以下方法实现
1 void dfs(int deep) 2 { 3 if (deep > m) 4 { 5 //check answer 6 } 7 else if (deep <= m) 8 { 9 for (i = 1; i <= n; i++) 10 dfs(deep + 1); 11 } 12 }
实例1. 水仙花数
?一个三位数abc如果满足abc = a^3 + b^3 + c^3 那么就把这个数叫做水仙花数。
?如果一个N位数所有数码的N次方的和加起来等于这个数字本身,我们把这样的数叫做广义水仙花数,容易看出来N = 3是广义水仙花数。
现在,我们的任务是,输入一个m (m < 7) ,让你求出所有满足N = m的广义水仙花数。
实现代码如下
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 int m; 5 int Pow(int x, int n) 6 { 7 int res = 1; 8 while (n--) res *= x; 9 return res; 10 } 11 void dfs(int deep, int curNum, int curSum) 12 { 13 if (deep > m) //类似于base case 14 { 15 if (curNum == curSum) 16 printf("%d\n", curNum); 17 } 18 else if (deep <= m) 19 { 20 int start = (deep == 1); //第一位不为0 21 for (int i = start; i <= 9; i++) 22 dfs(deep + 1, curNum * 10 + i, curSum + Pow(i, m)); 23 //缩小问题规模 24 } 25 } 26 int main() 27 { 28 29 while (scanf("%d", &m), m) 30 { 31 dfs(1, 0, 0); 32 } 33 return 0; 34 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。