圖說演算法使用JavaScript(三十四)

10-3  圖形走訪的訣竅

樹的追蹤目的是欲拜訪樹的每一個節點一次,可用的方法有中序法、前序法和後序法等三種。而圖形追蹤的定義如下:

一個圖形G=(V,E),存在某一頂點vEV,我們希望從v開始,經由此節點相鄰的節點兒去拜訪G中其他節點,這稱之為(圖形追蹤)。也就是從某一個頂點V1開始,走訪可以經由V1到達的頂點,接著在走訪下一個頂點直到全部的頂點走訪完畢為止。

在走訪的過程中可能會重複經過某些頂點及邊線。經由圖形的走訪可以判斷該圖形是否連通,並找出連通單元及路徑。圖形走訪的方法有兩種:(先深後廣走訪)及(先廣後深走訪)。

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料