㈠ c语言对于用bfs求最短路径的同时，如何记录路径
比如地图为二维数组map[n][m],记录起点到每个点的最短路径(这个bfs得到),那么可以从终点倒推,即若终点为x1,y1,dist[x1][y1]=d,(xi ,yi)为与(x1,y1)相连的点,若dist[xi][yi]==d-1,那么可以从(xi,yi)走到(x1,y1),然后继续找下去,直到找到起点.可以dfs实现.
㈡ 广度优先搜索C语言算法
它没有固定的写法， 但是大框都差不多， 一定要使用队列， 因为队列的存在可以维护程序按照广度优先的方式进行搜索。即层次遍历
可以给你一份我作过的一个题的代码，大体上就是这个样子
/****************************************************\
*
* Title : Rescue
* From : HDU 1242
* AC Time : 2012.01.12
* Type : 广度优先搜索求最短步数
* Method :从目标结点向回搜索，初始结点有多个
*
\****************************************************/
#include <stdio.h>
#include <string.h>
#define DATASIZE 201
#define QUEUESIZE 65536
typedef struct
{
int x,y;
}CPOINT;
int bfs(char map[][DATASIZE], int n, int m, CPOINT cpa);
int direction[][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int main(void)
{
int m,n,i,j,res;
CPOINT cpa;
char map[DATASIZE][DATASIZE];
freopen("c:\\in.data","r",stdin);
while(scanf("%d%d%*c",&n,&m) != EOF) {
for(i = 0 ; i < n ; i++) {
gets(map[i]);
for(j = 0 ; j < m ; j++) {
if(map[i][j] == 'a') {
cpa.x = i;
cpa.y = j;
}
}
}
res = bfs(map, n, m, cpa);
if(res) {
printf("%d\n",res);
} else {
printf("Poor ANGEL has to stay in the prison all his life.\n");
}
}
return 0;
}
int bfs(char map[][DATASIZE], int n, int m, CPOINT cpa)
{
CPOINT q[QUEUESIZE],u,np;
int vis[DATASIZE][DATASIZE],step[DATASIZE][DATASIZE],i,front,rear,res;
memset(q, 0, sizeof(q));
memset(vis, 0, sizeof(vis));
memset(step, 0, sizeof(step));
front = rear = res = 0;
q[rear++] = cpa;
vis[cpa.x][cpa.y] = 1;
step[cpa.x][cpa.y] = 0;
while(front <= rear) {
u = q[front++];
if(map[u.x][u.y] == 'r') {
res = step[u.x][u.y];
break;
}
for(i = 0 ; i < 4; i++) {
np.x = u.x + direction[i][0];
np.y = u.y + direction[i][1];
if(np.x >= 0 && np.x < n && np.y >= 0 && np.y < m && !vis[np.x][np.y] && map[np.x][np.y] != '#' ) {
vis[np.x][np.y] = 1;
q[rear++] = np;
step[np.x][np.y] = step[u.x][u.y] + 1;
if(map[np.x][np.y] == 'x') {
++step[np.x][np.y];
}
}
}
}
return res;
}
㈢ C语言编写程序实现图的遍历操作
楼主你好，下面是源程序！
/*/////////////////////////////////////////////////////////////*/
/* 图的深度优先遍历 */
/*/////////////////////////////////////////////////////////////*/
#include <stdlib.h>
#include <stdio.h>
struct node /* 图顶点结构定义 */
{
int vertex; /* 顶点数据信息 */
struct node *nextnode; /* 指下一顶点的指标 */
};
typedef struct node *graph; /* 图形的结构新型态 */
struct node head[9]; /* 图形顶点数组 */
int visited[9]; /* 遍历标记数组 */
/********************根据已有的信息建立邻接表********************/
void creategraph(int node[20][2],int num)/*num指的是图的边数*/
{
graph newnode; /*指向新节点的指针定义*/
graph ptr;
int from; /* 边的起点 */
int to; /* 边的终点 */
int i;
for ( i = 0; i < num; i++ ) /* 读取边线信息，插入邻接表*/
{
from = node[i][0]; /* 边线的起点 */
to = node[i][1]; /* 边线的终点 */
/* 建立新顶点 */
newnode = ( graph ) malloc(sizeof(struct node));
newnode->vertex = to; /* 建立顶点内容 */
newnode->nextnode = NULL; /* 设定指标初值 */
ptr = &(head[from]); /* 顶点位置 */
while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */
ptr = ptr->nextnode; /* 下一个顶点 */
ptr->nextnode = newnode; /* 插入节点 */
}
}
/********************** 图的深度优先搜寻法********************/
void dfs(int current)
{
graph ptr;
visited[current] = 1; /* 记录已遍历过 */
printf("vertex[%d]\n",current); /* 输出遍历顶点值 */
ptr = head[current].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
if ( visited[ptr->vertex] == 0 ) /* 如过没遍历过 */
dfs(ptr->vertex); /* 递回遍历呼叫 */
ptr = ptr->nextnode; /* 下一个顶点 */
}
}
/****************************** 主程序******************************/
void main()
{
graph ptr;
int node[20][2] = { {1, 2}, {2, 1}, /* 边线数组 */
{1, 3}, {3, 1},
{1, 4}, {4, 1},
{2, 5}, {5, 2},
{2, 6}, {6, 2},
{3, 7}, {7, 3},
{4, 7}, {4, 4},
{5, 8}, {8, 5},
{6, 7}, {7, 6},
{7, 8}, {8, 7} };
int i;
clrscr();
for ( i = 1; i <= 8; i++ ) /* 顶点数组初始化 */
{
head[i].vertex = i; /* 设定顶点值 */
head[i].nextnode = NULL; /* 指针为空 */
visited[i] = 0; /* 设定遍历初始标志 */
}
creategraph(node,20); /* 建立邻接表 */
printf("Content of the gragh's ADlist is:\n");
for ( i = 1; i <= 8; i++ )
{
printf("vertex%d ->",head[i].vertex); /* 顶点值 */
ptr = head[i].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
printf(" %d ",ptr->vertex); /* 印出顶点内容 */
ptr = ptr->nextnode; /* 下一个顶点 */
}
printf("\n"); /* 换行 */
}
printf("\nThe end of the dfs are:\n");
dfs(1); /* 打印输出遍历过程 */
printf("\n"); /* 换行 */
puts(" Press any key to quit...");
getch();
}
/*//////////////////////////////////////////*/
/* 图形的广度优先搜寻法 */
/* ///////////////////////////////////////*/
#include <stdlib.h>
#include <stdio.h>
#define MAXQUEUE 10 /* 队列的最大容量 */
struct node /* 图的顶点结构定义 */
{
int vertex;
struct node *nextnode;
};
typedef struct node *graph; /* 图的结构指针 */
struct node head[9]; /* 图的顶点数组 */
int visited[9]; /* 遍历标记数组 */
int queue[MAXQUEUE]; /* 定义序列数组 */
int front = -1; /* 序列前端 */
int rear = -1; /* 序列后端 */
/***********************二维数组向邻接表的转化****************************/
void creategraph(int node[20][2],int num)
{
graph newnode; /* 顶点指针 */
graph ptr;
int from; /* 边起点 */
int to; /* 边终点 */
int i;
for ( i = 0; i < num; i++ ) /* 第i条边的信息处理 */
{
from = node[i][0]; /* 边的起点 */
to = node[i][1]; /* 边的终点 */
/* 建立新顶点 */
newnode = ( graph ) malloc(sizeof(struct node));
newnode->vertex = to; /* 顶点内容 */
newnode->nextnode = NULL; /* 设定指针初值 */
ptr = &(head[from]); /* 顶点位置 */
while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */
ptr = ptr->nextnode; /* 下一个顶点 */
ptr->nextnode = newnode; /* 插入第i个节点的链表尾部 */
}
}
/************************ 数值入队列************************************/
int enqueue(int value)
{
if ( rear >= MAXQUEUE ) /* 检查伫列是否全满 */
return -1; /* 无法存入 */
rear++; /* 后端指标往前移 */
queue[rear] = value; /* 存入伫列 */
}
/************************* 数值出队列*********************************/
int dequeue()
{
if ( front == rear ) /* 队列是否为空 */
return -1; /* 为空，无法取出 */
front++; /* 前端指标往前移 */
return queue[front]; /* 从队列中取出信息 */
}
/*********************** 图形的广度优先遍历************************/
void bfs(int current)
{
graph ptr;
/* 处理第一个顶点 */
enqueue(current); /* 将顶点存入队列 */
visited[current] = 1; /* 已遍历过记录标志置疑1*/
printf(" Vertex[%d]\n",current); /* 打印输出遍历顶点值 */
while ( front != rear ) /* 队列是否为空 */
{
current = dequeue(); /* 将顶点从队列列取出 */
ptr = head[current].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
if ( visited[ptr->vertex] == 0 ) /*顶点没有遍历过*/
{
enqueue(ptr->vertex); /* 奖定点放入队列 */
visited[ptr->vertex] = 1; /* 置遍历标记为1 */
printf(" Vertex[%d]\n",ptr->vertex);/* 印出遍历顶点值 */
}
ptr = ptr->nextnode; /* 下一个顶点 */
}
}
}
/*********************** 主程序 ************************************/
/*********************************************************************/
void main()
{
graph ptr;
int node[20][2] = { {1, 2}, {2, 1}, /* 边信息数组 */
{6, 3}, {3, 6},
{2, 4}, {4, 2},
{1, 5}, {5, 1},
{3, 7}, {7, 3},
{1, 7}, {7, 1},
{4, 8}, {8, 4},
{5, 8}, {8, 5},
{2, 8}, {8, 2},
{7, 8}, {8, 7} };
int i;
clrscr();
puts("This is an example of Width Preferred Traverse of Gragh.\n");
for ( i = 1; i <= 8; i++ ) /*顶点结构数组初始化*/
{
head[i].vertex = i;
head[i].nextnode = NULL;
visited[i] = 0;
}
creategraph(node,20); /* 图信息转换，邻接表的建立 */
printf("The content of the graph's allist is:\n");
for ( i = 1; i <= 8; i++ )
{
printf(" vertex%d =>",head[i].vertex); /* 顶点值 */
ptr = head[i].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
printf(" %d ",ptr->vertex); /* 打印输出顶点内容 */
ptr = ptr->nextnode; /* 下一个顶点 */
}
printf("\n"); /* 换行 */
}
printf("The contents of BFS are:\n");
bfs(1); /* 打印输出遍历过程 */
printf("\n"); /* 换行 */
puts(" Press any key to quit...");
getch();
}
㈣ 关于C语言的
//现写了一个，楼主试试，自信楼主会满意的，嘿嘿
#include <stdio.h>
#include <string.h>
struct Graph {
static const int maxv = 1000 , maxe = 500000 ;
int V ;
int mat[maxv][maxv] ;
int adj[maxv][maxv] , szadj[maxv] ;
bool input() {
bool r = (scanf("%d" , &V) == 1) ;
for(int i = 0 ; i < V ; i++) {
for(int j = 0 ; j < V ; j++) {
r = r && (scanf("%d" , &mat[i][j]) == 1) ;
}
}
return r ;
}
bool has_arc_in[maxv] ;
void getAdjGraph() {
memset(has_arc_in , false , sizeof(has_arc_in)) ;
memset(szadj , 0 , sizeof(szadj)) ;
for(int i = 0 ; i < V ; i++) {
printf("node %d 's adj nodes :") ;
for(int j = 0 ; j < V ; j++) {
if(mat[i][j] > 0) {
adj[i][szadj[i]++] = j ;
has_arc_in[j] = true ;
printf("%d " , j) ;
}
}
printf("\n") ;
}
}
int que[maxv] ;
bool vis[maxv] ;
void bfs() {
memset(vis , false , sizeof vis) ;
int t = 0 ;
for(int i = 0 ; i < V ; i++) {
if(has_arc_in[i] == false) {
que[t++] = i ;
vis[i] = true ;
printf("node %d in queue ; \n" , i) ;
}
}
for(int h = 0 ; h < t ; h++) {
int now = que[h] ;
printf("node %d out queue ;\n" , now) ;
for(int i = 0 ; i < szadj[now] ; i++) {
int next = adj[now][i] ;
if(! vis[next]) {
que[t++] = next ;
vis[next] = true ;
printf("node %d in queue ;\n" , next) ;
}
}
}
}
} ;
Graph g ;
int main() {
while(g.input()){
g.getAdjGraph() ;
g.bfs() ;
}
return 0 ;
}
㈤ C语言算法BFS+HASH是什么
就是 康托hash判重 P1029 的所谓的hash就是 康托展开（作用是判重）目标状态就8种
276951438
294753618
438951276
492357816
618753294
672159834
816357492
834159672
由这八个BFS扩展，总共362880种状态，共12种交换方法。 9 的全排列有 三十多万 , 利用 康托 判断出 当前搜索到的 序列 是这 三十多万个排列方式中的第几个, 以此来判重......
康托展开:
{1,2,3,4,...,n}表示1,2,3,...,n的排列如 {1,2,3} 按从小到大排列一共6个 123 132 213 231 312 321代表的数字 1 2 3 4 5 6 也就是把10进制数与一个排列对应起来。他们间的对应关系可由康托展开来找到。 如我想知道321是{1,2,3}中第几个大的数可以这样考虑 第一位是3，当第一位的数小于3时，那排列数小于321 如 123 213 小于3的数有1，2 所以有2*2!个 再看小于第二位2的 小于2的数只有一个就是1 所以有1*1!=1 所以小于321的{1,2,3}排列数有2*2!+1*1!=5个所以321是第6个大的数。 2*2!+1*1!是康托展开 再举个例子 1324是{1,2,3,4}排列数中第几个大的数 第一位是1小于1的数没有，是0个 0*3! 第二位是3小于3的数有1，2但1已经在第一位了所以只有一个数2 1*2! 第三位是2小于2的数是1，但1在第一位所以有0个数 0*1! 所以比1324小的排列有0*3!+1*2!+0*1!=2个 1324是第三个大数。
㈥ c语言题目。这题是不是用bfs怎么写
可以用bfs
具体代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#defineMAXN1010
intdis[MAXN][MAXN];
intque[MAXN*MAXN];
intdir[4][2]={0,1,0,-1,1,0,-1,0};
intT,N,M,SX,SY,FX,FY;
intjudge(intx,inty){
if(x<1||x>N||y<1||y>M)
return0;
return1;
}
intbfs(){
inttail=0,front=0,curx,cury,i,nxtx,nxty;
dis[SX][SY]=1;
que[front++]=(SX-1)*M+(SY-1);
while(tail<front){
curx=que[tail]/M+1;
cury=que[tail++]%M+1;
for(i=0;i<4;i++){
nxtx=curx+dir[i][0];
nxty=cury+dir[i][1];
if(judge(nxtx,nxty)==0)
continue;
if(dis[nxtx][nxty]!=-1)
continue;
dis[nxtx][nxty]=dis[curx][cury]+1;
que[front++]=(nxtx-1)*M+(nxty-1);
if(nxtx==FX&&nxty==FY)
returndis[nxtx][nxty];
}
}
return-1;
}
intmain(){
inti,x,y,ans;
while(~scanf("%d%d%d",&N,&M,&T)){
memset(dis,-1,sizeof(dis));
scanf("%d%d%d%d",&SX,&SY,&FX,&FY);
for(i=0;i<T;i++){
scanf("%d%d",&x,&y);
dis[x][y]=-2;
}
ans=bfs();
printf("%d ",ans);
}
return0;
}
㈦ 数据结构C语言版 图的广度优先遍历和深度优先遍历 急急急 会查重
#include<iostream>
#include<string>
#include<queue>
usingnamespacestd;
intFirstAdjVex(intv);
intNextAdjVex(intv,intw);
voidDFS(intv);//从顶点v开始对图做深度优先遍历,v是顶点数组的下标
voidBFS(intv);//从顶点v开始对图做广度优先遍历，v是顶点数组的下标
intfind(stringa,intn);
intvisited[10]={0};
inttraver[10][10]={0};
stringname[10];
intmain()
{
intn,m,i,j,k;
stringa,b;
//freopen("Traver.txt","r",stdin);
cin>>n;
cin>>m;
for(i=0;i<n;i++)
{
cin>>a;
name[i]=a;
}
for(i=0;i<m;i++){
cin>>a;
cin>>b;
j=find(a,n);
k=find(b,n);
traver[j][k]=1;
traver[k][j]=1;
}
for(i=0;i<n;i++){
if(visited[i]==0)
DFS(i);
}
cout<<" ";
for(i=0;i<n;i++){
visited[i]=0;
}
for(i=0;i<n;i++){
if(visited[i]==0)
BFS(i);
}
cout<<" ";
return0;
}
//寻找函数
intfind(stringa,intn){
inti;
for(i=0;i<n;i++){
if(a==name[i])
returni;
}
return-1;
}
intFirstAdjVex(intv)
{
inti;
//从编号大的邻接点开始访问
for(i=9;i>=0;i--)
{
if(traver[v][i]==1)
returni;
}
return-1;
}
intNextAdjVex(intv,intw)
{
inti;
for(i=w-1;i>=0;i--)
{
if(traver[v][i]==1)
returni;
}
return-1;
}
voidDFS(intv)
{
intw;
//访问顶点v(输出顶点v的名字)
cout<<name[v]<<"";
visited[v]=1;
//找到顶点v的第一个邻接点w
for(w=FirstAdjVex(v);w>=0;w=NextAdjVex(v,w))
{
//如果w没有访问过，对顶点w做深度优先搜索
if(visited[w]==0)
DFS(w);
}
}
voidBFS(intv)//从顶点v开始对图做广度优先遍历，v是顶点数组的下标
{
intw,u;
queue<int>myqueue;//定义一个队列，元素是顶点的下标
//把顶点v入队
myqueue.push(v);
cout<<name[v]<<"";
visited[v]=1;
while(!myqueue.empty())
{//当队列不为空时进入循环
//取队头元素
u=myqueue.front();
//队头元素出队
myqueue.pop();
//把u的所有邻接点入队
w=FirstAdjVex(u);
while(w>=0)
{
if(visited[w]==0)
{
//访问w
cout<<name[w]<<"";
visited[w]=1;
//w入队
myqueue.push(w);
}
w=NextAdjVex(u,w);
}
}
}
㈧ 求解c语言一下代码详解
这个是 C++ 代码是肯定的了。
有些库函数没见过，从流程和字面看有些像验证码拉扯函数。
因为缺少背景资料，就详解不了了。
㈨ c语言BFS、DFS函数代码
这个没有固定的形式
根据具体的情况来写
关键是思想
bfs是先扩展节点再增加深度
dfs是先增加深度,到底后返回再扩展节点
一个是使用大量空间 另一个则是遍历所有路径,相对的更费时间
㈩ 用C语言编写三个算法，BFS或DFS，爬山算法，遗传算法实现八皇后问题
网络算法名，加上八皇后
比如
BFS 八皇后问题 C语言。
或者
遗传算法 八皇后问题 C语言
然后根据搜索结果 就可以得到算法和代码了。