程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj2386--圖的遍歷

poj2386--圖的遍歷

編輯:C++入門知識

題意描述:
要求輸出圖中連通分支的個數。
最簡單的圖遍歷問題,題目雖然簡單,卻考察了最基本的遍歷知識。
圖的常見遍歷方式有兩種:深度優先遍歷和廣度優先遍歷,他們的作用是將圖中的每個點都訪問一遍,只不過是順序不同。
如果把圖中的每條邊長都相等(比如都是1)的話,深度優先遍歷的過程是:
1.任意選定一個點p0作為遍歷的起點
2.從未訪問節點中任選一個距離p0最近的點進行訪問,並標記該點被訪問過
3.重復第2步,直到該連通分支中的所有節點都被訪問過
說的形象一點,深度優先遍歷就是按照層次的順序訪問節點,每一層中的節點與p0有相同的距離。先訪問第一層,再訪問第二層,……
深度優先遍歷過程就是盡可能深的去訪問節點,具體過程為:
1.任意選定一個點p0作為遍歷的起點
2.當訪問到某一個節點p1時,如果p1下面有未被遍歷的子節點,我們就接著訪問p1的某一個未被遍歷子節點,並標記該子節點被訪問過,
3.如果p1不存在未被訪問的子節點,我們就退回到p1的父節點,並執行第2步
4.執行第2、3步,直到所有節點被訪問過。
(遞歸過程真心不好描述啊~~~)
大家也看出來了,深度優先遍歷的是一個遞歸的過程,因此很容易想到要用到棧這種數據結構,具體實現的時候可以用遞歸,也可以用棧。看個人習慣了。
廣度優先遍歷實現就要用到隊列了。
以下是poj2386不同實現方式的代碼
深度優先遍歷,遞歸實現:
深度優先遍歷,棧實現:
廣度優先遍歷:

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved