題目 1702:
數(shù)據(jù)結(jié)構(gòu)-圖的遍歷-DFS深度優(yōu)先搜索(深搜)
時(shí)間限制: 2s
內(nèi)存限制: 96MB 提交: 3288 解決: 2060
題目描述
深度優(yōu)先搜索遍歷類似于樹(shù)的先根遍歷，是樹(shù)的先根遍歷的推廣。其過(guò)程為：假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)未曾被訪問(wèn)，則深度優(yōu)先搜索可以從圖中的某個(gè)頂點(diǎn)v出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次從v的未被訪問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。
其算法可以描述如下：
在本題中，讀入一個(gè)無(wú)向圖的鄰接矩陣（即數(shù)組表示），建立無(wú)向圖并按照以上描述中的算法遍歷所有頂點(diǎn)，輸出遍歷頂點(diǎn)的順序。
輸入格式
輸入的第一行包含一個(gè)正整數(shù)n，表示圖中共有n個(gè)頂點(diǎn)。其中n不超過(guò)50。
以后的n行中每行有n個(gè)用空格隔開(kāi)的整數(shù)0或1，對(duì)于第i行的第j個(gè)0或1，1表示第i個(gè)頂點(diǎn)和第j個(gè)頂點(diǎn)有直接連接，0表示沒(méi)有直接連接。當(dāng)i和j相等的時(shí)候，保證對(duì)應(yīng)的整數(shù)為0。
輸入保證鄰接矩陣為對(duì)稱矩陣，即輸入的圖一定是無(wú)向圖。
輸出格式
只有一行，包含n個(gè)整數(shù)，表示按照題目描述中的深度優(yōu)先遍歷算法遍歷整個(gè)圖的訪問(wèn)頂點(diǎn)順序。每個(gè)整數(shù)后輸出一個(gè)空格，并請(qǐng)注意行尾輸出換行。
樣例輸入
4 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 0
樣例輸出
0 1 3 2
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情