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

數據結構之生成樹

2013-11-15 15:34:02  來源: 數據結構 
    生成樹(Spanning Tree)從連通圖的任何一個頂點出發進行遍歷遍歷過程中經過的邊加上圖的所有頂點構成的子圖稱為圖的生成樹
  深度優先生成樹由深度優先搜索得到的生成樹簡稱為DFS生成樹
  廣度優先生成樹由廣度優先搜索得到的生成樹簡稱為BFS生成樹


  在對無向圖進行遍歷時對於連通圖僅需從圖中任一頂點出發進行深度優先搜索或廣度優先搜索便可訪問到圖中所有頂點對非連通圖則需從多個頂點出發進行搜索而每一次從一個新的起始點出發進行搜索過程中得到的頂點訪問序列恰為其各個連通分量中的頂點集  

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