熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構之深度優先遍歷

2013-11-15 15:35:47  來源: 數據結構 

圖的遍歷

  圖的遍歷(Traversing Graph)從圖中某一頂點出發訪遍圖中其余頂點且使每一個頂點僅被訪問一次
  圖的遍歷有兩種方法深度優先搜索和廣度優先搜索
 
深度優先遍歷

  深度優先遍歷(DepthFirst Traversal)首先訪問出發點v並將其標記為已訪問過然後依次從v出發搜索v的每個鄰接點w若w未曾訪問過則以w為新的出發點繼續進行深度優先遍歷直至圖中所有和源點v有路徑相通的頂點(亦稱為從源點可達的頂點)均已被訪問為止若此時圖中仍有未訪問的頂點則另選一個尚未訪問的頂點作為新的源點重復上述過程直至圖中所有頂點均已被訪問為止
  深度優先搜索(DepthFirst Search)深度優先遍歷定義是遞歸的其特點是盡可能先對縱深方向進行搜索故這種搜索方法稱為深度優先搜索


  深度優先遍歷序列對圖進行深度優先遍歷時按訪問頂點的先後次序得到的頂點序列稱為該圖的深度優先遍歷序列或簡稱為DFS序列


From:http://tw.wingwit.com/Article/program/sjjg/201311/23651.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.