การค้นหาในแนวลึก ( Depth – First Search)

การค้นหาในแนวลึก ( Depth – First Search)

การค้นหาแบบนี้จะค้นหาเวอร์เทกซ์แบบลงลึกก่อน โดยเริ่มจากจุดเริ่มต้นแล้วลงลึกไปยังเวอร์เทกซ์ข้างเคียงในระดับถัดไปเรื่อยๆ จนกว่าจะพบ หากค้นหาจนทั่วทุกเวอร์เทกซ์แล้วไม่พบก็สามารถแจ้งผลให้ทราบได้

โครงสร้างกราฟจะแตกต่างจากโครงสร้างต้นไม้ เราสามารถเข้าถึงทุกโหนดในต้นไม้โดยเริ่มจากรูท แต่ในกราฟ เวอร์เทกซ์ทุกเวอร์เทกซ์ไม่จำเป็นต้องมีเส้นทางถึงกันหมด

ตัวอย่าง  การท่องเข้าไปในกราฟมีทิศทาง

จากเวอร์เทกซ์  A   จะไปยังเวอร์เทกซ์  B  C  D หรือ E  ได้  แต่จะไปยัง เวอร์เทกซ์  F ไม่ได้

จากเวอร์เทกซ์  B   จะไปยังเวอร์เทกซ์อื่นใดไม่ได้  เพราะเป็นกราฟมีทิศทาง

จากเวอร์เทกซ์  C   จะไปยังเวอร์เทกซ์  C  E  B ได้  แต่จะไปยังเวอร์เทกซ์ A หรือ D ไม่ได้

อัลกอริทึมเพื่อการค้นหาในแนวลึก

สรุปเป็นแนวทางได้ดังนี้

found FALSE

clearStack (stack)

push (stack, startVertex)

do

pop (stack, vertex)

if (vertex = = targetVertex)

print vertex

found TRUE

else

print vertex

getAdjacencyVertices

push (stack, adjacency vertices)

while ((NOT emptyStack (stack)) AND (NOT found))

if (NOT found)

print “No path to target vertex”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s