首页 > 代码库 > 深度优先搜索两个实例

深度优先搜索两个实例

2024-07-03 12:03:54   228人阅读

参考算法导论第三版中译本，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 +１        //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 }

 

 


联系
我们