假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)均未被訪(fǎng)問(wèn)
我們提供的服務(wù)有：網(wǎng)站制作、網(wǎng)站建設(shè)、微信公眾號(hào)開(kāi)發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、遷西ssl等。為數(shù)千家企事業(yè)單位解決了網(wǎng)站和推廣的問(wèn)題。提供周到的售前咨詢(xún)和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的遷西網(wǎng)站制作公司
從某個(gè)頂點(diǎn)出發(fā)，然后依次從它的各個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪(fǎng)問(wèn)到。
若此時(shí)尚有其他頂點(diǎn)未被訪(fǎng)問(wèn)到，則另選一個(gè)未被訪(fǎng)問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)到為止。
實(shí)現(xiàn)深度優(yōu)先遍歷的關(guān)鍵在于回溯。所謂“回溯”，就是自后往前，追溯曾經(jīng)走過(guò)的路徑。
算法特點(diǎn)
深度優(yōu)先搜索是一個(gè)遞歸的過(guò)程。
首先，選定一個(gè)出發(fā)點(diǎn)后進(jìn)行遍歷，如果有鄰接的未被訪(fǎng)問(wèn)過(guò)的節(jié)點(diǎn)則繼續(xù)前進(jìn)。
若不能繼續(xù)前進(jìn)，則回退一步再前進(jìn)
若回退一步仍然不能前進(jìn)，則連續(xù)回退至可以前進(jìn)的位置為止。
重復(fù)此過(guò)程，直到所有與選定點(diǎn)相通的所有頂點(diǎn)都被遍歷。
深度優(yōu)先搜索是遞歸過(guò)程，帶有回退操作，因此需要使用棧存儲(chǔ)訪(fǎng)問(wèn)的路徑信息。當(dāng)訪(fǎng)問(wèn)到的當(dāng)前頂點(diǎn)沒(méi)有可以前進(jìn)的鄰接頂點(diǎn)時(shí)，需要進(jìn)行出棧操作，將當(dāng)前位置回退至出棧元素位置。
圖解過(guò)程
無(wú)向圖的深度優(yōu)先遍歷
以下圖所示無(wú)向圖說(shuō)明深度優(yōu)先搜索遍歷過(guò)程。
實(shí)例一
在這里插入圖片描述
假設(shè)我們從頂點(diǎn)A開(kāi)始，遍歷過(guò)程中的每一步如下：
首先選取頂點(diǎn)A為起始點(diǎn)，輸出A頂點(diǎn)信息，而且將A入棧，并且標(biāo)記A為已訪(fǎng)問(wèn)頂點(diǎn)
A的鄰接頂點(diǎn)有C、D、F，從中任意選取一個(gè)頂點(diǎn)前進(jìn)。這里我們選取C為前進(jìn)位置頂點(diǎn)。輸出C頂點(diǎn)信息，將C入棧，并標(biāo)記C為已訪(fǎng)問(wèn)頂點(diǎn)。當(dāng)前位置指向頂點(diǎn)C
頂點(diǎn)C的鄰接頂點(diǎn)有A、D、B，此時(shí)A已經(jīng)標(biāo)記為已訪(fǎng)問(wèn)頂點(diǎn)，因此不能繼續(xù)訪(fǎng)問(wèn)。從B或者D中選取一個(gè)頂點(diǎn)前進(jìn)，這里我們選取B頂點(diǎn)為前進(jìn)位置頂點(diǎn)。輸出B頂點(diǎn)信息，將B入棧，標(biāo)記B頂點(diǎn)為已訪(fǎng)問(wèn)頂點(diǎn)。當(dāng)前位置指向B
頂點(diǎn)B的鄰接頂點(diǎn)只有C、E，C已被標(biāo)記，不能繼續(xù)訪(fǎng)問(wèn)，因此選取E為前進(jìn)位置頂點(diǎn)，輸出E頂點(diǎn)信息，將E入棧，標(biāo)記E頂點(diǎn)，當(dāng)前位置指向E。
頂點(diǎn)E的鄰接頂點(diǎn)均已被標(biāo)記，此時(shí)無(wú)法繼續(xù)前進(jìn)，則需要進(jìn)行回退。將當(dāng)前位置回退至頂點(diǎn)B，回退的同時(shí)將E出棧。
頂點(diǎn)B的鄰接頂點(diǎn)也均被標(biāo)記，需要繼續(xù)回退，當(dāng)前位置回退至C，回退同時(shí)將B出棧。
頂點(diǎn)C可以前進(jìn)的頂點(diǎn)位置為D，則輸出D頂點(diǎn)信息，將D入棧，并標(biāo)記D頂點(diǎn)。當(dāng)前位置指向頂點(diǎn)D。
頂點(diǎn)D沒(méi)有前進(jìn)的頂點(diǎn)位置，因此需要回退操作。將當(dāng)前位置回退至頂點(diǎn)C，回退同時(shí)將D出棧。
頂點(diǎn)C沒(méi)有前進(jìn)的頂點(diǎn)位置，繼續(xù)回退，將當(dāng)前位置回退至頂點(diǎn)A，回退同時(shí)將C出棧。
頂點(diǎn)A前進(jìn)的頂點(diǎn)位置為F，輸出F頂點(diǎn)信息，將F入棧，并標(biāo)記F。將當(dāng)前位置指向頂點(diǎn)F。
頂點(diǎn)F的前進(jìn)頂點(diǎn)位置為G，輸出G頂點(diǎn)信息，將G入棧，并標(biāo)記G。將當(dāng)前位置指向頂點(diǎn)G。
頂點(diǎn)G沒(méi)有前進(jìn)頂點(diǎn)位置，回退至F。當(dāng)前位置指向F，回退同時(shí)將G出棧。
頂點(diǎn)F沒(méi)有前進(jìn)頂點(diǎn)位置，回退至A，當(dāng)前位置指向A，回退同時(shí)將F出棧。
頂點(diǎn)A沒(méi)有前進(jìn)頂點(diǎn)位置，繼續(xù)回退，棧為空，則以A為起始的遍歷結(jié)束。若圖中仍有未被訪(fǎng)問(wèn)的頂點(diǎn)，則選取未訪(fǎng)問(wèn)的頂點(diǎn)為起始點(diǎn)，繼續(xù)執(zhí)行此過(guò)程。直至所有頂點(diǎn)均被訪(fǎng)問(wèn)。
采用深度優(yōu)先搜索遍歷順序?yàn)锳-C-B-E-D-F-G。
利用一個(gè)臨時(shí)棧來(lái)實(shí)現(xiàn)回溯，最終遍歷完所有頂點(diǎn)
問(wèn)題：
（1）必須選取A作為遍歷的起點(diǎn)嗎？
不是原則我們可以選取任何一個(gè)節(jié)點(diǎn)作為起點(diǎn)進(jìn)行開(kāi)始，進(jìn)行深度優(yōu)先遍歷
（2）當(dāng)有多個(gè)鄰接點(diǎn)未被訪(fǎng)問(wèn)時(shí)，可以選取哪個(gè)作為下一個(gè)起點(diǎn)呢？
隨便哪個(gè)都行。
當(dāng)有多個(gè)臨界點(diǎn)可選時(shí)，相當(dāng)于走迷宮時(shí)出現(xiàn)了多個(gè)分叉路口，我們只要不走之前走過(guò)的路就行了。所以關(guān)鍵在于標(biāo)記哪個(gè)點(diǎn)是否已經(jīng)走過(guò)。不過(guò)，一般我們會(huì)定義一個(gè)原則，必須不碰重復(fù)點(diǎn)的情況下，選擇走左/右手第一條沒(méi)有走過(guò)的路，這樣比較好理解
兩個(gè)原則：
右手原則： 在沒(méi)有碰到重復(fù)頂點(diǎn)的情況下，分叉路口始終是向右手邊走，每路過(guò)一個(gè)頂點(diǎn)就做一個(gè)記號(hào)
左手原則： 在沒(méi)有碰到重復(fù)頂點(diǎn)的情況下，分叉路口始終是向左手邊走，每路過(guò)一個(gè)頂點(diǎn)就做一個(gè)記號(hào)
下面以右手原則進(jìn)行深度優(yōu)先遍歷再看個(gè)例子
實(shí)例二
在這里插入圖片描述
原則我們可以選取任何一個(gè)節(jié)點(diǎn)作為起點(diǎn)進(jìn)行開(kāi)始，進(jìn)行深度優(yōu)先遍歷，假設(shè)我們從頂點(diǎn)A開(kāi)始，遍歷過(guò)程中的每一步如下：
第一步：從頂點(diǎn)A開(kāi)始，將頂點(diǎn)A標(biāo)記為已訪(fǎng)問(wèn)節(jié)點(diǎn)
第二步：根據(jù)右手原則，訪(fǎng)問(wèn)頂點(diǎn)B，并將B標(biāo)記為已訪(fǎng)問(wèn)節(jié)點(diǎn)
第三步：右手原則，訪(fǎng)問(wèn)頂點(diǎn)C
第四步：右手原則，訪(fǎng)問(wèn)頂點(diǎn)D
第五步：右手原則，訪(fǎng)問(wèn)頂點(diǎn)E
第六步：右手原則，訪(fǎng)問(wèn)頂點(diǎn)F
在這里插入圖片描述
第七步：右手原則，應(yīng)該先訪(fǎng)問(wèn)頂點(diǎn)F的鄰接頂點(diǎn)A，但發(fā)現(xiàn)A已經(jīng)被訪(fǎng)問(wèn)，則訪(fǎng)問(wèn)A之外的最右側(cè)頂點(diǎn)G
在這里插入圖片描述
第八步：右手原則，先訪(fǎng)問(wèn)頂點(diǎn)B，頂點(diǎn)B已經(jīng)被訪(fǎng)問(wèn)；在訪(fǎng)問(wèn)頂點(diǎn)D，頂點(diǎn)D已經(jīng)被訪(fǎng)問(wèn)；最后訪(fǎng)問(wèn)頂點(diǎn)H
在這里插入圖片描述
第九步：發(fā)現(xiàn)頂點(diǎn)H的鄰接頂點(diǎn)均已被訪(fǎng)問(wèn)，則退回到頂點(diǎn)G;
第十步：頂點(diǎn)G的鄰接頂點(diǎn)均已被訪(fǎng)問(wèn)，則退回到頂點(diǎn)F；
第十一步：頂點(diǎn)F的鄰接頂點(diǎn)已被訪(fǎng)問(wèn)，則退回到頂點(diǎn)E；
第十二步：頂點(diǎn)E的鄰接頂點(diǎn)均已被訪(fǎng)問(wèn)，則退回到頂點(diǎn)D；
第十三步：頂點(diǎn)D的鄰接頂點(diǎn)I尚未被訪(fǎng)問(wèn)，則訪(fǎng)問(wèn)頂點(diǎn)I；
在這里插入圖片描述
第十四步：頂點(diǎn)I的鄰接頂點(diǎn)均已被訪(fǎng)問(wèn)，則退回到頂點(diǎn)D;
第十五步：頂點(diǎn)D的鄰接頂點(diǎn)均已被訪(fǎng)問(wèn)，退回到頂點(diǎn)C；
第十六步：頂點(diǎn)C的鄰接頂點(diǎn)均已被訪(fǎng)問(wèn)，則退回到頂點(diǎn)B；
頂點(diǎn)B的鄰接頂點(diǎn)均已被訪(fǎng)問(wèn)，則退回到頂點(diǎn)A，頂點(diǎn)A為起始頂點(diǎn)，深度優(yōu)先搜索結(jié)束。
圖的深度優(yōu)先搜索和二叉樹(shù)的前序遍歷、中序遍歷、后序遍歷本質(zhì)上均屬于一類(lèi)方法。
上面的過(guò)程可以總結(jié)為以下3個(gè)步驟：
首先選定一個(gè)未被訪(fǎng)問(wèn)過(guò)的頂點(diǎn)V作為起始頂點(diǎn)（或者訪(fǎng)問(wèn)指定的起始頂點(diǎn)V），并將其標(biāo)記為已訪(fǎng)問(wèn)
然后搜索與頂點(diǎn)V鄰接的所有頂點(diǎn)，判斷這些頂點(diǎn)是否被訪(fǎng)問(wèn)過(guò)，如果有未被訪(fǎng)問(wèn)過(guò)的頂點(diǎn)W；再選取與頂點(diǎn)W鄰接的未被訪(fǎng)問(wèn)過(guò)的一個(gè)頂點(diǎn)并進(jìn)行訪(fǎng)問(wèn)，依次重復(fù)進(jìn)行。當(dāng)一個(gè)頂點(diǎn)的所有的鄰接頂點(diǎn)都被訪(fǎng)問(wèn)過(guò)時(shí)，則依次回退到最近被訪(fǎng)問(wèn)的頂點(diǎn)。若該頂點(diǎn)還有其他鄰接頂點(diǎn)未被訪(fǎng)問(wèn)，則從這些未被訪(fǎng)問(wèn)的頂點(diǎn)中取出一個(gè)并重復(fù)上述過(guò)程，直到與起始頂點(diǎn)V相鄰接的所有頂點(diǎn)都被訪(fǎng)問(wèn)過(guò)為止。
若此時(shí)圖中依然有頂點(diǎn)未被訪(fǎng)問(wèn)，則再選取其中一個(gè)頂點(diǎn)作為起始頂點(diǎn)并進(jìn)行遍歷，轉(zhuǎn)（2）。反之，則遍歷結(jié)束。
有向圖深度優(yōu)先搜索
在這里插入圖片描述
（1）以頂點(diǎn)A為起始點(diǎn)，輸出A，將A入棧，并標(biāo)記A為已經(jīng)訪(fǎng)問(wèn)。當(dāng)前位置指向A。
（2）以A為尾的邊只有1條，且邊的頭為頂點(diǎn)B，則前進(jìn)位置為頂點(diǎn)B，輸出B，將B入棧，標(biāo)記B。當(dāng)前位置指向B。
（3）頂點(diǎn)B可以前進(jìn)的位置有C與F，選取F為前進(jìn)位置，輸出F，將F入棧，并標(biāo)記F。當(dāng)前位置指向F。
（4）頂點(diǎn)F的前進(jìn)位置為G，輸出G，將G入棧，并標(biāo)記G。當(dāng)前位置指向G。
（5）頂點(diǎn)G沒(méi)有可以前進(jìn)的位置，則回退至F，將G出棧。當(dāng)前位置指向F。
（6）頂點(diǎn)F沒(méi)有可以前進(jìn)的位置，繼續(xù)回退至B，將F出棧。當(dāng)前位置指向B。
（7）頂點(diǎn)B可以前進(jìn)位置為C和E，選取E，輸出E，將E入棧，并標(biāo)記E。當(dāng)前位置指向E。
（8）頂點(diǎn)E的前進(jìn)位置為D，輸出D，將D入棧，并標(biāo)記D。當(dāng)前位置指向D。
（9）頂點(diǎn)D的前進(jìn)位置為C，輸出C，將C入棧，并標(biāo)記C。當(dāng)前位置指向C。
（10）頂點(diǎn)C沒(méi)有前進(jìn)位置，進(jìn)行回退至D，回退同時(shí)將C出棧。
（11）繼續(xù)執(zhí)行此過(guò)程，直至棧為空，以A為起始點(diǎn)的遍歷過(guò)程結(jié)束。若圖中仍有未被訪(fǎng)問(wèn)的頂點(diǎn)，則選取未訪(fǎng)問(wèn)的頂點(diǎn)為起始點(diǎn)，繼續(xù)執(zhí)行此過(guò)程。直至所有頂點(diǎn)均被訪(fǎng)問(wèn)。
性能分析
當(dāng)圖采用鄰接矩陣存儲(chǔ)時(shí)，由于矩陣元素個(gè)數(shù)為n 2 n^2n
2
，因此時(shí)間復(fù)雜度就是O ( n 2 ) O(n^2)O(n
2
)
當(dāng)圖采用鄰接表存儲(chǔ)時(shí)，鄰接表中只是存儲(chǔ)了邊結(jié)點(diǎn)(e條邊，無(wú)向圖也只是2e個(gè)結(jié)點(diǎn))，加上表頭結(jié)點(diǎn)為n（也就是頂點(diǎn)個(gè)數(shù)），因此時(shí)間復(fù)雜度為O(n+e)。
廣度優(yōu)先搜索
算法思想
思想：
從圖中某頂點(diǎn)v出發(fā)，在訪(fǎng)問(wèn)了v之后依次訪(fǎng)問(wèn)v的各個(gè)未曾訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)
然后分別從這些鄰接點(diǎn)出發(fā)依次訪(fǎng)問(wèn)它們的鄰接點(diǎn)，并使得“先被訪(fǎng)問(wèn)的頂點(diǎn)的鄰接點(diǎn)先于后被訪(fǎng)問(wèn)的頂點(diǎn)的鄰接點(diǎn)被訪(fǎng)問(wèn)，直至圖中所有已被訪(fǎng)問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪(fǎng)問(wèn)到。
如果此時(shí)圖中尚有頂點(diǎn)未被訪(fǎng)問(wèn)，則需要另選一個(gè)未曾被訪(fǎng)問(wèn)過(guò)的頂點(diǎn)作為新的起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)到為止。
實(shí)現(xiàn)廣度優(yōu)先遍歷的關(guān)鍵在于回放。
回溯與重放是完全相反的過(guò)程。
仍然以剛才的圖為例，按照廣度優(yōu)先遍歷的思想
我們先遍歷頂點(diǎn)0，然后遍歷其鄰接點(diǎn)1、3
接下來(lái)我們要遍歷更外圍的頂點(diǎn)，可是如何找到這些更外圍的頂點(diǎn)呢？我們需要把剛才遍歷過(guò)的頂點(diǎn)1,3按照順序回顧一遍，從頂點(diǎn)1發(fā)現(xiàn)了鄰接點(diǎn)2，從頂點(diǎn)3發(fā)現(xiàn)了鄰接點(diǎn)4。于是得到了順序2,4
再把剛才遍歷過(guò)的頂點(diǎn)2，4按照順序回顧一遍，分別得到鄰接點(diǎn)5，6
再把剛才遍歷過(guò)的頂點(diǎn)5，7按照順序回顧一遍，分別得到鄰接點(diǎn)7，7。7只需要打印一次，所以我們需要一個(gè)東西來(lái)標(biāo)記當(dāng)前頂點(diǎn)是否已經(jīng)訪(fǎng)問(wèn)過(guò)
在這里插入圖片描述
像這樣把遍歷過(guò)的頂點(diǎn)按照之前的遍歷順序重新回顧，就叫做重放。
同樣的，要實(shí)現(xiàn)重放也需要額外的存儲(chǔ)空間，可以利用隊(duì)列的先入先出特性來(lái)實(shí)現(xiàn)。
另外，還需要標(biāo)記某個(gè)點(diǎn)是否已經(jīng)被訪(fǎng)問(wèn)過(guò)，可以用數(shù)組、set等來(lái)實(shí)現(xiàn)
可以看出，廣度優(yōu)先搜索它其實(shí)就是一種“地毯式”層層推進(jìn)的搜索策略，即先查找離起始頂點(diǎn)最近的，然后是次近的，依次往外搜索。
算法特點(diǎn)
廣度優(yōu)先搜索類(lèi)似于樹(shù)的層次遍歷，是按照一種由近及遠(yuǎn)的方式訪(fǎng)問(wèn)圖的頂點(diǎn)。在進(jìn)行廣度優(yōu)先搜索時(shí)需要使用隊(duì)列存儲(chǔ)頂點(diǎn)信息。
圖解過(guò)程
無(wú)向圖的廣度優(yōu)先搜索
在這里插入圖片描述
（1）選取A為起始點(diǎn)，輸出A，A入隊(duì)列，標(biāo)記A，當(dāng)前位置指向A。
在這里插入圖片描述
（2）隊(duì)列頭為A，A出隊(duì)列。A的鄰接頂點(diǎn)有B、E，輸出B和E，并將B和E入隊(duì)，以及標(biāo)記B、E為已訪(fǎng)問(wèn)。當(dāng)前位置指向B。
在這里插入圖片描述
（3）隊(duì)列頭為B，B出隊(duì)列。B的鄰接頂點(diǎn)有C、D，輸出C、D，將C、D入隊(duì)列，并標(biāo)記C、D。當(dāng)前位置指向B。
在這里插入圖片描述
（4）隊(duì)列頭為E，E出隊(duì)列。E的鄰接頂點(diǎn)有D、F，但是D已經(jīng)被標(biāo)記，因此輸出F，將F入隊(duì)列，并標(biāo)記F。當(dāng)前位置指向E。
在這里插入圖片描述
（5）隊(duì)列頭為C，C出隊(duì)列。C的鄰接頂點(diǎn)有B、D，但B、D均被標(biāo)記。無(wú)元素入隊(duì)列。當(dāng)前位置指向C。
在這里插入圖片描述
（6）隊(duì)列頭為D，D出隊(duì)列。D的鄰接頂點(diǎn)有B、C、E，但是B、C、E均被標(biāo)記，無(wú)元素入隊(duì)列。當(dāng)前位置指向D。
在這里插入圖片描述
（7）隊(duì)列頭為F，F(xiàn)出隊(duì)列。F的鄰接頂點(diǎn)有G、H，輸出G、H，將G、H入隊(duì)列，并標(biāo)記G、H。當(dāng)前位置指向F。
在這里插入圖片描述
（8）隊(duì)列頭為G，G出隊(duì)列。G的鄰接頂點(diǎn)有F，但F已被標(biāo)記，無(wú)元素入隊(duì)列。當(dāng)前位置指向G。
在這里插入圖片描述
（9）隊(duì)列頭為H，H出隊(duì)列。H的鄰接頂點(diǎn)有F，但F已被標(biāo)記，無(wú)元素入隊(duì)列。當(dāng)前位置指向H。
在這里插入圖片描述
（10）隊(duì)列空，則以A為起始點(diǎn)的遍歷結(jié)束。若圖中仍有未被訪(fǎng)問(wèn)的頂點(diǎn)，則選取未訪(fǎng)問(wèn)的頂點(diǎn)為起始點(diǎn)，繼續(xù)執(zhí)行此過(guò)程。直至所有頂點(diǎn)均被訪(fǎng)問(wèn)。
有向圖的廣度優(yōu)先搜索
在這里插入圖片描述
（1）選取A為起始點(diǎn)，輸出A，將A入隊(duì)列，標(biāo)記A。
在這里插入圖片描述
（2）隊(duì)列頭為A，A出隊(duì)列。以A為尾的邊有兩條，對(duì)應(yīng)的頭分別為B、C，則A的鄰接頂點(diǎn)有B、C。輸出B、C，將B、C入隊(duì)列，并標(biāo)記B、C。
在這里插入圖片描述
（3）隊(duì)列頭為B，B出隊(duì)列。B的鄰接頂點(diǎn)為C，C已經(jīng)被標(biāo)記，因此無(wú)新元素入隊(duì)列。
在這里插入圖片描述
（4）隊(duì)列頭為C，C出隊(duì)列。C的鄰接頂點(diǎn)有E、F。輸出E、F，將E、F入隊(duì)列，并標(biāo)記E、F。
在這里插入圖片描述
（5）列頭為E，E出隊(duì)列。E的鄰接頂點(diǎn)有G、H。輸出G、H，將G、H入隊(duì)列，并標(biāo)記G、H。
在這里插入圖片描述
（6）隊(duì)列頭為F，F(xiàn)出隊(duì)列。F無(wú)鄰接頂點(diǎn)
在這里插入圖片描述
（7）隊(duì)列頭為G，G出隊(duì)列。G無(wú)鄰接頂點(diǎn)
在這里插入圖片描述
（8）隊(duì)列頭為H，H出隊(duì)列。H鄰接頂點(diǎn)為E，但是E已被標(biāo)記，無(wú)新元素入隊(duì)列
在這里插入圖片描述
（9）隊(duì)列為空，以A為起始點(diǎn)的遍歷過(guò)程結(jié)束，此時(shí)圖中仍有D未被訪(fǎng)問(wèn)，則以D為起始點(diǎn)繼續(xù)遍歷。選取D為起始點(diǎn)，輸出D，將D入隊(duì)列，標(biāo)記D
在這里插入圖片描述
（10）隊(duì)列頭為D，D出隊(duì)列，D的鄰接頂點(diǎn)為B，B已被標(biāo)記，無(wú)新元素入隊(duì)列
在這里插入圖片描述
（11）隊(duì)列為空，且所有元素均被訪(fǎng)問(wèn)，廣度優(yōu)先搜索遍歷過(guò)程結(jié)束。廣度優(yōu)先搜索的輸出序列為：A-B–C-E-F-G-H-D。
算法分析
我們來(lái)看下，廣度優(yōu)先搜索的時(shí)間、空間復(fù)雜度是多少呢？假設(shè)圖有V個(gè)頂點(diǎn)，E條邊
每個(gè)頂點(diǎn)都需要進(jìn)出一遍隊(duì)列，每個(gè)邊都會(huì)被訪(fǎng)問(wèn)一次。所以，廣度優(yōu)先搜索的時(shí)間復(fù)雜度是O(V+E)。當(dāng)然，對(duì)于一個(gè)連通圖來(lái)說(shuō)，也就是說(shuō)一個(gè)圖中的所有頂點(diǎn)都是連通的，，E 肯定要大于等于 V-1，所以，廣度優(yōu)先搜索的時(shí)間復(fù)雜度也可以簡(jiǎn)寫(xiě)為 O(E)
廣度優(yōu)先搜索的空間消耗主要在幾個(gè)輔助變量 visited 數(shù)組、queue 隊(duì)列上。這兩個(gè)存儲(chǔ)空間的大小都不會(huì)超過(guò)頂點(diǎn)的個(gè)數(shù)，所以空間復(fù)雜度是 O(V)。
總結(jié)
圖的遍歷主要就是這兩種遍歷思想，深度優(yōu)先搜索使用遞歸方式，需要棧結(jié)構(gòu)輔助實(shí)現(xiàn)。廣度優(yōu)先搜索需要使用隊(duì)列結(jié)構(gòu)輔助實(shí)現(xiàn)。在遍歷過(guò)程中可以看出，
對(duì)于連通圖，從圖的任意一個(gè)頂點(diǎn)開(kāi)始深度或廣度優(yōu)先遍歷一定可以訪(fǎng)問(wèn)圖中的所有頂點(diǎn)
對(duì)于非連通圖，從圖的任意一個(gè)頂點(diǎn)開(kāi)始深度或廣度優(yōu)先遍歷并不能訪(fǎng)問(wèn)圖中的所有頂點(diǎn)。
實(shí)現(xiàn)
深度優(yōu)先遍歷
當(dāng)圖采用鄰接矩陣進(jìn)行存儲(chǔ)，遞歸的實(shí)現(xiàn)操作：
#define MAXVBA 100
#define INFINITY 65536
typedef struct {
char vexs[MAXVBA];
int arc[MAXVBA][MAXVBA];
int numVertexes, numEdges;
} MGraph;
// 鄰接矩陣的深度有限遞歸算法
#define TRUE 1
#define FALSE 0
#define MAX 256
typedef int Boolean; // 這里我們定義Boolean為布爾類(lèi)型，其值為T(mén)RUE或FALSE
Boolean visited[MAX]; // 訪(fǎng)問(wèn)標(biāo)志的數(shù)組
void DFS(MGraph G, int i){
visited[i] = TRUE;
printf("%c", G.vexs[i]);
for (int j = 0; j G.numVertexes; ++j) {
if (G.arc[i][j] == 1 !visited[j]){
DFS(G, j); // 對(duì)為訪(fǎng)問(wèn)的鄰接頂點(diǎn)遞歸調(diào)用
}
}
}
// 鄰接矩陣的深度遍歷操作
void DFSTraverse(MGraph G){
int i;
// 初始化所有頂點(diǎn)狀態(tài)都是未訪(fǎng)問(wèn)過(guò)狀態(tài)
for (i = 0; i G.numVertexes; ++i) {
visited[i] = FALSE;
}
//防止圖為非聯(lián)通的情況，遍歷整個(gè)圖
for (i = 0; i G.numVertexes; ++i) {
if (!visited[i]){ // 若是連通圖，只會(huì)執(zhí)行一次
DFS(G, i);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
當(dāng)圖采用鄰接矩陣進(jìn)行存儲(chǔ)，棧的實(shí)現(xiàn)操作：
void DFS_Stack(MGraph G, int i)
{
int node;
int count = 1;
printf("%c ", G.vexs[i]); // 打印已訪(fǎng)問(wèn)頂點(diǎn)
visited[i] = TRUE;
node = i;
push(i); //開(kāi)始的節(jié)點(diǎn)入棧
while(count G.numVertexes) //still has node not visited
{
/* 所有被訪(fǎng)問(wèn)的節(jié)點(diǎn)依次入棧，只有node當(dāng)找不到下一個(gè)相連的節(jié)點(diǎn)時(shí)，才使用出棧節(jié)點(diǎn) */
for(j=0; j G.numVertexes; j++)
{
if(G.arc[node][j] == 1 visited[j] == FALSE)
{
visited[j] = TRUE;
printf("%c ", G.vexs[j]);
count++;
push(j); //push node j
break;
}
}
if(j == G.numVertexes) //與node相連的頂點(diǎn)均已被訪(fǎng)問(wèn)過(guò)，所以需要從stack里取出node的上一個(gè)頂點(diǎn)，再看該頂點(diǎn)的鄰接頂點(diǎn)是否未被訪(fǎng)問(wèn)
node = pop();
else //找到與node相連并且未被訪(fǎng)問(wèn)的頂點(diǎn)，
node = j;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
請(qǐng)?zhí)砑訄D片描述
鄰接表存儲(chǔ)下圖的深度優(yōu)先搜索代碼實(shí)現(xiàn)，與鄰接矩陣的思想相同，只是實(shí)現(xiàn)略有不同：
// 鄰接表的深度有限遞歸算法
#define TRUE 1
#define FALSE 0
#define MAX 256
typedef int Boolean; // 這里我們定義Boolean為布爾類(lèi)型，其值為T(mén)RUE或FALSE
Boolean visited[MAX]; // 訪(fǎng)問(wèn)標(biāo)志的數(shù)組
void DFS(GraphAdjList GL, int i)
{
EdgeNode *p;
visited[i] = TRUE;
printf("%c " GL-adjList[i].data);
p = GL-adjList[i].firstEdge;
while(p)
{
if( !visited[p-adjvex] )
{
DFS(GL, p-adjvex);
}
p = p-next;
}
}
// 鄰接表的深度遍歷操作
void DFSTraverse(GraphAdjList GL)
{
int i;
for( i=0; i GL-numVertexes; i++ )
{
visited[i] = FALSE; // 初始化所有頂點(diǎn)狀態(tài)都是未訪(fǎng)問(wèn)過(guò)狀態(tài)
}
for( i=0; i GL-numVertexes; i++ )
{
if( !visited[i] ) // 若是連通圖，只會(huì)執(zhí)行一次
{
DFS(GL, i);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
廣度優(yōu)先遍歷
請(qǐng)?zhí)砑訄D片描述
// 鄰接矩陣的廣度遍歷算法
void BFSTraverse(MGraph G)
{
int i, j;
Queue Q;
for( i=0; i G.numVertexes; i++ )
{
visited[i] = FALSE;
}
initQueue( Q );
for( i=0; i G.numVertexes; i++ )
{
if( !visited[i] )
{
printf("%c ", G.vex[i]);
visited[i] = TRUE;
EnQueue(Q, i);
while( !QueueEmpty(Q) )
{
DeQueue(Q, i);
for( j=0; j G.numVertexes; j++ )
{
if( G.art[i][j]==1 !visited[j] )
{
printf("%c ", G.vex[j]);
visited[j] = TRUE;
EnQueue(Q, j);
}
}
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
原文鏈接：;chksm=8c99e609bbee6f1fdb736f1bc45da5f6b6765ce190db68eac5a65ca22cc2694dc151f8db828fidx=1mid=2653197523scene=21sn=4edecca7392534177eef521511ff740b#wechat_redirect
下面是我修改了滴源碼，是基于一張簡(jiǎn)單的地圖，在地圖上搜索目的節(jié)點(diǎn)，依次用深度優(yōu)先、廣度優(yōu)先、Dijkstra算法實(shí)現(xiàn)。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Stack;
/**
*
* @author yinzhuo
*
*/
public class Arithmatic {
boolean flag = true;
// 一張地圖
static int[][] map = new int[][]// 地圖數(shù)組
{
{ 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0 },
{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0 },
{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } };
初級(jí)java工程師多數(shù)是剛畢業(yè)或者工作1,2年的新人。對(duì)于新人，面試中基礎(chǔ)問(wèn)題會(huì)問(wèn)道很多，因?yàn)橄纫疾爝@個(gè)人的基礎(chǔ)。
關(guān)于基礎(chǔ)類(lèi)的題目，我在面試初級(jí)java工程師的時(shí)候一般會(huì)問(wèn)下面兩大類(lèi)問(wèn)題，每類(lèi)5個(gè)題目，這樣下來(lái)我就基本可以了解這位工程師的程度了。
java基礎(chǔ)類(lèi)
面向?qū)ο蠡A(chǔ)類(lèi)
java基礎(chǔ)類(lèi)
1.描述一下java的訪(fǎng)問(wèn)修飾符，和它們之間的區(qū)別？
回答：如果可以回到出public，private，protected，就算是ok；回答出default的，加分。
2. int和Integer 區(qū)別？
回答：如果回答出Integer是int的包裝類(lèi)，就算ok；回答出其他的基本類(lèi)型和它們相應(yīng)的包裝類(lèi)，加分。
3.如何定義一個(gè)單精度浮點(diǎn)類(lèi)型的變量？
回答：float 變量名=1.2f ；回答出不加最后的f為雙精度浮點(diǎn)類(lèi)型，加分
4. equals和==的區(qū)別？
回答： equals是值比較（一般處理java開(kāi)發(fā)都會(huì)這么說(shuō)，算是ok的）而==是引用比較（或者對(duì)象比較）；回答equals是可以自定義的，加分
5.將一個(gè)數(shù)組作為參數(shù)傳遞到一個(gè)方法中，在方法中，數(shù)組內(nèi)的元素值被改變了，那么在方法外部，這個(gè)數(shù)組內(nèi)的元素是否也被改編了？
回答：是，因?yàn)閖ava方法中傳遞的是引用，就ok。如果回答中，將引用說(shuō)明了自己的理解，加分。
面向?qū)ο蠡A(chǔ)類(lèi)
1.重載和重寫(xiě)的區(qū)別？
回答：這個(gè)看個(gè)人理解，理解沒(méi)有什么大的偏差就ok；回答出多態(tài)相關(guān)的，加分。
2.構(gòu)造方法能不能重載？
回答：可以重載，ok；回答構(gòu)造方法時(shí)不能繼承的，所以如果要調(diào)用指定父類(lèi)構(gòu)造器就必須重寫(xiě)子類(lèi)構(gòu)造方法，加分。
3.抽象方法（abstract）是否可以被final、static、native修飾？
回答：都不可以，因?yàn)槌橄蠓椒ㄊ潜仨氉宇?lèi)實(shí)現(xiàn)的，final方法時(shí)不可以被重寫(xiě)的，static是父類(lèi)必須實(shí)現(xiàn)的方法，native是本地語(yǔ)言實(shí)現(xiàn)的方法。回答出封裝和繼承相關(guān)的，加分
4.當(dāng)父類(lèi)引用指向子類(lèi)對(duì)象的時(shí)候，子類(lèi)重寫(xiě)了父類(lèi)方法和屬性，那么當(dāng)訪(fǎng)問(wèn)屬性的時(shí)候，訪(fǎng)問(wèn)是誰(shuí)的屬性？調(diào)用方法時(shí)，調(diào)用的是誰(shuí)的方法？
回答：訪(fǎng)問(wèn)的是父類(lèi)的屬性，調(diào)用的是子類(lèi)的方法，ok；如果可以畫(huà)圖解釋的話(huà)，加分
5.抽象類(lèi)和接口有什么異同？
回答：一些類(lèi)定義上的區(qū)別，ok；回答在應(yīng)用過(guò)程中，如何根據(jù)業(yè)務(wù)定義接口，加很多分
最后，如果前面問(wèn)題回答的不錯(cuò)，會(huì)補(bǔ)充兩個(gè)編程習(xí)慣問(wèn)題。
1.在你寫(xiě)過(guò)的代碼中，你寫(xiě)過(guò)超過(guò)2層的循環(huán)嗎，怎么實(shí)現(xiàn)的？
回答：沒(méi)有，就算ok；如果回答有，聽(tīng)一下實(shí)現(xiàn)，如果原因說(shuō)不出來(lái)，扣分。
2.在你寫(xiě)過(guò)的代碼中，if語(yǔ)句最多嵌套了幾層，最多有多少分支，怎么實(shí)現(xiàn)的？
回答：3層以下，就算ok；如果回答3層以上，聽(tīng)一下實(shí)現(xiàn)，如果原因說(shuō)不出來(lái)，扣分。
4，5個(gè)分支，就算ok；如果回答5個(gè)分支以上，聽(tīng)一下實(shí)現(xiàn)，如果原因說(shuō)不出來(lái)，扣分。
最后兩個(gè)題其實(shí)比較陷阱，但是正是一個(gè)反向的思考才能了解面試者之前的工作狀態(tài)。
如果面試者在平日里就有好的習(xí)慣，自然不用擔(dān)心。
(1)DOM解析
DOM是html和xml的應(yīng)用程序接口(API)，以層次結(jié)構(gòu)（類(lèi)似于樹(shù)型）來(lái)組織節(jié)點(diǎn)和信息片段，映射XML文檔的結(jié)構(gòu)，允許獲取
和操作文檔的任意部分，是W3C的官方標(biāo)準(zhǔn)
【優(yōu)點(diǎn)】
①允許應(yīng)用程序?qū)?shù)據(jù)和結(jié)構(gòu)做出更改。
②訪(fǎng)問(wèn)是雙向的，可以在任何時(shí)候在樹(shù)中上下導(dǎo)航，獲取和操作任意部分的數(shù)據(jù)。
【缺點(diǎn)】
①通常需要加載整個(gè)XML文檔來(lái)構(gòu)造層次結(jié)構(gòu)，消耗資源大。
【解析詳解】
①構(gòu)建Document對(duì)象：
DocumentBuilderFactory dbf = DocumentBuilderFactory.newInstance();
DocumentBuilder db = bdf.newDocumentBuilder();
InputStream is = Thread.currentThread().getContextClassLoader().getResourceAsStream(xml文件);
Document doc = bd.parse(is);
②遍歷DOM對(duì)象
Document： XML文檔對(duì)象，由解析器獲取
NodeList： 節(jié)點(diǎn)數(shù)組
Node： 節(jié)點(diǎn)(包括element、#text)
Element： 元素，可用于獲取屬性參數(shù)
(2)SAX(Simple API for XML)解析
流模型中的"推"模型分析方式。通過(guò)事件驅(qū)動(dòng)，每發(fā)現(xiàn)一個(gè)節(jié)點(diǎn)就引發(fā)一個(gè)事件，事件推給事件處理器，通過(guò)回調(diào)方法
完成解析工作，解析XML文檔的邏輯需要應(yīng)用程序完成
【優(yōu)勢(shì)】
①不需要等待所有數(shù)據(jù)都被處理，分析就能立即開(kāi)始。
②只在讀取數(shù)據(jù)時(shí)檢查數(shù)據(jù)，不需要保存在內(nèi)存中。
③可以在某個(gè)條件得到滿(mǎn)足時(shí)停止解析，不必解析整個(gè)文檔。
④效率和性能較高，能解析大于系統(tǒng)內(nèi)存的文檔。
【缺點(diǎn)】
①需要應(yīng)用程序自己負(fù)責(zé)TAG的處理邏輯（例如維護(hù)父/子關(guān)系等），文檔越復(fù)雜程序就越復(fù)雜。
②單向?qū)Ш?，無(wú)法定位文檔層次，很難同時(shí)訪(fǎng)問(wèn)同一文檔的不同部分?jǐn)?shù)據(jù)，不支持XPath。
【原理】
簡(jiǎn)單的說(shuō)就是對(duì)文檔進(jìn)行順序掃描，當(dāng)掃描到文檔(document)開(kāi)始與結(jié)束、元素(element)開(kāi)始與結(jié)束時(shí)通知事件
處理函數(shù)(回調(diào)函數(shù))，進(jìn)行相應(yīng)處理，直到文檔結(jié)束
【事件處理器類(lèi)型】
①訪(fǎng)問(wèn)XML DTD：DTDHandler
②低級(jí)訪(fǎng)問(wèn)解析錯(cuò)誤：ErrorHandler
③訪(fǎng)問(wèn)文檔內(nèi)容：ContextHandler
【DefaultHandler類(lèi)】
SAX事件處理程序的默認(rèn)基類(lèi)，實(shí)現(xiàn)了DTDHandler、ErrorHandler、ContextHandler和EntityResolver接口，通常
做法是，繼承該基類(lèi)，重寫(xiě)需要的方法，如startDocument()
【創(chuàng)建SAX解析器】
SAXParserFactory saxf = SAXParserFactory.newInstance();
SAXParser sax = saxf.newSAXParser();
注：關(guān)于遍歷
①深度優(yōu)先遍歷(Depthi-First Traserval)
②廣度優(yōu)先遍歷(Width-First Traserval)
(3)JDOM(Java-based Document Object Model)
Java特定的文檔對(duì)象模型。自身不包含解析器，使用SAX
【優(yōu)點(diǎn)】
①使用具體類(lèi)而不是接口，簡(jiǎn)化了DOM的API。
②大量使用了Java集合類(lèi)，方便了Java開(kāi)發(fā)人員。
【缺點(diǎn)】
①?zèng)]有較好的靈活性。
②性能較差。
(4)DOM4J(Document Object Model for Java)
簡(jiǎn)單易用，采用Java集合框架，并完全支持DOM、SAX和JAXP
【優(yōu)點(diǎn)】
①大量使用了Java集合類(lèi)，方便Java開(kāi)發(fā)人員，同時(shí)提供一些提高性能的替代方法。
②支持XPath。
③有很好的性能。
【缺點(diǎn)】
①大量使用了接口，API較為復(fù)雜。
(5)StAX(Streaming API for XML)
流模型中的拉模型分析方式。提供基于指針和基于迭代器兩種方式的支持,JDK1.6新特性
【和推式解析相比的優(yōu)點(diǎn)】
①在拉式解析中，事件是由解析應(yīng)用產(chǎn)生的，因此拉式解析中向客戶(hù)端提供的是解析規(guī)則，而不是解析器。
②同推式解析相比，拉式解析的代碼更簡(jiǎn)單，而且不用那么多庫(kù)。
③拉式解析客戶(hù)端能夠一次讀取多個(gè)XML文件。
④拉式解析允許你過(guò)濾XML文件和跳過(guò)解析事件。
【簡(jiǎn)介】
StAX API的實(shí)現(xiàn)是使用了Java Web服務(wù)開(kāi)發(fā)（JWSDP）1.6，并結(jié)合了Sun Java流式XML分析器(SJSXP)-它位于
javax.xml.stream包中。XMLStreamReader接口用于分析一個(gè)XML文檔，而XMLStreamWriter接口用于生成一個(gè)
XML文檔。XMLEventReader負(fù)責(zé)使用一個(gè)對(duì)象事件迭代子分析XML事件-這與XMLStreamReader所使用的光標(biāo)機(jī)制
形成對(duì)照。
重慶分公司
重慶分公司
