『壹』 廣度優先搜索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;
}
『貳』 bfs演算法是什麼
bfs演算法寬度優先搜索演算法（又稱廣度優先搜索）是最簡便的圖的搜索演算法之一，這一演算法也是很多重要的圖的演算法的原型。Dijkstra單源最短路徑演算法和Prim最小生成樹演算法都採用了和寬度優先搜索類似的思想。其別名又叫BFS，屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。
與深度優先搜索的對比
1、把根節點壓入棧中。
2、每次從棧中彈出一個元素，搜索所有在它下一級的元素，把這些元素壓入棧中。並把這個元素記為它下一級元素的前驅。
3、找到所要找的元素時結束程序。
4、如果遍歷整個樹還沒有找到，結束程序。
『叄』 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是第三個大數。
『肆』 bfs演算法是什麼
廣度優先搜索演算法（英語：Breadth-First Search，縮寫為BFS），又譯作寬度優先搜索，或橫向優先搜索，是一種圖形搜索演算法。
簡單的說，BFS是從根節點開始，沿著樹的寬度遍歷樹的節點。如果所有節點均被訪問，則演算法中止。廣度優先搜索的實現一般採用open-closed表。
作法
BFS是一種暴力搜索演算法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能地址，徹底地搜索整張圖，直到找到結果為止。BFS並不使用經驗法則演算法。
從演算法的觀點，所有因為展開節點而得到的子節點都會被加進一個先進先出的隊列中。
一般的實現里，其鄰居節點尚未被檢驗過的節點會被放置在一個被稱為open的容器中（例如隊列或是鏈表），而被檢驗過的節點則被放置在被稱為closed的容器中。
(4)c語言bfs演算法原理擴展閱讀：
廣度優先搜索演算法的應用
廣度優先搜索演算法能用來解決圖論中的許多問題，例如：
1、查找圖中所有連接組件（ConnectedComponent）。一個連接組件是圖中的最大相連子圖。
2、查找連接組件中的所有節點。
3、查找非加權圖中任兩點的最短路徑。
4、測試一圖是否為二分圖。
5、（Reverse）Cuthill–McKee演算法
『伍』 關於BF演算法的C語言實現
我修改的程序都是把S[0] T[0]轉換為strlen(S) strlen(T)函數來實現的
為什麼不把strlen(S),strlen(T)分別賦予S[0],T[0],害怕覆蓋原來的數據嗎?沒有必要,他們原本就是來存儲這個數據的,君不見,它們都不參與匹配!他們的初始化應該在這個函數之外完成,在每次數組長度改變後,就及時設置,換句話說,在調用這個函數之前,應該保證他們已經設置正確,
在列印時,應該從第二個元素S[1]或T[1]開始,因為S[0],T[0]不再是數組的實際內容
不知道我有沒有表述清楚,
一般,數組的第一個元素存放實際的內容,而你這里並不是這樣,數組的第一個元素不再是數組的實際內容,而是數組長度
==================================================================
補充;
比較大小時S[0]的值不就變成了整形的ASCII碼值了么？
1.整數就是整數,沒有ASCII碼,ASCII碼是針對字元的
2.在C中,整數賦予字元變數是合法的
2.在C中,字元與整數的關系運算也是合法的,當你要把一個位元組的數解釋成字元的時候,它就是字元,可他存儲的還是數啊,就把它當整數用吧,畢竟我們沒有打算列印它,當然它能表示的整數太少了,所以數組長度受到限制
如果你要以字元顯示它,那它當然是那個整數所對應的字元,如果那是可列印字元的話