深度優先遍歷

深度優先搜尋，是圖論中的經典算法。其利用深度優先搜尋算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。

基本介紹

• 中文名：深度優先遍歷
• 外文名：Depth-First Traversal
• 學科：數據結構
• 屬於：圖

遞歸定義

深度優先遍歷(Depth-First Traversal)

假設給定圖G的初態是所有頂點均未曾訪問過。在G中任選一頂點v為初始出發點(源點)，則深度優先遍歷可定義如下：首先訪問出發點v，並將其標記為已訪問過；然後依次從v出發搜尋v的每個鄰接點w。若w未曾訪問過，則以w為新的出發點繼續進行深度優先遍歷，直至圖中所有和源點v有路徑相通的頂點(亦稱為從源點可達的頂點)均已被訪問為止。若此時圖中仍有未訪問的頂點，則另選一個尚未訪問的頂點作為新的源點重複上述過程，直至圖中所有頂點均已被訪問為止。

圖的深度優先遍歷類似於樹的前序遍歷。採用的搜尋方法的特點是儘可能先對縱深方向進行搜尋。這種搜尋方法稱為深度優先搜尋(Depth-First Search)。相應地，用此方法遍歷圖就很自然地稱之為圖的深度優先遍歷。

過程

設x是當前被訪問頂點，在對x做過訪問標記後，選擇一條從x出發的未檢測過的邊(x，y)。若發現頂點y已訪問過，則重新選擇另一條從x出發的未檢測過的邊，否則沿邊(x，y)到達未曾訪問過的y，對y訪問並將其標記為已訪問過；然後從y開始搜尋，直到搜尋完從y出發的所有路徑，即訪問完所有從y出發可達的頂點之後，才回溯到頂點x，並且再選擇一條從x出發的未檢測過的邊。上述過程直至從x出發的所有邊都已檢測過為止。此時，若x不是源點，則回溯到在x之前被訪問過的頂點；否則圖中所有和源點有路徑相通的頂點(即從源點可達的所有頂點)都已被訪問過，若圖G是連通圖，則遍歷過程結束，否則繼續選擇一個尚未被訪問的頂點作為新的頂點，繼續遍歷。

template <int max_size>void Digraph<max_size> :: depth_first(void (*visit)(Vertex &)) const

/* Post: The function *visit has been performed at each vertex of the Digraph in depth-first order.

Uses: Method traverse to produce the recursive depth-first order. */

{

bool visited [max_size];

Vertex v;

for (all v in G) visited [v] = false;

for (all v in G) if (!visited [v])

traverse (v, visited, visit);

}

template <int max_size>

void Digraph<max_size>::traverse(Vertex &v, bool visited[ ],void (*visit)(Vertex &)) const

/* Pre: v is a vertex of the Digraph.

Post: The depth-first traversal, using function *visit, has been completed for v and for all vertices that can be reached from v.

Uses: traverse recursively. */

{

Vertex w;

visited [v] = true;

(*visit) (v);

for (all w adjacent to v)

if (!visited [w])

traverse (w, visited, visit);

}

java代碼如下：
//求DFS的深度優先遞歸算法
public class DNFSreach {

/**
* 這裡是文檔說明
* 算法如下
*開始
*Start;
*
* procedure DFS_visit(G,u)
* color[u] = Gray;//白色結點u已被發現
* for each edge (u,v)do
* if color[u] = White then
* DFS_visit(G,v);
* repeat color[u]=black;//完成後置u為黑色
* end;
*
* procedure DFS(G)
* for each vertex u 屬於V do
* color[u] = white
* for vertex each u 屬於 V do
* if color[u]=white
* then DFS_visit(G,u)
* repeat
*
*
* 構建一個無向圖
* 無窮大表示這兩個點無邊，1表示兩者有邊
* 白色用1表示，灰色用2表示，黑色用3表示
* 初始狀態均為白色
* 搜尋中被發現的頂點置為灰色
* 結束時，即其鄰接表被完全檢索之後，其被置為黑色
* 構建一個color[8]數組，其中color[0]不用
* 初始化為0
* S表示無窮大
* 0 1 2 3 4 5 6 7 8
* -------------------------
* 0
* 1 s 1 1 s s s s s
* 2 1 s s 1 1 s s s
* 3 1 s s s s 1 1 s
* 4 s 1 s s s s s 1
* 5 s 1 s s s s s 1
* 6 s s 1 s s s 1 s
* 7 s s 1 s s 1 s s
* 8 s s s 1 1 s s s
*
* 深度優先搜尋的結果應該為
* 1-2-4-8-5-3-6-7
*
* @param args
*/
static int color[];
static int d =0;
public static void main(String[] args) {
int s = Integer.MAX_VALUE;
int G[][]={{s,s,s,s,s,s,s,s,s},
{s,s,1,1,s,s,s,s,s},
{s,1,s,s,1,1,s,s,s},
{s,1,s,s,s,s,1,1,s},
{s,s,1,s,s,s,s,s,1},
{s,s,1,s,s,s,s,s,1},
{s,s,s,1,s,s,s,1,s},
{s,s,s,1,s,s,1,s,s},
{s,s,s,s,1,1,s,s,s}};
color = new int [9];
ProcedureDFS(G,9);
}
public static void ProcedureDFS(int [][]G,int n){
//圖是以二維數組的形式保存
//n是二維數組的維數
for(int i=1;i <= n-1;i++){
color[i]=1;//把每一個頂點都置為白色，表示還沒搜尋
}
for(int i=1;i<= n-1;i++){
//對於每一個頂點沒被訪問的頂點進行訪問
if(color[i] == 1){
DFS_visit(G,i);//遍歷其訪問的頂點
}
}
}

private static void DFS_visit(int[][] g, int i) {
// TODO 自動生成的方法存根
color[i] = 2;//標誌為灰色，表示被訪問過
d++;
if(d != g.length-1)
System.out.print(""+i+" -> ");
if(d == g.length-1){
System.out.println(""+i);
}
for(int t=1;t<= g.length-1;t++){
//鄰接點沒有被訪問到
if(color[t] == 1 && g[i][t] != Integer.MAX_VALUE){
DFS_visit(g,t);
}
}
color[i] = 3;//標誌位黑色
}
}

最小花費舉例：

package test1;
import java.io.FileInputStream;
import java.util.Scanner;

class Deptfsearch {
static int Answer, N, sum, cost;
static int[][] input, mark;
static int[] visit;

static boolean check() {
for (int v = 1; v <= N; v++) {
if (visit[v] == 0)
return false;
}
return true;
}

static void Try(int u) {
if (check()) {
if (input[u][1] != 0 && Answer > cost + input[u][1])
Answer = cost + input[u][1];
return;
}
if (Answer < cost)
return;
for (int v = 1; v <= N; v++) {
if (input[u][v] != 0 && visit[v] == 0) {
visit[v] = 1;
cost = cost + input[u][v];
Try(v);
cost = cost - input[u][v];
visit[v] = 0;
}
}
}

public static void main(String args[]) throws Exception {
@SuppressWarnings("resource")
Scanner sc = new Scanner(System.in);
sc = new Scanner(new FileInputStream("sample_input.txt"));

int T = sc.nextInt();
for (int test_case = 0; test_case < T; test_case++) {

sum = 0;
cost = 0;
N = sc.nextInt();
input = new int[N + 1][N + 1];
mark = new int[N + 1][N + 1];
visit = new int[N + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
input[i][j] = sc.nextInt();
sum = sum + input[i][j];
}
}
Answer = sum + 1;
visit[1] = 1;
if (N == 1)
Answer = input[1][1];
else
Try(1);
// Print the answer to standard output(screen).
System.out.println("Case #" + (test_case + 1));
System.out.println(Answer);
}
}
}