深度優先搜索演算法
#define MaxVerNum 100 /* 最大頂點數為*/
typedef enum {False,True} boolean;
#include "stdio.h"
#include "stdlib.h"
boolean visited[MaxVerNum];
typedef struct node /* 表結點*/
{
int adjvex;/* 鄰接點域,一般是放頂點對應的序號或在表頭向量中的下標*/
char Info; /*與邊(或弧)相關的信息*/
struct node * next; /* 指向下一個鄰接點的指針域*/
} EdgeNode;
typedef struct vnode /* 頂點結點*/
{
char vertex; /* 頂點域*/
EdgeNode * firstedge; /* 邊表頭指針*/
} VertexNode;
typedef struct
{
VertexNode adjlist[MaxVerNum]; /* 鄰接表*/
int n,e; /* 頂點數和邊數*/
} ALGraph; /* ALGraph是以鄰接表方式存儲的圖類型*/
//建立一個無向圖的鄰接表存儲的演算法如下：
void CreateALGraph(ALGraph *G)/* 建立有向圖的鄰接表存儲*/
{
int i,j,k;
int N,E;
EdgeNode *p;
printf("請輸入頂點數和邊數：");
scanf("%d %d",&G->n,&G->e);
printf("n=%d,e=%d\n\n",G->n,G->e);
getchar();
for(i=0;i<G->n;i++) /* 建立有n個頂點的頂點表*/
{
printf("請輸入第%d個頂點字元信息(共%d個)：",i+1,G->n);
scanf("%c",&(G->adjlist[i].vertex)); /* 讀入頂點信息*/
getchar();
G->adjlist[i].firstedge=NULL; /* 頂點的邊表頭指針設為空*/
}
for(k=0;k<2*G->e;k++) /* 建立邊表*/
{
printf("請輸入邊<Vi,Vj>對應的頂點序號(共%d個)：",2*G->e);
scanf("%d %d",&i,&j);/* 讀入邊<Vi,Vj>的頂點對應序號*/
p=(EdgeNode *)malloc(sizeof(EdgeNode)); // 生成新邊表結點p
p->adjvex=j; /* 鄰接點序號為j */
p->next=G->adjlist[i].firstedge;/* 將結點p插入到頂點Vi的鏈表頭部*/
G->adjlist[i].firstedge=p;
}
printf("\n圖已成功創建!對應的鄰接表如下：\n");
for(i=0;i<G->n;i++)
{
p=G->adjlist[i].firstedge;
printf("%c->",G->adjlist[i].vertex);
while(p!=NULL)
{
printf("[ %c ]",G->adjlist[p->adjvex].vertex);
p=p->next;
}
printf("\n");
}
printf("\n");
} /*CreateALGraph*/
int FirstAdjVertex(ALGraph *g,int v)//找圖g中與頂點v相鄰的第一個頂點
{
if(g->adjlist[v].firstedge!=NULL) return (g->adjlist[v].firstedge)->adjvex;
else return 0;
}
int NextAdjVertex(ALGraph *g ,int vi,int vj )//找圖g中與vi相鄰的，相對相鄰頂點vj的下一個相鄰頂點
{
EdgeNode *p;
p=g->adjlist[vi].firstedge;
while( p!=NULL && p->adjvex!=vj) p=p->next;
if(p!=NULL && p->next!=NULL) return p->next->adjvex;
else return 0;
}
void DFS(ALGraph *G,int v) /* 從第v個頂點出發深度優先遍歷圖G */
{
int w;
printf("%c ",G->adjlist[v].vertex);
visited[v]=True; /* 訪問第v個頂點，並把訪問標志置True */
for(w=FirstAdjVertex(G,v);w;w=NextAdjVertex(G,v,w))
if (!visited[w]) DFS(G,w); /* 對v尚未訪問的鄰接頂點w遞歸調用DFS */
}
void DFStraverse(ALGraph *G)
/*深度優先遍歷以鄰接表表示的圖G，而以鄰接矩陣表示時，演算法完全相同*/
{ int i,v;
for(v=0;v<G->n;v++)
visited[v]=False;/*標志向量初始化*/
//for(i=0;i<G->n;i++)
if(!visited[0]) DFS(G,0);
}/*DFS*/
void main()
{
ALGraph G;
CreateALGraph(&G);
printf("該無向圖的深度優先搜索序列為：");
DFStraverse(&G);
printf("\nSuccess!\n");
}
❷ 深度優先演算法解決八數碼問題
首先我們來想像一隻老鼠，在一座不見天日的迷宮內，老鼠在入口處進去，要從出 口出來。那老鼠會怎麼走？當然是這樣的：老鼠如果遇到直路，就一直往前走，如果遇到分叉路口，就任意選 擇其中的一個繼續往下走，如果遇到死胡同，就退回到最近的一個分叉路口，選擇另一條道路再走下去，如果 遇到了出口，老鼠的旅途就算結束了。深度優先搜索法的基本原則就是這樣：按照某種條件往前試探搜索，如 果前進中遭到失敗（正如老鼠遇到死胡同）則退回頭另選通路繼續搜索，直到找到條件的目標為止。
實現這一演算法，我們要用到編程的另一大利器--遞歸。遞歸是一個很抽象的概念， 但是在日常生活中，我們還是能夠看到的。拿兩面鏡子來，把他們面對著面，你會看到什麼？你會看到鏡子中 有無數個鏡子？怎麼回事？A鏡子中有B鏡子的象，B鏡子中有A鏡子的象，A鏡子的象就是A鏡子本身的真實寫 照，也就是說A鏡子的象包括了A鏡子，還有B鏡子在A鏡子中的象………………好累啊，又煩又繞口，還不好理 解。換成計算機語言就是A調用B，而B又調用A，這樣間接的，A就調用了A本身，這實現了一個重復的功能。再 舉一個例子；從前有座山，山裡有座廟，廟里有個老和尚，老和尚在講故事，講什麼呢？講：從前有座山，山 里有座廟，廟里有個老和尚，老和尚在講故事，講什麼呢？講：從前有座山，山裡有座廟，廟里有個老和尚， 老和尚在講故事，講什麼呢？講：…………。好傢伙，這樣講到世界末日還講不玩，老和尚講的故事實際上就 是前面的故事情節，這樣不斷地調用程序本身，就形成了遞歸。 萬一這個故事中的某一個老和尚看這個故事不 順眼，就把他要講的故事換成：「你有完沒完啊！」，這樣，整個故事也就嘎然而止了。我們編程就要注意這 一點，在適當的時候，就必須要有一個這樣的和尚挺身而出，把整個故事給停下來，或者使他不再往深一層次 搜索，要不，我們的遞歸就會因計算機存儲容量的限制而被迫溢出，切記，切記。
我們把遞歸思想運用到上面的迷宮中，記老鼠現在所在的位置是(x,y),那它現在有 前後左右4個方向可以走，分別是(x+1,y),(x-1,y),(x,y+1),(x,y-1),其中一個方向是它來時的路，我們先不 考慮，我們就分別嘗試其他三個方向，如果某個方向是路而不是牆的話，老鼠就向那個方向邁出一步。在新的 位置上，我們又可以重復前面的步驟。老鼠走到了死胡同又是怎麼回事？就是除了來時的路，其他3個方向都是 牆，這時這條路就走到了盡頭，無法再向深一層發展，我們就應該沿來時的路回去，嘗試另外的方向。
例：八皇後問題：在標准國際象棋的棋盤上（8*8格）准備放置8隻皇後，我們知 道，國際象棋中皇後的威力是最大的，她既可以橫走豎走，還可以斜著走，遇到擋在她前進路線上的敵人，她 就可以吃掉對手。要求在棋盤上安放8隻皇後，使她們彼此互相都不能吃到對方，求皇後的放法。
這是一道很經典的題目了，我們先要明確一下思路，如何運用深度優先搜索法，完 成這道題目。我們先建立一個8*8格的棋盤，在棋盤的第一行的任意位置安放一隻皇後。緊接著，我們就來放 第二行，第二行的安放就要受一些限制了，因為與第一行的皇後在同一豎行或同一對角線的位置上是不能安放 皇後的，接下來是第三行，……，或許我們會遇到這種情況，在擺到某一行的時候，無論皇後擺放在什麼位 置，她都會被其他行的皇後吃掉，這說明什麼呢？這說明，我們前面的擺放是失敗的，也就是說，按照前面 的皇後的擺放方法，我們不可能得到正確的解。那這時怎麼辦？改啊，我們回到上一行，把原先我們擺好的 皇後換另外一個位置，接著再回過頭擺這一行，如果這樣還不行或者上一行的皇後只有一個位置可放，那怎 么辦？我們回到上一行的上一行，這和老鼠碰了壁就回頭是一個意思。就這樣的不斷的嘗試
❸ 圖的深度優先遍歷演算法屬於_ A.窮舉法 B.回溯法 C.遞歸 D.分治法
圖的深度優先遍歷演算法屬於_ A.窮舉法 B.回溯法 C.遞歸 D.分治法
B 回溯
❹ 深度優先演算法的定義
深度優先搜索演算法（Depth-First-Search），是搜索演算法的一種。是沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。當節點v的所有邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重復以上過程，整個進程反復進行直到所有節點都被訪問為止。屬於盲目搜索。
深度優先搜索是圖論中的經典演算法，利用深度優先搜索演算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。
因發明「深度優先搜索演算法」，霍普克洛夫特與陶爾揚共同獲得計算機領域的最高獎：圖靈獎.
❺ 深度優先演算法的例1.迷宮問題
實現這一演算法，我們要用到編程的一大利器--遞歸。「遞歸」是一個很抽象的概念， 但是在日常生活中，我們還是能夠看到的。拿兩面鏡子來，把他們面對著面，你會看到什麼？你會看到鏡子中 有無數個鏡子？怎麼回事？A鏡子中有B鏡子的象，B鏡子中有A鏡子的象，A鏡子的象就是A鏡子本身的真實寫照，也就是說A鏡子的象包括了A鏡子，還有B鏡子在A鏡子中的象………………好累啊，又煩又繞口，還不好理解。換成計算機語言就是A調用B，而B又調用A，這樣間接的，A就調用了A本身，這實現了一個重復的功能。
再舉一個例子：從前有座山，山裡有座廟，廟里有個老和尚，老和尚在講故事，講什麼呢？講：從前有座山，山裡有座廟，廟里有個老和尚，老和尚在講故事，講什麼呢？講：從前有座山，山裡有座廟，廟里有個老和尚， 老和尚在講故事，講什麼呢？講：…………。好傢伙，這樣講到世界末日還講不完，老和尚講的故事實際上就是前面的故事情節，這樣不斷地調用程序本身，就形成了遞歸。 萬一這個故事中的某一個老和尚看這個故事不順眼，就把他要講的故事換成：「你有完沒完啊！」，這樣，整個故事也就嘎然而止了。我們編程就要注意這一點，在適當的時候，就必須要有一個這樣的和尚挺身而出，把整個故事給停下來，或者使他不再往深一層次搜索，要不，遞歸就會因計算機存儲容量的限制而被迫溢出，切記，切記。 這是一道很經典的題目了，我們先要明確一下思路，如何運用深度優先搜索法，完 成這道題目。我們先建立一個8*8格的棋盤，在棋盤的第一行的任意位置安放一隻皇後。緊接著，我們就來放 第二行，第二行的安放就要受一些限制了，因為與第一行的皇後在同一豎行或同一對角線的位置上是不能安放 皇後的，接下來是第三行，……，或許我們會遇到這種情況，在擺到某一行的時候，無論皇後擺放在什麼位 置，她都會被其他行的皇後吃掉，這說明什麼呢？這說明，我們前面的擺放是失敗的，也就是說，按照前面 的皇後的擺放方法，我們不可能得到正確的解。那這時怎麼辦？改啊，我們回到上一行，把原先我們擺好的 皇後換另外一個位置，接著再回過頭擺這一行，如果這樣還不行或者上一行的皇後只有一個位置可放，那怎 么辦？我們回到上一行的上一行，這和老鼠碰了壁就回頭是一個意思。就這樣的不斷的嘗試，修正,我們最終會得到正確的結論的。
❻ 深度優先遍歷與廣度優先遍歷的區別
一、指代不同
1、深度優先遍歷：是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次。
2、廣度優先遍歷：系統地展開並檢查圖中的所有節點，以找尋結果。
二、特點不同
1、深度優先遍歷：所有的搜索演算法從其最終的演算法實現上來看，都可以劃分成兩個部分──控制結構和產生系統。正如前面所說的，搜索演算法簡而言之就是窮舉所有可能情況並找到合適的答案，所以最基本的問題就是羅列出所有可能的情況，這其實就是一種產生式系統。
2、廣度優先遍歷：並不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。
三、演算法不同
1、深度優先遍歷：把根節點壓入棧中。每次從棧中彈出一個元素，搜索所有在它下一級的元素，把這些元素壓入棧中。並把這個元素記為它下一級元素的前驅。找到所要找的元素時結束程序。如果遍歷整個樹還沒有找到，結束程序。
2、廣度優先遍歷：把根節點放到隊列的末尾。每次從隊列的頭部取出一個元素，查看這個元素所有的下一級元素，把它們放到隊列的末尾。並把這個元素記為它下一級元素的前驅。找到所要找的元素時結束程序。如果遍歷整個樹還沒有找到，結束程序。
❼ 數據結構簡要說明深度優先搜索法(DFS)和廣度優先搜索法(BFS)的不同之處
一個是類似層序遍歷，一個類似先序遍歷
❽ 深度優先搜索的系統演算法
所有的搜索演算法從其最終的演算法實現上來看，都可以劃分成兩個部分──控制結構和產生系統。正如前面所說的，搜索演算法簡而言之就是窮舉所有可能情況並找到合適的答案，所以最基本的問題就是羅列出所有可能的情況，這其實就是一種產生式系統。
我們將所要解答的問題劃分成若干個階段或者步驟，當一個階段計算完畢，下面往往有多種可選選擇，所有的選擇共同組成了問題的解空間，對搜索演算法而言，將所有的階段或步驟畫出來就類似是樹的結構（如圖）。
從根開始計算，到找到位於某個節點的解，回溯法（深度優先搜索）作為最基本的搜索演算法，其採用了一種「一隻向下走，走不通就掉頭」的思想（體會「回溯」二字），相當於採用了先根遍歷的方法來構造搜索樹。
上面的話可能難於理解，沒關系，我們通過基本框架和例子來闡述這個演算法，你會發現其中的原理非常簡單自然。
❾ 連通圖的深度優先遍歷演算法
這個第一個點是隨機的。只是看你怎麼儲存的。如果你把v的鄰接頂點用數組保存，那麼它在數組的最前邊。用指針的話，就指向下一個緊接的位置。
❿ 深度優先演算法 和 寬度優先演算法 的優缺點
1、深度優先演算法佔內存少但速度較慢，廣度優先演算法佔內存多但速度較快，在距離和深度成正比的情況下能較快地求出最優解。
2、深度優先與廣度優先的控制結構和產生系統很相似，唯一的區別在於對擴展節點選取上。由於其保留了所有的前繼節點，所以在產生後繼節點時可以去掉一部分重復的節點，從而提高了搜索效率。
3、這兩種演算法每次都擴展一個節點的所有子節點，而不同的是，深度優先下一次擴展的是本次擴展出來的子節點中的一個，而廣度優先擴展的則是本次擴展的節點的兄弟點。在具體實現上為了提高效率,所以採用了不同的數據結構。