深度优先搜索与广度优先搜索的比较_代价树的深度优先和有界广度优先哪个好

1.深度优先搜索

  深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

简单面试题

  面试题一：颜色填充。编写函数，实现许多图片编辑软件都支持的“颜色填充”功能。给定一个屏幕（以二维数组表示，元素为颜色值）、一个点和一个新的颜色值，将新颜色值填入这个点的周围区域，直到原来的颜色值全都改变。

代码：

class Solution {
public:
    bool visits[50][50];
    int old;
    void dfs(vector<vector<int>>& image,int i,int j,int newColor) {       
        if(i < 0 || i >=  image.size() || j < 0;j >= image[0].size())  //超出图像范围，就停止搜索
            return ;
        image[i][j] = newColor; 										//填充新像素
        visits[i][j] = true;
	        //如果相邻位置存在	没有访问过	是需要改变的像素
        if(i - 1 >= 0 && !visits[i - 1][j] && image[i - 1][j] == old)
            dfs(image,i - 1,j,newColor);			//进行深度搜索				
        if(j + 1 < image[0].size() && !visits[i][j + 1] && image[i][j + 1]  == old)
            dfs(image,i,j + 1,newColor);
        if(i + 1 < image.size() && !visits[i + 1][j] && image[i + 1][j]  == old)
            dfs(image,i + 1,j,newColor);
        if(j - 1 >=0 && !visits[i][j - 1] && image[i][j - 1] == old )
            dfs(image,i,j - 1,newColor);

    }

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
         int row = image.size(),col = image[0].size();
         if(row <= 0 || col <= 0 || sr >= row || sc >= col) {	//当输入不合理是，返回为空
             image.clear();
             return image;
         }                   
         for(int i = 0;i < row;i++) 							//初始化标志数组
            for(int j = 0;j < col;j++)
                visits[i][j] = false;
        old = image[sr][sc]; 									//记录下要改变的像素
        dfs(image,sr,sc,newColor); 								//开启深度优先搜索
        return image;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

总结：
深度优先搜索类似于树的前序遍历。可以通过下图的遍历结果证明。

面试题

  设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。如果指定节点没有对应的“下一个”节点，则返回null。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    //如果右不存在，就是上一个；右存在，就是右
    TreeNode *res = NULL;
    bool flag = false;
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if(root == NULL)
            return NULL;

        inorderSuccessor(root->left,p);

        if (flag && nullptr == res) {            
			res = root;
			return res;
		}
		if (res) {                              //当找到后，就不继续下面的搜索了
            return res;
        }
        if (root == p) {                        //中序遍历，当存在一个结点等于p时，标志为true
			flag = true;
		}

        inorderSuccessor(root->right,p);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

2.广度优先搜索

  广度优先搜索BFS（Breadth First Search）也称为宽度优先搜索，它是一种先访问的结点先扩展的策略。
   广度优先搜索算法的搜索步骤一般是：

 （1）从队列头取出一个结点，检查它按照扩展规则是否能够扩展，如果能则产生一个新结点。
 （2）检查新生成的结点，看它是否已在队列中存在，如果新结点已经在队列中出现过，就放弃这个结点，然后回到第（1）步。否则，如果新结点未曾在队列中出现过，则将它加入到队列尾。
 （3）检查新结点是否y为目标结点。如果新结点是目标结点，则搜索成功，程序结束；若新结点不是目标结点，则回到第（1）步，再从队列头取出结点进行扩展。
1
2
3

最终可能产生两种结果：找到目标结点，或扩展完所有结点而没有找到目标结点。

简单面试题

  给定一个保存员工信息的数据结构，它包含了员工唯一的id，重要度 和 直系下属的id。比如，员工1是员工2的领导，员工2是员工3的领导。他们相应的重要度为15, 10, 5。那么员工1的数据结构是[1, 15, [2]]，员工2的数据结构是[2, 10, [3]]，员工3的数据结构是[3, 5, []]。注意虽然员工3也是员工1的一个下属，但是由于并不是直系下属，因此没有体现在员工1的数据结构中。
  现在输入一个公司的所有员工信息，以及单个员工id，返回这个员工和他所有下属的重要度之和。
代码：

/*
// Definition for Employee.
class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};
*/
class Solution {
public:
    Employee* findEmployeeById(vector<Employee*> employees,int id) {
        for(int i = 0;i < employees.size();i++)
            if(employees[i]->id == id)
                return employees[i];
        return NULL;
    }
    int getImportance(vector<Employee*> employees, int id) {
        queue<Employee*> q;
       Employee* head = findEmployeeById(employees,id);
       q.push(head);
       int sum = 0;
       while(!q.empty()) {
           for(int i = q.size();i;i--) {
               Employee *front = q.front();
               sum += front->importance;
               q.pop();
               for(int j = 0;j < front->subordinates.size();j++) {
                   q.push(findEmployeeById(employees,front->subordinates[j]));
               }
           }
       }
       return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

面试题

  给定字典中的两个词，长度相等。写一个方法，把一个词转换成另一个词， 但是一次只能改变一个字符。每一步得到的新词都必须能在字典中找到。编写一个程序，返回一个可能的转换序列。如有多个可能的转换序列，你可以返回任何一个。
代码：

/*该题需要注意的是：如何将路径给记录下来，此处采用的结构是queue<pair<string, string>>，first是下一个结点单词，后面是一个字符串路径，单词之间使用“-”连接，这样通过转换找到了目标单词后，second就是该路径的字符串，如例子：
begword = "hit"
endword = "cog"
wodlist = ["hot","dot","dog","lot","log","cog"]

最后路径字符串为：hit-hot-dot-dog-cog
然后进行字符串分割即可
*/
class Solution {
public:
    vector<string> testSplit(const string& line, const char& delim)
    {
        vector<string> ret;
        string temp = "";
        int i = 0;
        while (line[i] != '\0') {
            if (line[i] - delim == 0) {
                ret.push_back(temp);
                temp = "";
            }
            else
                temp = temp + line[i];
            i++;
        }
        if(temp.length() > 0)
            ret.push_back(temp);
        return ret;
    }
    /* 建立通用状态对应的单词列表映射关系 */
    void generateMap(int len, map<string,vector<string>> &mp, vector<string>& wordList){
        for (auto word : wordList){
            for (int i = 0; i < len; i++){
                string tmp_word = word;
                tmp_word[i] = '*';
                if (mp.count(tmp_word) == 0) {
                    vector<string> vec = { word };
                    mp.insert({ tmp_word, vec });
                } else {
                    mp[tmp_word].push_back(word);
                }
            }
        }
    }

    vector<string> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        int count = 1;
        int len = beginWord.size();
        map<string, vector<string>> mp; /* 通用状态对应的单词字典 */
        queue<pair<string, string>> Q;
        set<string> st;
        vector<string> vec;


        /* 建立通用状态对应的单词列表映射关系 */
        generateMap(len, mp, wordList);

        Q.push({ beginWord, beginWord});
        st.insert(beginWord);

        while (!Q.empty()) {
            int size = Q.size();
            //遍历当前队列中所有单词 
            for (int i = 0; i < size; i++){
                pair<string, string> front = Q.front();
                
                /* 如果当前单词与目标单词一致，则完成搜索 */
                if (front.first == endWord) {
                    return testSplit(front.second, '-');
                    
                }
                Q.pop();

                /* 找到当前单词所有可能的下一个目标单词 */
                for (int j = 0; j < len; j++){
                    string w = front.first;
                    w[j] = '*';
                    /* 找到连接的边 */
                    if (mp.count(w) != 0) {
                        for (auto a : mp[w]) {                              //此处遍历所有邻居，相当于广度优先搜索
                            if (st.count(a) == 0) {//没有搜索过的才加入到队列
                                Q.push({a, front.second + "-" + a});
                                st.insert(a);
                            }
                        }
                    }
                }
            }
        }
        return vec;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

3.两种优先算法的比较

实现方式：深度优先遍历用栈，广度优先遍历用队列；
与树的遍历关系：深度优先遍历对应树的先序、中序和后序三种遍历， 广度优先遍历对就树的层次遍历。
应用:深度优先遍历可以用来判断有向图是否有环