C++广度优先搜索

广度优先搜索：

求解最短路、求解连通性问题、时间复杂度相对较稳定、需要哈希表和队列的数据结构基础

算法描述：

第一步，初始化数据结构，广搜在计算过程中，需要利用一个哈希表visited和一个队列queue来记录当前访问过的节点，其中哈希表是为了快速查找某个节点是否被访问，并且执行插入，队列是为了记录顶点的访问顺序.

第二步，起点入队，先把起点s插入队列中，并且在哈希表中把起点s标记掉。

第三步，顶点访问，如果队列不为空，弹出一个队列首元素u，继续访问和u相邻的顶点v，如果v不在哈希表中，则在哈希表中标记掉v，并且把v插入到队列中，直到队列为空，搜索结束。

代码分析，第一步，初始化数据结构

function initEdges(n, edges[maxn])

  for i -> (0, n-1)

    edges[i] = {}

第二步，邻接表加边

function addEdge(edges[maxn], u, v)

  edges[u].append(v)

第三步，广搜的过程

function bfs(n, s, edges[maxn], visited)

  q = Queue()

  visited.clear()

  q.push(s)

  visited.add(s)

  while(not q.empty())

    u = q.front()

    q.pop()

    for i -> (0, edges[u].size() - 1)

     v = edges[u][i]

     if(v not in visited)

       q.push(v)

       visited.add(v)

代码练习 1 对应力扣，寻找图中是否存在路径，代码见下

#define maxn 200001class Solution {vector<vector<int>> edges;void initEdges(int n){edges.clear();for(int i=0; i<n; ++i){edges.push_back({});}}void addEdges(int u, int v){edges[u].push_back(v);}void dfs(int n, int s, bool visited[maxn]){queue<int> q;for(int i=0; i<n; ++i){visited[i] = false;}q.push(s);visited[s] = true;while(!q.empty()){int u = q.front();q.pop();for(int i=0; i<edges[u].size(); ++i){int v = edges[u][i];if(!visited[v]){q.push(v);visited[v] = true;}}}}public:bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {initEdges(n);for(int i=0; i<edges.size(); ++i){int u = edges[i][0];int v = edges[i][1];addEdges(u, v);addEdges(v, u);}bool v[maxn];dfs(n, source, v);return v[destination];}
};

  代码练习2，对应力扣，钥匙和房间，代码见下

#define maxn 1001
class Solution {vector<vector<int>> edges;void initEdges(int n){edges.clear();for(int i=0; i<n; ++i){edges.push_back({});}}void addEdges(int u, int v){edges[u].push_back(v);}void dfs(int n, int s, bool visited[maxn]){queue<int> q;for(int i=0; i<n; ++i){visited[i] = false;}q.push(s);visited[s] = true;while(!q.empty()){int u = q.front();q.pop();for(int i=0; i<edges[u].size(); ++i){int v = edges[u][i];if(!visited[v]){q.push(v);visited[v] = true;}}}}
public:bool canVisitAllRooms(vector<vector<int>>& rooms) {int n = rooms.size();initEdges(n);for(int i=0; i<n; ++i){for(int j=0; j < rooms[i].size(); ++j){addEdges(i, rooms[i][j]);}}bool v[maxn];dfs(n, 0, v);for(int i=0; i<n; ++i){if(v[i] == false){return false;}}return true;}
};

代码练习，对应力扣，受限条件下可到达节点的数量 代码见下

#define maxn 200001class Solution {vector<vector<int>> edges;void initEdges(int n){edges.clear();for(int i=0; i<n; ++i){edges.push_back({});}}void addEdges(int u, int v){edges[u].push_back(v);}void dfs(int n, int s, bool visited[maxn]){queue<int> q;for(int i=0; i<n; ++i){visited[i] = false;}q.push(s);visited[s] = true;while(!q.empty()){int u = q.front();q.pop();for(int i=0; i<edges[u].size(); ++i){int v = edges[u][i];if(!visited[v]){q.push(v);visited[v] = true;}}}}
public:int reachableNodes(int n, vector<vector<int>>& e, vector<int>& restricted) {initEdges(n);int hash[maxn];memset(hash, 0, sizeof(hash));for(int i=0; i<restricted.size(); ++i){hash[restricted[i]] = 1;}for(int i=0; i<e.size(); ++i){int u = e[i][0];int v = e[i][1];if(hash[u] + hash[v] == 0){addEdges(u, v);addEdges(v, u);               }}bool v[maxn];dfs(n, 0, v);int ans = 0;for(int i=0; i<n; ++i){if(v[i]){++ans;}       }return ans;}
};