图的遍历（深度优先搜素和广度优先搜素）

#includestdio.h//struct note//{// int x;// int y;//};//char a[20][21];//int getnum(int i, int j)//{// int sum, x, y;// sum 0;//统计消灭敌人数量// x i;y j;// while (a[x][y] ! #)// {// if (a[x][y] G)// {// sum;// }// x--;// }// x i;y j;// while (a[x][y] ! #)// {// if (a[x][y] G)// {// sum;// }// x;// }// x i;y j;// while (a[x][y] ! #)// {// if (a[x][y] G) {// sum;// }// y--;// }// x i;y j;// while (a[x][y] ! #)// {// if (a[x][y] G)// {// sum;// }// y;// }// return sum;//}//计算某个区块面积//struct note//{// int x;// int y;//};//在此处省略用DFS解决的代码//图的遍历//首先讲明什么是图就是点之间连线//图的储存用i行j列的矩阵储存表示i到j点有没有线1是有无穷是没有0表示自己与自己之间没线//int book[101], sum, n, e[101][100];//void dfs(int cur)//{// int i;// printf(%d , cur);// sum;// if (sum n) return;// for (i 1;i n;i)// {// if (e[cur][i] 1 book[i] 0) {// book[i] 1;// dfs(i);//// }// }// return;//}//int min 99999999, book[101], n, e[101][101];//void dfs(int cur, int dis)//cur是城市编号dis是走过的路程最短路程//{// int j;// if (dis min)return;// if (cur n)// {// if (dis min) min dis;// return;// }// for (j 1;j n;j)// {// if (e[cur][j] ! 99999999 book[j] 0)// {// book[j] 1;// dfs(j, dis e[cur][j]);// book[j] 0;// }// }// return;//}structnote{intx;ints;};intmain(){// struct note que[401];// int head, tail;// int book[20][20] { 0 };// int i, j, k, sum, max 0, mx, my, n, m, startx, starty, tx, ty;// int next[4][2] { {0,1},{1,0},{0,-1},{-1,0} };// scanf_s(%d %d %d %d, n, m, startx, starty);// for (i 0;i n - 1;i)// {// scanf_s(%s, a[i],21);//a[i]是a[i][j]的首地址可以输入第i行的数据//缺少缓冲区大小参数就只能输入限定量的数字// }// head 1;// tail 1;// que[tail].x startx;// que[tail].y starty;// tail;// book[startx][starty] 1;// max getnum(startx, starty);//把起点的消灭敌人数量记为消灭最大数量max的初始值// mx startx;// my starty;// while (head tail)// {// for (k 0;k 3;k)// {// tx que[head].x next[k][0];// ty que[head].y next[k][1];// if (tx0 || txn - 1 || ty0 || tym - 1)// {// continue;// }// if (a[tx][ty] . book[tx][ty] 0)// {// book[tx][ty] 1;// que[tail].x tx;// que[tail].y ty;// tail;// sum getnum(tx, ty);// if (sum max) {// max sum;// mx tx;// my ty;//更新最大值// }// }// }// head;//一个点扩展结束head对后面的点进行扩展//// }// printf((%d,%d),%d\n, mx, my, max);//struct note que[2501];//int head, tail;//int a[50][51];//储存地图//int book[50][51] { 0 };//int i, j, k, sum, max 0, mx, my, n, m, startx, starty, tx, ty;//int next[4][2] { {0,1},{1,0},{0,-1},{-1,0} };//scanf_s(%d %d %d %d, n, m, startx, starty);//for (i 1;i n;i)// for (j 1;j m;j)// scanf_s(%d, a[i][j]);//head 1;//tail 1;//book[startx][starty] 1;//que[tail].x startx;//que[tail].y starty;//tail;//sum 1;//while (head tail)//{// for (k 0;k 3;k)// {// tx que[head].x next[k][0];// ty que[head].y next[k][1];// if (tx 1 || txn || ty1 || tym)// continue;// if (a[tx][ty] 0 book[tx][ty] 0)// {// sum;// book[tx][ty] 1;// que[tail].x tx;// que[tail].y ty;// tail;// }// }// head;//}//printf(%d\n, sum);//int i, j, m, a, b;//scanf_s(%d %d, n, m);//n是顶点数量m是边的数量//for (i 1;i n;i)//{// for (j 1;j n;j)// if (i j) e[i][j] 0;// else e[i][j] 99999999;//}//for (i 1;i m;i)//{// scanf_s(%d %d, a, b);// e[a][b] 1;// e[b][a] 1;//没有方向//}//book[1] 1;//dfs(1);//接下来看看广度优先搜索的遍历/*int i, j, n, m, a, b, cur, book[101] { 0 }, e[101][101]; int que[10001], head, tail; scanf_s(%d %d, n, m); for (i 1;i n;i) for (j 1;j n;j) if (i j) e[i][j] 0; else e[i][j] 99999999; for (i 1;i m;i) { scanf_s(%d %d, a, b); e[a][b] 1; e[b][a] 1; } head 1; tail 1; que[tail] 1; tail; book[1] 1; while (head tail) { cur que[head]; for (i 1;i n;i) { if (e[cur][i] 1 book[i] 0) { que[tail] i; tail; book[i] 1; } if (tail n) { break; } } head; } for (i 1;i tail;i) { printf(%d , que[i]); }*/// int i, j, m, a, b, c;//scanf_s(%d %d, n, m);//for (i 1;i n;i)// for (j 1;j n;j)// if (i j) e[i][j] 0;// else e[i][j] 99999999;//for (i 1;i m;i)//{// scanf_s(%d %d %d, a, b, c);// e[a][b] c;// e[b][a] c;// //此处有方向 ,或者没有方向有不同答案//}//book[1] 1;//dfs(1, 0);//printf(%d\n, min);structnoteque[2501];inte[51][51]{0},book[51]{0};inthead,tail;inti,j,n,m,a,b,cur,start,end,flag0;scanf_s(%d %d %d %d,n,m,start,end);for(i1;in;i)for(j1;jm;j)if(ij)e[i][j]0;elsee[i][j]99999999;for(i1;im;i){scanf_s(%d %d,a,b);e[a][b]1;e[b][a]1;}head1;tail1;que[tail].x1;que[tail].s0;tail;book[start]1;while(headtail){curque[head].x;for(j1;jn;j){if(e[cur][j]1book[j]0){que[tail].xj;que[tail].sque[head].s1;tail;book[j]1;}}if(que[tail].xend){flag1;break;}if(flag1)break;head;}printf(%d,que[tail-1].s);return0;}知识点总结1. 广度优先搜索 (BFS)核心思想从起点开始逐层向外探索所有相邻节点使用队列Queue数据结构实现“先进先出”的访问顺序。应用场景迷宫/地图探索计算可到达的区域面积如“计算某个区块面积”。最短路径无权图寻找从起点到终点的最少步数如最后一段寻找start到end的最短路径。状态搜索在“炸弹人”游戏中寻找能消灭最多敌人的位置通过BFS遍历所有可放置位置并评估。2. 深度优先搜索 (DFS)核心思想沿着一条路径深入探索到底直到无法继续再回溯探索其他分支通常使用递归或栈实现。应用场景图的遍历访问图中所有连通节点。路径搜索与优化在加权图中寻找特定路径如城市间最短路径并通过剪枝if (dis min) return;优化搜索过程。3. 队列 (Queue) 的手动实现使用结构体数组如struct note que[2501]和头尾指针head,tail来模拟队列操作这是C语言中实现BFS的标准方式。操作入队数据存入que[tail]然后tail。出队从que[head]读取数据然后head。判断空head tail。4. 图的表示与遍历邻接矩阵使用二维数组e[101][101]表示图e[i][j]的值表示顶点i到j的边权1表示连通99999999表示不连通0表示自环。遍历关键需要book数组或visited数组来标记节点是否已被访问防止重复访问。5. 迷宫/矩阵类问题的通用处理模式方向数组int next[4][2] { {0,1},{1,0},{0,-1},{-1,0} }代表了上、下、左、右四个方向的坐标变化是处理网格移动的通用技巧。边界检查在移动新坐标(tx, ty)后必须检查是否越界如tx0 || txn-1。状态检查判断新位置是否可通行如a[tx][ty] .或a[tx][ty] 0以及是否已访问book[tx][ty] 0。6. 算法思想与优化剪枝在DFS求最短路径时如果当前路径长度dis已经超过已知最短路径min则立即返回减少不必要的搜索。打擂台法在搜索过程中通过比较并更新最大值如max和对应的mx, my来找到最优解。总结代码片段是算法学习的经典实践涵盖了从基础数据结构队列到核心算法BFS、DFS的应用并涉及了图论和网格搜索等常见问题模型。这些是解决许多编程竞赛和面试中算法问题的基石。