㈠ 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語言
然後根據搜索結果 就可以得到演算法和代碼了。