題目：

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

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

樣例輸入：
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

代碼：

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

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

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

需注意如圖：

輸入：

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?

第一個(gè)棧直接儲(chǔ)存字符，使用時(shí)換成數(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é)點(diǎn)是否遍歷過(guò)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)下標(biāo)，當(dāng)假設(shè)b.charAt(i)='A',b.charAt(j)='B',則相當(dāng)于用0與1有個(gè)邊,表示'A'與'B'有個(gè)邊}}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--) {//從最后一個(gè)字母開(kāi)始入棧，保證了小的字母先出棧，棧先進(jìn)后出if(g[y][i]!=0&&!pd[i])//非0表示有連接，false表示沒(méi)被標(biāo)記，權(quán)值在這里沒(méi)有用{char zm=(char)(i+'A');zhan.push(zm);}}}}
}

第二個(gè)先全部換成數(shù)字，棧儲(chǔ)存數(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é)點(diǎn)是否遍歷過(guò)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)下標(biāo)，當(dāng)假設(shè)b.charAt(i)='A',b.charAt(j)='B',則相當(dāng)于用0與1有個(gè)邊,表示'A'與'B'有個(gè)邊}}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--) {//從最后一個(gè)字母開(kāi)始入棧，保證了小的字母先出棧，棧先進(jìn)后出if(g[y][i]!=0&&!pd[i])//非0表示有連接，false表示沒(méi)被標(biāo)記，權(quán)值在這里沒(méi)有用{zhan.push(i);}}}}
}