題目：

圖的深度優(yōu)先搜索
描述：
圖的深度優(yōu)先搜索類似于樹的先根遍歷，是樹的先根遍歷的推廣。即從某個結(jié)點開始，先訪問該結(jié)點，然后深度訪問該結(jié)點的第一棵子樹，依次為第二頂子樹。如此進行下去，直到所有的結(jié)點都訪問為止。在該題中，假定所有的結(jié)點以“A”至“Z”中的若干字符表示，且要求結(jié)點的訪問順序根據(jù)“A”至“Z”的字典順序進行訪問。例如有如下圖：

如果要求從H開始進行深度優(yōu)先搜索，則搜索結(jié)果為：H->A->K->U->E.
輸入：
輸入只包含一個測試用例，第一行為一個自然數(shù)n，表示頂點的個數(shù)，第二行為n個大寫字母構(gòu)成的字符串，表示頂點，接下來是為一個n*n大小的矩陣，表示圖的鄰接關(guān)系。數(shù)字為0表示不鄰接，否則為相應(yīng)的邊的長度。
最后一行為一個字符，表示要求進行深度優(yōu)先搜索的起始頂點。
輸出：
用一行輸出深度優(yōu)先搜索結(jié)果，起始點為給定的頂點，各頂點之間用一個空格隔開(注意后面的提示)。

樣例輸入：
5
HUEAK
0 0 2 3 0
0 0 0 7 4
2 0 0 0 0
3 7 0 0 1
0 4 0 1 0
H

樣例輸出：
H A K U E

代碼：

代碼與圖的廣度搜索差不多，不同的就是將隊列變?yōu)闂?/p>

以下兩個代碼都差不多，都是利用對應(yīng)的ascll碼轉(zhuǎn)換成0~25相應(yīng)的數(shù)字，理論上來說是一樣的

權(quán)值在本題沒有使用

需注意如圖：

輸入：

5
HUEAG
0 0 2 3 0
0 0 0 7 4
2 0 0 0 0
3 7 0 0 1
0 4 0 1 0
U

輸出：

U A G H E?

第一個棧直接儲存字符，使用時換成數(shù)字

import java.util.Scanner;
import java.util.Stack;public class Xingyuxingxi {public static void main(String[] args){Scanner sc=new Scanner(System.in);int a=sc.nextInt();String b=sc.next();int [][]g=new int[26][26];boolean []pd=new boolean[26];//記錄結(jié)點是否遍歷過for (int i = 0; i < a; i++) {for (int j = 0; j < a; j++) {g[b.charAt(i)-'A'][b.charAt(j)-'A'] = sc.nextInt();//把字符轉(zhuǎn)換成1~25的相應(yīng)下標，當假設(shè)b.charAt(i)='A',b.charAt(j)='B',則相當于用0與1有個邊,表示'A'與'B'有個邊}}Stack<Character>zhan=new Stack<Character>();char d=sc.next().charAt(0);zhan.push(d);while(!zhan.isEmpty()){d=zhan.pop();int y=d-'A';if(!pd[y])System.out.print(d+" ");pd[y]=true;for (int i = 25; i >=0 ; i--) {//從最后一個字母開始入棧，保證了小的字母先出棧，棧先進后出if(g[y][i]!=0&&!pd[i])//非0表示有連接，false表示沒被標記，權(quán)值在這里沒有用{char zm=(char)(i+'A');zhan.push(zm);}}}}
}

第二個先全部換成數(shù)字，棧儲存數(shù)字，最后輸出轉(zhuǎn)換成字符

import java.util.Scanner;
import java.util.Stack;public class Xingyuxingxi {public static void main(String[] args){Scanner sc=new Scanner(System.in);int a=sc.nextInt();String b=sc.next();int [][]g=new int[26][26];boolean []pd=new boolean[26];//記錄結(jié)點是否遍歷過for (int i = 0; i < a; i++) {for (int j = 0; j < a; j++) {g[b.charAt(i)-'A'][b.charAt(j)-'A'] = sc.nextInt();//把字符轉(zhuǎn)換成1~25的相應(yīng)下標，當假設(shè)b.charAt(i)='A',b.charAt(j)='B',則相當于用0與1有個邊,表示'A'與'B'有個邊}}Stack<Integer>zhan=new Stack<Integer>();char d=sc.next().charAt(0);zhan.push(d-'A');while(!zhan.isEmpty()){int y=zhan.pop();if(!pd[y])System.out.print((char)(y+'A')+" ");pd[y]=true;for (int i = 25; i >=0 ; i--) {//從最后一個字母開始入棧，保證了小的字母先出棧，棧先進后出if(g[y][i]!=0&&!pd[i])//非0表示有連接，false表示沒被標記，權(quán)值在這里沒有用{zhan.push(i);}}}}
}