本篇文章给大家谈谈dfs迷宫c语言，以及dfs C语言对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
1、用dfs走迷宫 求到出口的最短路径怎么做？？2、C语言用图的广度优先遍历做漫步迷宫问题3、数据结构迷宫问题（c语言）4、dfs怎么用，求C语言版的，麻烦举个例子5、求解c语言一递归迷宫问题6、关于C++迷宫问题，寻找一条通路穿越迷宫（找到一条即可）。要求写出一个递归程序来穿越迷宫。
用dfs走迷宫 求到出口的最短路径怎么做？？
每次到达x==ny==m（（n,m）是终点的坐标）的时候，将目前的值与之前算出来的最小路径进行比较，让它等于小的那个，搜索玩后就可以输出最小值了。（似乎发现你程序里面map[i][j]=1后return之后没有进行map[i][j]=0的操作，这样会挂的…）
C语言用图的广度优先遍历做漫步迷宫问题
这是我们老师给我们上数据结构课的课件
#include “stdio.h”
typedef int datatype; /*假定线性表元素的类型为整型*/
#define maxsize 1024 /*假定线性表的最大长度为1024*/
# define n 100 /* 图的顶点最大个数 */
typedef char VEXTYPE; /* 顶点的数据类型 */
typedef float ADJTYPE; /* 权值类型 */
typedef struct
{ VEXTYPE vexs[n] ; /* 顶点信息数组 */
ADJTYPE arcs[n][n] ; /* 边权数组 */
int num ; /* 顶点的实际个数 */
}GRAPH;
/***********************1。置空图**********************/
void GraphInit(GRAPH *L)
{
L-num=0;
}
/***********************2。求结点数**********************/
int GraphVexs(GRAPH *L)
{
return(L-num);
}
/***********************3。创建图**********************/
void GraphCreate(GRAPH *L)
{
int i,j;
GraphInit(L);
printf(“请输入顶点数目：”);
scanf(“%d”,L-num);
printf(“请输入各顶点的信息(单个符号）：”);
for(i=0;iL-num;i++)
{
fflush(stdin);
scanf(“%c”,L-vexs[i]);
}
printf(“请输入边权矩阵的信息：”);
for(i=0;iL-num;i++)
{
for(j=0;jL-num;j++)
{
scanf(“%f”,L-arcs[i][j]);
}
}
printf(“图已经创建完毕！”);
}
/***********************4。图的输出**********************/
void GraphOut(GRAPH L)
{
int i,j;
printf(“\n图的顶点数目为：%d”,L.num);
printf(“\n图的各顶点的信息为：\n”);
for(i=0;iL.num;i++)
printf(“%c “,L.vexs[i]);
printf(“\n图的边权矩阵的信息为：\n”);
for(i=0;iL.num;i++)
{
for(j=0;jL.num;j++)
{
printf(“%6.2f “,L.arcs[i][j]);
}
printf(“\n”);
}
printf(“图已经输出完毕！”);
}
/***********************5。图的深度周游**********************/
void DFS(GRAPH g,int qidian,int mark[])
//从第qidian个点出发深度优先周游图g中能访问的各个顶点
{
int v1;
mark[qidian]=1;
printf(“%c “,g.vexs[qidian]);
for(v1=0;v1g.num;v1++)
{
if(g.arcs[qidian][v1]!=0mark[v1]==0)
DFS(g,v1,mark);
}
}
/***********************6。图的深度周游**********************/
void GraphDFS(GRAPH g)
//深度优先周游图g中能访问的各个顶点
{
int qidian,v,v1,mark[maxsize];
printf(“\n深度周游：”);
printf(“\n请输入起点的下标：”);
scanf(“%d”,qidian);
for(v=0;vg.num;v++)
{
mark[v]=0;
}
for(v=qidian;vg.num+qidian;v++)
{
//printf(“v=%d “,v);
v1=v%g.num;
if(mark[v1]==0)
DFS(g,v1,mark);
}
}
typedef int DATATYPE; //队列元素的数据类型
typedef struct
{
DATATYPE data[maxsize]; //队中元素
int front,rear; //队头元素下标、队尾元素后面位置的下标
} SEQQUEUE;
/*****************************************************************************/
void QueueInit(SEQQUEUE *sq)
//将顺序循环队列sq置空（初始化）
{
sq-front=0;
sq-rear=0;
}
/*****************************************************************************/
int QueueIsEmpty(SEQQUEUE sq)
//如果顺序循环队列sq为空，成功返回1，否则返回0
{
if (sq.rear==sq.front)
return(1);
else
return(0);
}
/*****************************************************************************/
int QueueFront(SEQQUEUE sq,DATATYPE *e)
//将顺序循环队列sq的队头元素保存到e所指地址，成功返回1，失败返回0
{
if (QueueIsEmpty(sq))
else
}
/*****************************************************************************/
int QueueIn (SEQQUEUE *sq,DATATYPE x)
//将元素x入队列sq的队尾，成功返回1，失败返回0
{
if (sq-front==(sq-rear+1)%maxsize)
{
printf(“queue is full!\n”);
return 0;
}
else
{
sq-data[sq-rear]=x;
sq-rear=(sq-rear+1)%maxsize;
return(1);
}
}
/*****************************************************************************/
int QueueOut(SEQQUEUE *sq)
//将队列sq队首元素出队列，成功返回1,失败返回0
{
if (QueueIsEmpty(*sq))
{
printf(“queue is empty!\n”);
return 0;
}
else
{
sq-front=(sq-front+1)%maxsize;
return 1;
}
}
/***********************7。图的广度周游**********************/
void BFS(GRAPH g,int v,int mark[])
//从v出发广度优先周游图g中能访问的各个顶点
{
int v1,v2;
SEQQUEUE q;
QueueInit(q);
QueueIn(q,v);
mark[v]=1;
printf(“%c “,g.vexs[v]);
while(QueueIsEmpty(q)==0)
{
QueueFront(q,v1);
QueueOut(q);
for(v2=0;v2g.num;v2++)
{
if(g.arcs[v1][v2]!=0mark[v2]==0)
{
QueueIn(q,v2);
mark[v2]=1;
printf(“%c “,g.vexs[v2]);
}
}
}
}
/***********************8。图的广度周游**********************/
void GraphBFS(GRAPH g)
//深度优先周游图g中能访问的各个顶点
{
int qidian,v,v1,mark[maxsize];
printf(“\n广度周游：”);
printf(“\n请输入起点的下标：”);
scanf(“%d”,qidian);
for(v=0;vg.num;v++)
{
mark[v]=0;
}
for(v=qidian;vg.num+qidian;v++)
{
v1=v%g.num;
if(mark[v1]==0)
BFS(g,v1,mark);
}
}
/***********************主函数**********************/
void main()
{
GRAPH tu;
GraphCreate(tu);
GraphOut(tu);
GraphDFS(tu);
GraphBFS(tu);
}
数据结构迷宫问题（c语言）
#includestdio.h
#includestring.h
#includestdlib.h
#includetime.h
int m,n,num,map[101][101],f[101][101],a[101],b[101],d[2][4]={0,-1,0,1,-1,0,1,0},ans,flag;
void maze()
{
int i,j;
time_t t;
srand(time(t));
for(i=0;im;i++)
for(j=0;jn;j++)
{
map[i][j]=rand()%2;
if(map[i][j])
num++;
}
if(numm*n/2)
{
for(i=0;im;i++)
for(j=0;jn;j++)
if(!map[i][j])
map[i][j]+=rand()%2;
}
map[0][0]=1;
map[m-1][n-1]=1;
}
void print()
{
int i,j;
for(i=0;im;i++)
for(j=0;jn;j++)
{
printf(“%d “,map[i][j]);
if(j==n-1)puts(“”);
}
}
void dfs(int x,int y)
{
int i,tx,ty;
if(!flag)
return;
for(i=0;i4;i++)
{
tx=x+d[0][i];
ty=y+d[1][i];
if(!f[tx][ty]tx=0ty=0txmtynmap[tx][ty])
{
f[tx][ty]=1;
a[ans]=tx;
b[ans++]=ty;
if(tx+ty==0)
{
printf(“(%d,%d)\n”,m,n);
for(flag=i=0;ians;i++)
printf(“(%d,%d)\n”,a[i]+1,b[i]+1);
return;
}
dfs(tx,ty);
f[tx][ty]=0;
ans–;
}
}
}
int main()
{
while(scanf(“%d%d”,m,n),m+n)
{
memset(f,0,sizeof(f));
num=ans=0;
flag=1;
maze();
print();
dfs(m-1,n-1);
if(flag)
puts(“There is no path”);
}
return 0;
}
dfs怎么用，求C语言版的，麻烦举个例子
一般的DFS算法：
typedef struct
{
int all;
int recorder[ALLIN][ALLIN];
}Matrix;
int visited[ALLIN];
void DFS(Matrix data, int i,int num)
{
int *p;
printf(“%d”,i);
visited[i]=1;
p=data.recorder[i];
for(int j=0;jnum;j++)
{
if(*(p+j)==1 !visited[j])
DFS(data,j,num);
}
}
求解c语言一递归迷宫问题
给你给伪算法：（设坐标为x,y,坐标向右和下延生。）
函数：
｛
判断当前是不是（7,7)，如果是，表示走出迷宫。打印轨迹
1 尝试往左先走一步（x-1，如果x小于0，或者对应位置标识为阻塞）
2 1如果成功，用本函数递归调用左走一步的坐标，并记下当前位置到轨迹列表。
3 尝试往前先走一步（y+1，如果y小于0，或者对应位置标识为阻塞）
4 3如果成功，用本函数递归调用前走一步的坐标,并记下当前位置到轨迹列表。
5 尝试往右先走一步（x+1，如果x小于0，或者对应位置标识为阻塞）
6 5如果成功，用本函数递归调用前走一步的坐标,并记下当前位置到轨迹列表。
如果是（0，0），表示没有合适的路径可走出迷宫。
如果不是（0，0），将轨迹列表最后一位弹出。
｝
关于C++迷宫问题，寻找一条通路穿越迷宫（找到一条即可）。要求写出一个递归程序来穿越迷宫。
题目有问题：如何指定迷宫的起点和终点。
我这里假设迷宫某个边界位置是起点，(x, y)是否是终点要用GotGoal(x, y)函数判断。
核心函数
void DFS(char *m, int height, int width, int x, int y, int now_dir)
这里m是一个一维数组，表示迷宫。格点x, y的信息是m[y * width + x]
比如3行4列的迷宫
####
#…
..##
在m里就是#####…..##，每一行紧接着上一行。
height 迷宫高度
width 迷宫宽度
x是当前位置横坐标。右边是正方向。
y是当前位置纵坐标。下方是正方向。
now_dir是是当前的方向。你需要给上下左右4个方向规定一个编号。
比如
int dir_list[4][2] = {
{-1, 0}, // 地图左
{0, -1}, // 地图上
{1, 0}, // 地图右
{0, 1} // 地图下
};
// 第一个数表示恒坐标变化量，第二个数表示纵坐标变化量
那么对于当前方向now_dir，“摸着右手边的墙”的探索方向编号依次是（可以参照上面dir_list的注释来理解）
(now_dir + 1) % 4 当前方向右侧
(now_dir + 0) % 4 当前方向
(now_dir – 1 + 4) % 4 当前方向左侧
(now_dir – 2 + 4) % 4 当前方向反方向（回头）。（这里要+4是为了防止now_dir减去数字后变成负数，负数除以4的余数还是负数）。
使用DFS的方法：
先将地图信息保存到char数组里，作为DFS函数第一参数
将迷宫入口横坐标保存到x参数，纵坐标保存到y参数
将刚进入迷宫的方向的编号（dir_list的第一下标）保存到now_dir
DFS的基本实现（伪代码）
void DFS(char *m, int height, int width, int x, int y, int now_dir)
{
int turn = 0;
int new_dir;
int new_x;
int new_y;
if (GotGoal(x, y) ) // 如果当前位置是终点
return;
m[y * width + x] = ‘X’; // 占据当前位置
PrintMap(m, height, width); // 打印地图当前状态
for (turn = 1; = -2; turn–) // 依次循环4个方向：右、前、左、回头
{
new_dir = (now_dir + turn + 4) % 4; // 计算新方向的编号
new_x = x + dir_list[new_dir][0];
new_y = y + dir_list[new_dir][1]; // 计算出“如果要走新方向，则下一步的位置”
if (new_x 0 || new_x = width)// 如果走出左右边界
continue;
if (new_y 0 || new_y = height) // 如果走出上下边界
continue;
if (‘#’ == m[new_y * width + new_x]) // 如果下一步是是墙
continue;
DFS(m, height, width, new_x, new_y, new_dir);
}
return;
}
注意：
这个问题由于不涉及最短路，而且每走一步都算走过，包括走进了死胡同。因此这个问题完全不需要用递归，实际上程序也不可能回溯，因为每一步都是对的。直接用for或while循环就行了。用递归，当路线比较长时，可能超过操作系统限制而报错。
对于有环路的迷宫，程序会死循环。
如果要判断出死循环的情况，需要一个额外的数组int m_arrived[][4]，保存每个位置的每个方向是否走过。一开始都是0，走过m[i]且方向是dir的时候，m_arrived[i][dir] = 1即可。
有不明白的地方请追问。
dfs迷宫c语言的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于dfs C语言、dfs迷宫c语言的信息别忘了在本站进行查找喔。
微信扫一扫 
支付宝扫一扫 
