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