graph dfs-stack
#include<iostream>
using namespace std;
#include<stack>
int matrix[7][7] = {
//A,B,C,D,E,F,G
/*A*/ {0,0,1,1,0,1,0},
/*B*/ {0,0,1,0,0,0,0},
/*C*/ {1,1,0,1,0,0,0},
/*D*/ {1,0,1,0,0,0,0},
/*E*/ {0,0,0,0,0,0,1},
/*F*/ {1,0,0,0,0,0,1},
/*G*/ {0,0,0,0,1,1,0}
};
bool vis[7];//mark array
//Depth first search
void dfs() {
stack<int> s;
//Start searching from A
s.push(0);
vis[0] = 1;
while (!s.empty()) {
int tmp = s.top();
s.pop();
cout << char(tmp + 'A');//Convert to ascii code
for (int i = 0; i < 7; i + + ) {
if (matrix[tmp][i] != 0 & amp; & amp; !vis[i]) {
s.push(i);
vis[i] = 1;
}
}
}
}
int main() {
dfs();
}
Graph DFS-Recursion
#include<iostream>
using namespace std;
int matrix[7][7] = {
//A,B,C,D,E,F,G
/*A*/ {0,0,1,1,0,1,0},
/*B*/ {0,0,1,0,0,0,0},
/*C*/ {1,1,0,1,0,0,0},
/*D*/ {1,0,1,0,0,0,0},
/*E*/ {0,0,0,0,0,0,1},
/*F*/ {1,0,0,0,0,0,1},
/*G*/ {0,0,0,0,1,1,0}
};
bool vis[7];
int maxx = 0;
//The index in dfs() is called the parameter, and dep is called the stage, which is the level of recursion reached.
void dfs(int index, int dep) {
maxx = max(maxx, dep);
vis[index] = 1;
cout << char(index + 'A');
for (int i = 0; i < 7; i + + ) {
if (matrix[index][i] == 1 & amp; & amp; !vis[i]) {
dfs(i, dep + 1);//You cannot use dep + +, you need to ensure that A is always on the first level, that is, the dep corresponding to A is 1
}
}
}
int main() {
dfs(0,1);
cout << "The maximum search depth is: " << maxx;
return 0;
}
Figure BFS
#include<iostream>
using namespace std;
#include<queue>
int matrix[7][7] = {
//A,B,C,D,E,F,G
/*A*/ {0,0,1,1,0,1,0},
/*B*/ {0,0,1,0,0,0,0},
/*C*/ {1,1,0,1,0,0,0},
/*D*/ {1,0,1,0,0,0,0},
/*E*/ {0,0,0,0,0,0,1},
/*F*/ {1,0,0,0,0,0,1},
/*G*/ {0,0,0,0,1,1,0}
};
bool vis[7];
int maxdep = 0;
void bfs() {
queue<int> q;
q.push(0);
vis[0] = 1;//Set 1 when entering the queue
int last = 0, nlast = 0;
while (!q.empty()) {
int tmp = q.front();
q.pop();
cout << char(tmp + 'A') << " ";
for (int i = 0; i < 7; i + + ) {
if (matrix[tmp][i] == 1 & amp; & amp; !vis[i]) {
q.push(i);
vis[i] = 1;//Every time you enter the queue, set 1 here
nlast = i;
}
}
if (tmp == last) {
cout << endl;//Newline
last = nlast;
maxdep + + ;
}
}
}
Here we use a structure instead of last and nlast in the tree.
//struct node {
// int index;
// int dep;
// node(int id, int d) {//Used a parameterized constructor
// index = id;
// dep = d;
// }
//};
//bool vis[7];
//int maxdep = 1;
//void bfs() {
// queue<node> q;
// q.push(node(0,1));//Construction with parameters
// //q.push(node{ 0,1 }); //List initialization
// vis[0] = 1; //Set 1 when entering the queue
//
// while (!q.empty()) {
// node tmp = q.front();
// q.pop();
// if (tmp.dep - maxdep == 1) cout << endl;//Newline
// maxdep = max(maxdep, tmp.dep);
// cout << char(tmp.index + 'A') << " ";
// for (int i = 0; i < 7; i + + ) {
// if (matrix[tmp.index][i] == 1 & amp; & amp; !vis[i]) {
// q.push(node{i,tmp.dep + 1});
// vis[i] = 1;//Every time you enter the queue, set 1 here
// }
// }
// }
//}
int main() {
bfs();
cout << "The maximum number of search levels is: " << maxdep;
return 0;
}
Maze Problem-DFS
#include<iostream>
using namespace std;
/*
S**.
....
***F
S: starting point F: end point *: wall
*/
char maze[101][101];//maze array
bool vis[101][101];//mark array
int n, m;//n rows and m columns
int sx, sy,/*starting point coordinates*/ fx, fy;/*end point coordinates*/
bool flag = false;//Whether to go to the F flag
int max_dep = 0;
//Direction array right, bottom, left, top
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
//x,y are states
//Deep search: 1. First in, last out 2. Mark 3. Adjacent points (direction array), that is, similar to the picture, traverse adjacent points
void dfs(int x, int y, int dep) {
//If a certain state searched happens to be the end point
if (x == fx & amp; & y == fy) {
flag = true;
max_dep = max(max_dep, dep);
return;
}
//Traverse the direction array, that is, the four possible directions
for (int i = 0; i < 4; i + + ) {
int bx = x + dx[i], by = y + dy[i];
//If it crosses the boundary, no need to search, regenerate a new position
if (bx < 0 || bx >= n || by < 0 || by >= m) continue;
//If the generated new position is a wall, there is no need to search and the new position will be regenerated.
if (maze[bx][by] == '*') continue;
//If the generated new location has been passed (marked), there is no need to repeat the search and regenerate the new location.
if (vis[bx][by]) continue;
vis[bx][by] = 1;
dfs(bx, by, dep + 1);
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i + + ) {
for (int j = 0; j < m; j + + ) {
cin >> maze[i][j];
if (maze[i][j] == 'S') {
sx = i;
sy = j;//Record starting position
}
if (maze[i][j] == 'F') {
fx = i;
fy = j;//Record the end position
}
}
}
vis[sx][sy] = 1;//Mark starting point
dfs(sx, sy, 0);//Initial state
cout << (flag ? "YES\\
" : "NO\\
");
cout << "Search depth is: " << max_dep;
return 0;
}
Maze problem BFS
#include<iostream>
using namespace std;
#include<queue>
int matrix[7][7] = {
//A,B,C,D,E,F,G
/*A*/ {0,0,1,1,0,1,0},
/*B*/ {0,0,1,0,0,0,0},
/*C*/ {1,1,0,1,0,0,0},
/*D*/ {1,0,1,0,0,0,0},
/*E*/ {0,0,0,0,0,0,1},
/*F*/ {1,0,0,0,0,0,1},
/*G*/ {0,0,0,0,1,1,0}
};
bool vis[7];
int maxdep = 0;
void bfs() {
queue<int> q;
q.push(0);
vis[0] = 1;//Set 1 when entering the queue
int last = 0, nlast = 0;
while (!q.empty()) {
int tmp = q.front();
q.pop();
cout << char(tmp + 'A') << " ";
for (int i = 0; i < 7; i + + ) {
if (matrix[tmp][i] == 1 & amp; & amp; !vis[i]) {
q.push(i);
vis[i] = 1;//Every time you enter the queue, set 1 here
nlast = i;
}
}
if (tmp == last) {
cout << endl;//Newline
last = nlast;
maxdep + + ;
}
}
}
Here we use a structure instead of last and nlast in the tree.
//struct node {
// int index;
// int dep;
// node(int id, int d) {//Used a parameterized constructor
// index = id;
// dep = d;
// }
//};
//bool vis[7];
//int maxdep = 1;
//void bfs() {
// queue<node> q;
// q.push(node(0,1));//Construction with parameters
// //q.push(node{ 0,1 }); //List initialization
// vis[0] = 1; //Set 1 when entering the queue
//
// while (!q.empty()) {
// node tmp = q.front();
// q.pop();
// if (tmp.dep - maxdep == 1) cout << endl;//Newline
// maxdep = max(maxdep, tmp.dep);
// cout << char(tmp.index + 'A') << " ";
// for (int i = 0; i < 7; i + + ) {
// if (matrix[tmp.index][i] == 1 & amp; & amp; !vis[i]) {
// q.push(node{i,tmp.dep + 1});
// vis[i] = 1;//Every time you enter the queue, set 1 here
// }
// }
// }
//}
int main() {
bfs();
cout << "The maximum number of search levels is: " << maxdep;
return 0;
}
Dijkstra
#include<iostream>
using namespace std;
#define INF 0x3f3f3f3f
#define row 7
#define col 7
int matrix[row][col]{
//A B C D E F G
/*A*/ {INF,12,INF,INF,INF,16,14},
/*B*/ {12,INF,10,INF,INF,7,INF},
/*C*/ {INF,10,INF,3,6,5,INF},
/*D*/ {INF,INF,3,INF,4,INF,INF},
/*E*/ {INF,INF,5,4,INF,2,8},
/*F*/ {16,7,6,INF,2,INF,9},
/*G*/ {14,INF,INF,INF,8,9,INF}
};
int vis[7], s[7], u[7], nextnode[7];
void Dijkstra(int index) {
vis[index] = 1;
for (int i = 0; i < 7; i + + ) {//First get the U set, which is the set of fixed points for which the shortest path has not been calculated
u[i] = matrix[index][i];//The distance from index to each point
}
int min_cur = index; //Record which point has the smallest distance from index
int count = 6;
while (count--) {
int minx = INF;
for (int i = 0; i < 7; i + + ) {
if (!vis[i] & amp; & amp; u[i] < minx) {//Find the minimum distance and update the S set
minx = u[i];
min_cur = i;
}
}
vis[min_cur] = 1;//Mark, indicating that it has entered the S set
s[min_cur] = minx;
//From the point of the shortest path just calculated, calculate the distance from other points to the index through this point, and whether it is smaller than the original one.
for (int i = 0; i < 7; i + + ) {
int tmp = matrix[i][min_cur] == INF ? INF : minx + matrix[i][min_cur];
if (!vis[i] & amp; & amp; tmp < u[i]) {
u[i] = tmp;//If it is smaller, update the U set
nextnode[i] = min_cur;
}
}
}
}
int main() {
for (int i = 0; i < 7; i + + ) {
nextnode[i] = -1;
}
Dijkstra('D' - 'A');//Find the shortest distance from point D to each point
for (int i = 0; i < 7; i + + ) {
The shortest distance from cout << "D to" << char(i + 'A') << " is: " << s[i] << endl;
}
int index = 0;
while (index != -1) {
cout << char(index + 'A');
index = nextnode[index];
}
cout << "D";
return 0;
}
Search and traceback templates
#include<iostream>
using namespace std;
string s;
bool vis[7];//Mark the array to see if it has been searched
char ans[7];
//Search and backtracking template questions - full arrangement
void dfs(int dep) {//The dep parameter is used in most cases. Add it directly when writing dfs.
//6. Termination condition + data processing
if (dep == s.size() + 1) {
//Search and print principles: search as much as you want and print as much as you want
for (int i = 1; i < dep; i + + ) {
//Print optimization: give priority to C language output
printf("%c", ans[i]);
}
printf("\\
");
return;
}
//1. Number of enumeration schemes
for (int i = 0; i < s.size(); i + + ) {
//2. Mark to prevent repeated searches
if (!vis[i]) {
vis[i] = 1;//mark
//3. Search the current layer
ans[dep] = s[i];
//4. Go to the next level to search
dfs(dep + 1);
//5. Backtracking-restore related status
vis[i] = 0;
}
}
}
int main() {
cin >> s;
dfs(1);
return 0;
}
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 56927 people are learning the system