深度優(yōu)先搜索- 不撞南墻不回頭
深度優(yōu)先搜索屬于圖算法的一種士修，英文縮寫為DFS即Depth First Search.其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止温兼，而且每個節(jié)點只能訪問一次.
下圖是一個無向圖以舒，如果我們從A點發(fā)起深度優(yōu)先搜索（以下的訪問次序并不是唯一的融师，第二個點既可以是B也可以是C,D）焚虱，則我們可能得到如下的一個訪問過程：A->B->E（沒有路了堰燎！回溯到A)->C->F->H->G->D（沒有路楣责，最終回溯到A,A也沒有未訪問的相鄰節(jié)點，本次搜索結束）.
簡要說明深度優(yōu)先搜索的特點：每次深度優(yōu)先搜索的結果必然是圖的一個連通分量.深度優(yōu)先搜索可以從多點發(fā)起.如果將每個節(jié)點在深度優(yōu)先搜索過程中的"結束時間"排序（具體做法是創(chuàng)建一個list坯台，然后在每個節(jié)點的相鄰節(jié)點都已被訪問的情況下炬丸，將該節(jié)點加入list結尾，然后逆轉(zhuǎn)整個鏈表)蜒蕾，則我們可以得到所謂的"拓撲排序",即topological sort.
題二稠炬、有九張（1-9）的撲克牌，放入九個盒子里面咪啡，使得 _ _ _ + _ _ _ = _ _ _ 成立首启，
現(xiàn)在使用深度優(yōu)先搜索優(yōu)化一下之前的方法，之前使用枚舉算法撤摸，時間復雜度太高
int a[10], book[10], n , total = 0;// C語言全局變量在沒有賦值的時候毅桃，默認為0
void dfsTwo(int step); // 深度優(yōu)先搜索
char* getDateTime(void);
int main(int argc, const char * argv[]) {
char * time = getDateTime();
printf("時間 ====%s \n",time);
dfsTwo(1); // 首先在第一個盒子里面
printf("總共有%d種方法",total/2);
printf("時間 ====%s \n",time);
getchar();
}
void dfsTwo(int step) // 深度優(yōu)先搜索
{
int i = 0;
if (step ==10) { // 如果是第十個個盒子，說明之前的九個盒子里面都是有撲克牌的
// 判斷是否滿足等式 _ _ _ + _ _ _ = _ _ _
if ((100*a[1] + 10*a[2] + a[3])+(100*a[4] + 10*a[5] + a[6])==(100*a[7] + 10*a[8] + a[9]) ) {
// 如果滿足條件准夷， 解加一钥飞，并打印這個解
total ++;
printf("%d%d%d+%d%d%d=%d%d%d \n",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
}
return;
}
// 如果不是第十個盒子，哪應該放那張牌
// 按照 1 - 9 的順序嘗試
for (i = 1; i < 10; i ++) {
// 判斷撲克牌是否在手中
if (book[i] == 0) {
// 開始使用手中的撲克牌
a[step] = i;
book[i] = 1;
// 第step個盒子已經(jīng)放好了撲克牌衫嵌，走到下面一個盒子里面
dfsTwo(step + 1);
book[i] = 0; // 收回手中的牌读宙，才可以繼續(xù)操作
}
}
}
char* getDateTime()
{
static char nowtime[20];
time_t rawtime;
struct tm* ltime;
time(&rawtime);
ltime = localtime(&rawtime);
strftime(nowtime, 20, "%Y-%m-%d %H:%M:%S", ltime);
return nowtime;
}
題三、深度優(yōu)先算法 最短路徑
看下列地圖楔绞，可以的到點a 到點b的最短距離
0 表示空地结闸， 1 表示障礙物 其中 a 和 b 也是在空地里面 ，求a（0酒朵，0） 到 b（3桦锄，2） 的最短距離 這里坐標為 (行，列)
5行 4列
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
int n3 ,m3 ,p3 ,q3,min3 = 99999999;
int a3[51][51], book3[51][51];
void dfsThree(int x,int y, int step);
char* getDateTime(void);
int main(int argc, const char * argv[]) {
int i , j , startX ,startY;
// 讀入n 和 m n為行 m為列
printf("請輸入 行 和列:");
scanf("%d %d",&n3, &m3);
// 讀入迷宮
for (i = 0; i < n3; i ++ ) {
printf("輸入迷宮:\n");
for (j = 0; j < m3; j ++) {
scanf("%d",&a3[i][j]);
}
}
// 讀入 起點 和終點
printf("輸入起點坐標");
scanf("%d%d",&startX,&startY); // 設置起點坐標為 （startX,startY）
printf("輸入終點坐標");
scanf("%d%d",&p3,&q3); // 設置終點坐標為 （p,q）
// 從起點開始搜索
book3[startX][startY] = 1; // 標記起點已經(jīng)在路徑上耻讽，防止再重復行走
dfsThree(startX, startY, 0); // 第一個參數(shù) 為起點x 察纯，第二個為起點y 帕棉，第三個為初始化步數(shù)0
printf("輸出最短步數(shù) 针肥，%d\n",min3);
getchar();
}
// 得到 A點 到b點的最少步數(shù)
void dfsThree(int x,int y, int step) // 深度優(yōu)先搜索
{
int next [4][2] = {
{0,1}, // 向右走
{1,0}, // 向下走
{0,-1}, // 向左走
{-1,0} // 向上走
};
int tx = 0, ty = 0,k;
// 判斷是否達到b點位置
printf("x ==%d y ==%d p3=== %d q3====%d \n",x,y,p3,q3);
if (x == p3 && y == q3) {
// 更新最小步數(shù)
if (step < min3) {
printf("輸出最短步數(shù) 饼记，%d\n",min3);
min3 = step;
}
return;
}
// 枚舉四種走法
for (k = 0; k < 4; k ++) {
// 計算下一個點的坐標
tx = x + next[k][0]; // x = 0 , y = 1 是因為是二維數(shù)組 [4][2] {0,1} 其中下標為0 為x 下標為1的為y。 k 數(shù)組是為長度為4
ty = y + next[k][1];
// 判斷是否越界
if ( tx < 0 || tx > n3 || ty < 0 || ty > m3) {
continue;
}
// 判斷改點是否是障礙物或者是已經(jīng)走過的點
if (a3[tx][ty] == 0 && book3[tx][ty] == 0) { // 0 為空地 1 表示障礙物
// 不是障礙物 或者已經(jīng)走過的點繼續(xù)
book3[tx][ty] = 1; //標記這個點已經(jīng)走過
dfsThree(tx, ty, step + 1);
book3[tx][ty] = 0;
}
}
return;
}
char* getDateTime()
{
static char nowtime[20];
time_t rawtime;
struct tm* ltime;
time(&rawtime);
ltime = localtime(&rawtime);
strftime(nowtime, 20, "%Y-%m-%d %H:%M:%S", ltime);
return nowtime;
}
廣度優(yōu)先搜索 - 層層遞進
廣度優(yōu)先搜索算法(Breadth First Search)慰枕，又稱為"寬度優(yōu)先搜索"或"橫向優(yōu)先搜索"具则，簡稱BFS。
它的思想是：從圖中某頂點v出發(fā)具帮，在訪問了a之后依次訪問a的各個未曾訪問過的鄰接點博肋，然后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使得“先被訪問的頂點的鄰接點先于后被訪問的頂點的鄰接點被訪問蜂厅，直至圖中所有已被訪問的頂點的鄰接點都被訪問到匪凡。如果此時圖中尚有頂點未被訪問，則需要另選一個未曾被訪問過的頂點作為新的起始點掘猿，重復上述過程病游，直至圖中所有頂點都被訪問到為止。
題三稠通、廣度優(yōu)先算法 最短路徑
看下列地圖衬衬，可以的到點a 到點b的最短距離
0 表示空地， 1 表示障礙物 其中 a 和 b 也是在空地里面 改橘，求a（0滋尉，0） 到 b（3，2） 的最短距離 這里坐標為 (行飞主，列)
5行 4列
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
換句話說狮惜，廣度優(yōu)先搜索遍歷圖的過程是以a為起點，由近至遠既棺，依次訪問和va路徑相通且路徑長度為1,2...的頂點讽挟。
1、從 （0丸冕，0）開始搜索耽梅，以a點代替
a 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
-》
2、第二層搜索 從（0胖烛，0）搜索眼姐，右方和下方 以 b點 代替
a b 1 0
b 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
-》
3、第三層搜索 ,（0佩番，1）這個b點右邊是障礙物众旗，無法搜索，可以往下搜索（1趟畏，1）贡歧，（1，0）這個點搜索右方發(fā)現(xiàn)已經(jīng)搜索完成了（每個點需要搜索一次），跳過利朵，搜索（1律想，0）下方的點 （2，0）绍弟，以c代替
a b 1 0
b c 0 0
c 0 1 0
0 1 0 0
0 0 0 1
...
就這樣一直層層搜索直到搜索完成所有到點（3技即，2）的路線，結束搜索,遇到障礙物“1”跳過樟遣，最后變成下面這個地圖
a b 1 f
b c d e
c d 1 f
d 1 h g
e f g 1
完整demo如下
// 廣度優(yōu)化搜索
struct note
{
int x; // 橫坐標
int y; // 縱坐標
int f; // 父親在隊列的的編號 而叼，需要輸出路徑才需要使用
int s; // 步數(shù)
};
char* getDateTime(void);
int main(int argc, const char * argv[]) {
struct note queB[2501]; // 因為地圖大小不會超過 50 * 50 所以 隊列擴展也不會超過2500個
int aB[51][51], bookB[51][51];
// 定義一個表示方向的數(shù)組
int nextB [4][2] = {
{0,1}, // 向右走
{1,0}, // 向下走
{0,-1}, // 向左走
{-1,0} // 向上走
};
int headB ,tailB;
int iB,jB,kB,nB,mB,startX,startY,pB,qB,txB,tyB,flagB;
printf("請輸入行和列：");
scanf("%d %d",&nB,&mB);
for (iB = 0; iB < nB; iB ++) {
printf("輸入當前行地圖");
for (jB = 0; jB < mB; jB++) {
scanf("%d",&aB[iB][jB]);
}
}
printf("輸入開始坐標startX，startY 結束坐標 pB qB");
scanf("%d %d %d %d",&startX,&startY,&pB,&qB);
// 隊列初始化
headB = 0;
tailB = 0;
// 往隊列里面插入迷宮入口坐標
queB[tailB].x = startX;
queB[tailB].y = startY;
queB[tailB].f = 0;
queB[tailB].s = 0;
tailB ++;
bookB[startX][startY] = 1;
flagB = 0;// 標記是否達到目標點豹悬，0表示沒有達到葵陵，1表示已經(jīng)達到了目標點
// 當隊列部位空得時候循環(huán)
while (headB < tailB) {
// 枚舉4個方向
for (kB = 0; kB< 4; kB ++) {
// 計算下一個點的坐標
txB = queB[headB].x + nextB[kB][0];
tyB = queB[headB].y + nextB[kB][1];
// 判斷是否越界
if (txB < 0 || txB > nB || tyB < 0 || tyB > mB ) {
continue;
}
// 判斷是否是障礙物，或者是已經(jīng)走過的路
if (aB[txB][tyB] == 0 && bookB[txB][tyB] == 0) {
// 不是障礙物瞻佛，并且沒有走過的路
// 標記已經(jīng)走過的點埃难，廣度搜索和深度搜索不同，只需要走過一次不需要bookB數(shù)組還原
bookB[txB][tyB] = 0;
// 并且把這個點插入到隊列里面
queB[tailB].x = txB;
queB[tailB].y = tyB;
queB[tailB].f = headB; // 打印路徑需要涤久，因為點事從head里面擴展出來的
queB[tailB].s = queB[headB].s + 1;// 步數(shù)是父親步數(shù)的 + 1
tailB ++;
}
// 如果到達目標點涡尘，停止擴展，任務結束响迂，退出循環(huán)
if (txB == pB && tyB == qB) {
flagB = 1;
break;
}
}
if (flagB == 1) {
break;
}
headB ++; // 當一個點擴展結束之后考抄，需要下一個點開始擴展
}
// 打印隊列中末尾最后的一個點的步數(shù)
// 注意 tail 是指向隊尾 的下一個位置，這里需要減一
// for (iB = 0; iB < tailB; iB ++) {
// printf("%d ",queB[iB].f);
// }
printf("\n最短的步數(shù)是：%d\n",queB[tailB - 1].s);
getchar();
return;
}
char* getDateTime()
{
static char nowtime[20];
time_t rawtime;
struct tm* ltime;
time(&rawtime);
ltime = localtime(&rawtime);
strftime(nowtime, 20, "%Y-%m-%d %H:%M:%S", ltime);
return nowtime;
}
本人也是剛剛學習蔗彤，如有錯誤川梅，請多多指正。
本文部分內(nèi)容參考 【啊哈然遏！算法】這本書
代碼例子
