dfs演算法跟回溯的

⑴ dfs演算法是什麼

DFS是深度優先搜索演算法。

深度優先搜索演算法，又稱DFS(Depth First Search)。DFS演算法是一種搜索演算法，而搜索演算法實質上是一種枚舉，即藉助計算機的高性能來有目的地枚舉一個問題的部分情況或這個問題的所有情況，進而求出問題的解的一種方法。

分類：

1. 順序性剪枝

若一些題的搜索順序對答案無影響，那麼搜索順序的不同會導致搜索樹形態的改變，優先搜索分支較少的階段，此時能減少搜索的規模。

2. 重復性剪枝

在搜索的時候如果有多種方式可以到達一個狀態，那麼只需要搜索一個分支就可以了。

3. 可行性剪枝

可行性剪枝是對搜索正確性的一個保證，當分支在遞歸邊界的時候回溯。

4. 最優性剪枝

在搜索過程中，如果當前階段的代價已經超過我們已知的最小代價，那麼此時繼續搜索下去就失去了意義。

5. 記憶化剪枝

記錄搜索狀態的結果，當重復遍歷一個狀態的時候就可以直接返回這個狀態的答案，避免重復的搜索。

⑵ 求有權無向圖的DFS演算法

深度優先遍歷類似於樹的先序遍歷，俗稱一條路走到黑，然後再考慮回溯的問題，回溯到最近訪問的頂點並看它是否還有相鄰頂點未訪問，若無繼續往前回溯。

我下面寫寫核心偽代碼，其他諸如圖的類型定義、還有你要對每個結點做的具體操作（我在代碼中用visit()函數來代替了，具體做啥操作根據題目來）我就不寫了。
bool visited[MSX_VERTEX_NUM]; //標記訪問數組
void DFS_Traverse(Grath G) //對圖G進行DFS
{
for(v=0;v<G.vexnum;++v)

{
visited[v]=false; //初始化已訪問標記數據

}
for(v=0;v<G.vexnum;++v) //假設從v=0開始遍歷

{
if(!visited[v])

DFS(G,v);

}

}
void DFS(Graph G,int v) //從頂點v出發，用遞歸的思想，深度優先遍歷
{
visit(v); //這里的visit()就是對頂點v的具體操作，題目是啥就自己寫啥

visited[v]=true; //標記已訪問

for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))

//從最近結點開始，依次找相鄰結點
{
if(!visited[w]) //w為還未訪問的相鄰結點

{
DFS(G,w);

}
}
}

⑶ C語言編寫深度優先搜索(DFS)是否需要回溯

我就是從pascal轉到c多年的，這些演算法和語言無關的，只是一種思想。都是怎樣方便就怎樣的，深搜我個人就喜歡直接寫遞歸解決

⑷ dfs演算法是什麼

DFS其實叫深度優先搜索演算法，起始它只是一種搜索的方法思路，並沒有固定的演算法格式。

作為搜索演算法的一種，DFS對於尋找一個解的NP（包括NPC）問題作用很大。但是，搜索演算法畢竟是時間復雜度是O(n!)的階乘級演算法，它的效率非常低，在數據規模變大時，這種演算法就顯得力不從心了。

DFS思路：

DFS思路是一條路走到底，撞到了牆再回頭。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重復以上過程，整個進程反復進行直到所有節點都被訪問為止，屬於盲目搜索。