undefined

一、广度优先遍搜索

（Breadth-First-Search）

// 使用邻接表作为基础存储结构
class Graph {
private:
    int n;
    std::vector<std::list<int>> abj;
public:
    Graph(int count) : n(count), abj(count, std::list<int>()) {}
    void addNode(int left, int right) {
        abj[left].push_back(right);
        abj[right].push_back(left);
    }
    void bfs(int start, int end) {
        if (start == end) return;
        std::queue<int> qu;
        qu.push(start);
        std::vector<bool> visited(n, false);
        visited[start] = true; 
        std::vector<int> prev(n, -1);
        while (!qu.empty()) {
            int tmp = qu.front();
            qu.pop();
            for (auto x = abj[tmp].begin(); x != abj[tmp].end(); x++) {
                if (!visited[*x]) {
                    prev[*x] = tmp;
                    if ((*x) == end) {
                        print(prev, start, end);
                        return;
                    }
                    visited[*x] = true;
                    qu.push(*x);
                }
            }
        }
    }
private: 
    void print(std::vector<int>& prev, int start, int end) {
        if (prev[end] != -1 && start != end) {
            print(prev, start, prev[end]);
        }
        std::cout << end << " ";
    }
};

• visited 是用来记录已经被访问的顶点，用来避免顶点被重复访问。如果顶点 q 被访问，那相应的 visited[q]会被设置为 true。
• queue 是一个队列，用来存储已经被访问、但相连的顶点还没有被访问的顶点。因为广度优先搜索是逐层访问的，也就是说，我们只有把第 k 层的顶点都访问完成之后，才能访问第 k+1 层的顶点。当我们访问到第 k 层的顶点的时候，我们需要把第 k 层的顶点记录下来，稍后才能通过第 k 层的顶点来找第 k+1 层的顶点。所以，我们用这个队列来实现记录的功能。
• prev 用来记录搜索路径。当我们从顶点 s 开始，广度优先搜索到顶点 t 后，prev 数组中存储的就是搜索的路径。不过，这个路径是反向存储的。prev[w]存储的是，顶点 w 是从哪个前驱顶点遍历过来的。比如，我们通过顶点 2 的邻接表访问到顶点 3，那 prev[3]就等于 2。为了正向打印出路径，我们需要递归地来打印

时间复杂度：最坏情况下，终止顶点 t 离起始顶点 s 很远，需要遍历完整个图才能找到。这个时候，每个顶点都要进出一遍队列，每个边也都会被访问一次，所以，广度优先搜索的时间复杂度是 O(V+E)，其中，V 表示顶点的个数，E 表示边的个数。当然，对于一个连通图来说，也就是说一个图中的所有顶点都是连通的，E 肯定要大于等于 V-1，所以，广度优先搜索的时间复杂度也可以简写为 O(E)。

空间复杂度：广度优先搜索的空间消耗主要在几个辅助变量 visited 数组、queue 队列、prev 数组上。这三个存储空间的大小都不会超过顶点的个数，所以空间复杂度是 O(V)。

二、深度优先搜索

（Depth-First-Search）

void dfs(int start, int end) {
     if (start == end) return;
     found = false;
     std::vector<bool> visited(count, false);
     std::vector<int> prev(count, -1);
     recurDfs(prev, visited, start, end);   
     print(prev, start, end);
     std::cout << std::endl;
 }

 void recurDfs(std::vector<int>& prev, std::vector<bool>& visited, int start, int end) {
     if (start == end || visited[start]) return;
     visited[start] = true;
     for (auto iter = abj[start].begin(); iter != abj[start].end(); ++iter) {
         if (!visited[*iter]) {
             prev[*iter] = start;
             recurDfs(prev, visited, *iter, end);
         }
     }
 }

 void recurDfs2(std::vector<int>& prev, std::vector<bool>& visited, int start, int end) {
     if (found) return;
     visited[start] = true;
     if (start == end) {
         found = true;
         return;
     }
     for (auto iter = abj[start].begin(); iter != abj[start].end(); ++iter) {
         if (!visited[*iter]) {
             prev[*iter] = start;
             recurDfs(prev, visited, *iter, end);
         }
     }
 }

有个比较特殊的变量 found，它的作用是，当我们已经找到终止顶点 t 之后，我们就不再递归地继续查找了。

• 时间复杂度：每条边最多会被访问两次，一次是遍历，一次是回退。所以，图上的深度优先搜索算法的时间复杂度是 O(E)，E 表示边的个数。
• 空间复杂度：深度优先搜索算法的消耗内存主要是 visited、prev 数组和递归调用栈。visited、prev 数组的大小跟顶点的个数 V 成正比，递归调用栈的最大深度不会超过顶点的个数，所以总的空间复杂度就是 O(V)。

三、问题

• 如何找出社交网络中某个用户的三度好友关系？也就是好友的好友

  其实使用广度优先搜索即可解决。广度优先搜索第一层就是用户的一度好友，第二层就是用户好友的好友