阅读量:0
图论理论基础
了解邻接矩阵(*)，度，邻接表（数组+链表）等 遍历顺序：深搜加广搜
深搜理论基础
dfs是可一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，再换方向（换方向的过程就涉及到了回溯）。
void dfs(参数) { if (终止条件) { 存放结果; return; } for (选择：本节点所连接的其他节点) { 处理节点; dfs(图，选择的节点); // 递归 回溯，撤销处理结果 } } 98. 所有可达路径
注意图的输入形式，这里图用二维数组graph[s][t]表示，其中s,t表示s,t两点之间是否相连，相连赋值为1，不然为0。
后面深搜的方法和回溯三部曲几乎一样。
#include<iostream> #include<vector> using namespace std; vector<vector<int>> res; vector<int> path; void dfs(const vector<vector<int>> &graph , int m ,int n){ if(m==n){ res.push_back(path); return ; } for(int i=1;i<=n;i++){ if(graph[m][i]==1){ path.push_back(i); dfs(graph,i,n); path.pop_back(); } } } int main(){ int N,M,s,t; cin>>N>>M; vector<vector<int>> graph(N + 1,vector<int>(N + 1,0)); while(M--){ cin>>s>>t; graph[s][t]=1; } path.push_back(1); dfs(graph,1,N); if (res.size() == 0) cout << -1 << endl; for (const vector<int> &pa : res) { for(int i=0;i<pa.size()-1;i++){ cout<<pa[i]<<" "; } cout<<pa[pa.size()-1]<<endl; } return 0; } 广搜理论基础
bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向 // grid 是地图，也就是一个二维数组 // visited标记访问过的节点，不要重复访问 // x,y 表示开始搜索节点的下标 void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) { queue<pair<int, int>> que; // 定义队列 que.push({x, y}); // 起始节点加入队列 visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点 while(!que.empty()) { // 开始遍历队列里的元素 pair<int ,int> cur = que.front(); que.pop(); // 从队列取元素 int curx = cur.first; int cury = cur.second; // 当前节点坐标 for (int i = 0; i < 4; i++) { // 开始想当前节点的四个方向左右上下去遍历 int nextx = curx + dir[i][0]; int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标 if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 坐标越界了，直接跳过 if (!visited[nextx][nexty]) { // 如果节点没被访问过 que.push({nextx, nexty}); // 队列添加该节点为下一轮要遍历的节点 visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问 } } } }