第五十天 第十一章：图论part01 图论理论基础 深搜理论基础 98. 全部可达路 ...

 图论理论基础
相识邻接矩阵(*)，度，邻接表（数组+链表）等        遍历次序：深搜加广搜
深搜理论基础  
dfs是可一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，再换方向（换方向的过程就涉及到了回溯）。

1. void dfs(参数) {
2.     if (终止条件) {
3.         存放结果;
4.         return;
5.     }
7.     for (选择：本节点所连接的其他节点) {
8.         处理节点;
9.         dfs(图，选择的节点); // 递归
10.         回溯，撤销处理结果
11.     }
12. }

复制代码

98. 全部可达路径  
留意图的输入形式，这里图用二维数组graph[t]表示，其中s,t表示s,t两点之间是否相连，相连赋值为1，不然为0。
后面深搜的方法和回溯三部曲险些一样。

1. #include<iostream>
2. #include<vector>
3. using namespace std;
5. vector<vector<int>> res;
6. vector<int> path;
8. void dfs(const vector<vector<int>> &graph , int m ,int n){
9.     if(m==n){
10.        res.push_back(path);
11.        return ;
12.     }
13.    
14.     for(int i=1;i<=n;i++){
15.         if(graph[m][i]==1){
16.             path.push_back(i);
17.             dfs(graph,i,n);
18.             path.pop_back();
19.         }
20.     }
21. }
23. int main(){
24.     int N,M,s,t;
25.     cin>>N>>M;
26.     vector<vector<int>> graph(N + 1,vector<int>(N + 1,0));
27.     while(M--){
28.        cin>>s>>t;
29.        graph[s][t]=1;
30.     }
31.     path.push_back(1);
32.     dfs(graph,1,N);
33.     if (res.size() == 0) cout << -1 << endl;
34.     for (const vector<int> &pa : res) {
35.         for(int i=0;i<pa.size()-1;i++){
36.          cout<<pa[i]<<" ";
37.         }
38.         cout<<pa[pa.size()-1]<<endl;
39.     }
41.     return 0;
42. }

复制代码

广搜理论基础
bfs是先把本节点所毗连的全部节点遍历一遍，走到下一个节点的时候，再把毗连节点的全部节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。

1. int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
2. // grid 是地图，也就是一个二维数组
3. // visited标记访问过的节点，不要重复访问
4. // x,y 表示开始搜索节点的下标
5. void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
6.     queue<pair<int, int>> que; // 定义队列
7.     que.push({x, y}); // 起始节点加入队列
8.     visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点
9.     while(!que.empty()) { // 开始遍历队列里的元素
10.         pair<int ,int> cur = que.front(); que.pop(); // 从队列取元素
11.         int curx = cur.first;
12.         int cury = cur.second; // 当前节点坐标
13.         for (int i = 0; i < 4; i++) { // 开始想当前节点的四个方向左右上下去遍历
14.             int nextx = curx + dir[i][0];
15.             int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标
16.             if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 坐标越界了，直接跳过
17.             if (!visited[nextx][nexty]) { // 如果节点没被访问过
18.                 que.push({nextx, nexty});  // 队列添加该节点为下一轮要遍历的节点
19.                 visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问
20.             }
21.         }
22.     }
24. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。