1703 問題 G: 數(shù)據(jù)結(jié)構(gòu)-圖的遍歷-BFS廣度優(yōu)先搜索（廣搜）
時間限制: 1s
內(nèi)存限制: 32MB 提交: 2063 解決: 1358
題目描述
廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷的過程。其過程為：假設(shè)從圖中的某頂點(diǎn)v出發(fā)，在訪問了v之后依次訪問v的各個未曾被訪問過的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問它們的鄰接點(diǎn)，并使“先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。若此時圖中尚有頂點(diǎn)未被訪問，則另選圖中一個未曾被訪問的頂點(diǎn)作為起始點(diǎn)。重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。
其算法可以描述如下：
在本題中，讀入一個無向圖的鄰接矩陣（即數(shù)組表示），建立無向圖并按照以上描述中的算法遍歷所有頂點(diǎn)，輸出遍歷頂點(diǎn)的順序。
輸入
輸入的第一行包含一個正整數(shù)n，表示圖中共有n個頂點(diǎn)。其中n不超過50。
以后的n行中每行有n個用空格隔開的整數(shù)0或1，對于第i行的第j個0或1，1表示第i個頂點(diǎn)和第j個頂點(diǎn)有直接連接，0表示沒有直接連接。當(dāng)i和j相等的時候，保證對應(yīng)的整數(shù)為0。
輸入保證鄰接矩陣為對稱矩陣，即輸入的圖一定是無向圖。
輸出
只有一行，包含n個整數(shù)，表示按照題目描述中的廣度優(yōu)先遍歷算法遍歷整個圖的訪問頂點(diǎn)順序。每個整數(shù)后輸出一個空格，并請注意行尾輸出換行。
樣例輸入
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)擊這里了解課程詳情
比賽公告
暫無……