ในวิทยาการคอมพิวเตอร์การท่องกราฟ (หรือที่เรียกว่าการค้นหากราฟ ) หมายถึงกระบวนการเยี่ยมชม (ตรวจสอบและ/หรืออัปเดต) แต่ละจุดยอดในกราฟการท่องกราฟดังกล่าวแบ่งประเภทตามลำดับที่เยี่ยมชมจุดยอด การท่องต้นไม้เป็นกรณีพิเศษของการท่องกราฟ

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

ดังนั้น โดยปกติแล้วจึงจำเป็นต้องจดจำว่าจุดยอดใดบ้างที่อัลกอริทึมได้สำรวจไปแล้ว เพื่อให้มีการกลับไปเยี่ยมชมจุดยอดเหล่านั้นให้น้อยที่สุดเท่าที่จะเป็นไปได้ (หรือในกรณีที่แย่ที่สุด เพื่อป้องกันไม่ให้การสำรวจดำเนินต่อไปอย่างไม่มีที่สิ้นสุด) อาจทำได้โดยการกำหนด "สี" หรือ "สถานะการเยี่ยมชม" ให้กับแต่ละจุดยอดของกราฟในระหว่างการสำรวจ จากนั้นจึงตรวจสอบและอัปเดตสถานะเหล่านั้นเมื่ออัลกอริทึมเยี่ยมชมแต่ละจุดยอด หากจุดยอดนั้นได้รับการเยี่ยมชมไปแล้ว อัลกอริทึมจะละเว้นจุดยอดนั้นและไม่ดำเนินการต่อ มิฉะนั้น อัลกอริทึมจะตรวจสอบ/อัปเดตจุดยอดและดำเนินการต่อตามเส้นทางปัจจุบัน

กราฟบางกรณีพิเศษนั้นบ่งบอกถึงการเยี่ยมชมจุดยอดอื่นๆ ในโครงสร้างของกราฟ และดังนั้นจึงไม่จำเป็นต้องบันทึกการเยี่ยมชมอย่างชัดเจนในระหว่างการสำรวจ ตัวอย่างที่สำคัญคือต้นไม้: ในระหว่างการสำรวจ อาจสันนิษฐานได้ว่าจุดยอด "บรรพบุรุษ" ทั้งหมดของจุดยอดปัจจุบัน (และจุดยอดอื่นๆ ขึ้นอยู่กับอัลกอริทึม) ได้ถูกเยี่ยมชมแล้ว การค้นหากราฟแบบค้นหา เชิงลึกและแบบค้นหาเชิงกว้างเป็นการดัดแปลงมาจากอัลกอริทึมแบบต้นไม้ โดยมีความแตกต่างหลักๆ คือการไม่มีจุดยอด "ราก" ที่กำหนดโดยโครงสร้าง และการเพิ่มโครงสร้างข้อมูลเพื่อบันทึกสถานะการเยี่ยมชมของการสำรวจ

หมายเหตุ — หากแต่ละจุดยอดในกราฟจะถูกสำรวจโดยอัลกอริทึมแบบต้นไม้ (เช่น DFS หรือ BFS) จะต้องเรียกใช้อัลกอริทึมอย่างน้อยหนึ่งครั้งสำหรับแต่ละส่วนที่เชื่อมต่อกันของกราฟ ซึ่งทำได้ง่ายๆ โดยการวนซ้ำผ่านจุดยอดทั้งหมดของกราฟ และเรียกใช้อัลกอริทึมกับจุดยอดแต่ละจุดที่ยังไม่ได้สำรวจเมื่อตรวจสอบแล้ว

การค้นหาแบบเจาะลึก (Depth-First Search หรือ DFS) เป็นอัลกอริทึมสำหรับการสำรวจกราฟจำกัด DFS จะเยี่ยมชมจุดยอดลูกก่อนที่จะเยี่ยมชมจุดยอดพี่น้อง กล่าวคือ มันจะสำรวจความลึกของเส้นทางใดเส้นทางหนึ่งก่อนที่จะสำรวจความกว้างของเส้นทางนั้น โดยทั่วไปแล้วจะใช้สแต็ก (มักจะเป็นสแต็กการเรียก ของโปรแกรม ผ่านการเรียกซ้ำ ) ในการนำอัลกอริทึมนี้ไปใช้

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

DFS เป็นพื้นฐานของอัลกอริธึมที่เกี่ยวข้องกับกราฟหลายอย่าง รวมถึงการเรียงลำดับเชิงโทโพโลยีและการทดสอบความเป็นระนาบ

• อินพุต : กราฟGและจุดยอดvของกราฟG
• ผลลัพธ์ : การกำหนดป้ายกำกับให้กับขอบในส่วนประกอบที่เชื่อมต่อกันของvว่าเป็นขอบการค้นพบและขอบย้อนกลับ

ขั้นตอน DFS( G , v ) คือ กำหนดป้ายกำกับvเป็น "สำรวจแล้ว" สำหรับขอบ ทั้งหมด eในG .incidentEdges( v ) ทำถ้าขอบeยังไม่ถูกสำรวจให้w ← G .adjacentVertex( v , e ) ถ้าจุดยอดwยังไม่ถูกสำรวจ ให้กำหนดป้าย กำกับeเป็นขอบที่ถูกค้นพบแล้ว เรียก DFS( G , w ) ซ้ำๆ มิฉะนั้นให้ ติดป้ายกำกับeเป็นขอบย้อนกลับ 

การค้นหาแบบกว้าง (Breadth-First Search หรือ BFS) เป็นอีกเทคนิคหนึ่งสำหรับการสำรวจกราฟจำกัด BFS จะเยี่ยมชมจุดยอดพี่น้องก่อนที่จะเยี่ยมชมจุดยอดลูก และ จะใช้ คิวในกระบวนการค้นหา อัลกอริทึมนี้มักใช้เพื่อหาเส้นทางที่สั้นที่สุดจากจุดยอดหนึ่งไปยังอีกจุดยอดหนึ่ง

• อินพุต : กราฟGและจุดยอดvของกราฟG
• ผลลัพธ์ : จุดยอดที่ใกล้ที่สุดกับvที่ตรงตามเงื่อนไขบางประการ หรือค่าว่างหากไม่มีจุดยอดดังกล่าวอยู่

ขั้นตอน BFS( G , v ) คือ สร้างคิวQ เพิ่มvลงในQ ทำเครื่องหมายv ในขณะที่Qยังไม่ว่างทำซ้ำw ← Q.dequeue () ถ้าwคือสิ่งที่เราต้องการ ให้ส่ง คืนw สำหรับขอบ ทั้งหมด eในG.adjacentEdges ( w ) ทำซ้ำ x ← G.adjacentVertex ( w , e ) ถ้าxยังไม่ได้ทำเครื่องหมายให้ ทำ เครื่องหมายx เพิ่ม x ลงในQ ส่งคืนค่า null 

การค้นหาแบบกว้าง (Breadth-first search) สามารถนำมาใช้แก้ปัญหาหลายอย่างในทฤษฎีกราฟได้ เช่น:

• การค้นหาจุดยอดทั้งหมดภายในส่วนประกอบที่เชื่อมต่อ กันหนึ่งส่วน ;
• อัลกอริทึมของเชนีย์ ;
• การหาเส้นทางที่สั้นที่สุดระหว่างจุดสองจุด;
• ทดสอบกราฟว่าแบ่งเป็นสองส่วนหรือไม่ ;
• การกำหนดหมายเลขตาข่ายด้วย อัลกอริทึม Cuthill–McKee ;
• อัลกอริทึมฟอร์ด-ฟุลเคอร์สันสำหรับการคำนวณ อัตรา การไหลสูงสุดในเครือข่ายการไหล
• การแปลงข้อมูลเป็นรูปแบบอนุกรม/การแปลงกลับจากรูปแบบอนุกรมของต้นไม้ไบนารี เทียบกับการแปลงข้อมูลเป็นรูปแบบอนุกรมในลำดับที่เรียงแล้ว (ซึ่งช่วยให้สามารถสร้างต้นไม้ขึ้นใหม่ได้อย่างมีประสิทธิภาพ)
• อัลกอริทึมการสร้างเขาวงกต ;
• อัลกอริทึม Flood Fillสำหรับทำเครื่องหมายบริเวณต่อเนื่องของภาพสองมิติหรืออาร์เรย์ n มิติ;
• การวิเคราะห์เครือข่ายและความสัมพันธ์

ปัญหาการสำรวจกราฟสามารถมองได้ว่าเป็นรูปแบบหนึ่งของการท่องกราฟ เป็นปัญหาแบบออนไลน์หมายความว่าข้อมูลเกี่ยวกับกราฟจะถูกเปิดเผยเฉพาะในระหว่างการทำงานของอัลกอริทึมเท่านั้น แบบจำลองทั่วไปมีดังนี้: กำหนดกราฟเชื่อมต่อG = ( V , E )ที่มีน้ำหนักขอบไม่เป็นลบ อัลกอริทึมเริ่มต้นที่จุดยอดใดจุดหนึ่ง และรู้ขอบขาออกทั้งหมดที่เข้ามาและจุดยอดที่ปลายขอบเหล่านั้น—แต่ไม่รู้มากกว่านั้น เมื่อเยี่ยมชมจุดยอดใหม่ ขอบขาออกทั้งหมดที่เข้ามาและจุดยอดที่ปลายขอบก็จะถูกทราบอีกครั้ง เป้าหมายคือการเยี่ยมชมจุดยอดทั้งnจุดและกลับไปยังจุดยอดเริ่มต้น แต่ผลรวมของน้ำหนักของการเดินทางควรน้อยที่สุดเท่าที่จะเป็นไปได้ ปัญหานี้ยังสามารถเข้าใจได้ว่าเป็นเวอร์ชันเฉพาะของปัญหาพนักงานขายเดินทาง (Travelling Salesman Problem)โดยที่พนักงานขายต้องสำรวจกราฟไปพร้อมๆ กับการเดินทาง

สำหรับกราฟทั่วไป อัลกอริทึมที่เป็นที่รู้จักดีที่สุดสำหรับทั้งกราฟแบบไม่มีทิศทางและแบบมีทิศทางคืออัลกอริทึมแบบโลภ (greedy algorithm) ที่เรียบง่าย :

• ในกรณีที่ไม่มีทิศทาง เส้นทางโลภจะยาวกว่าเส้นทางที่เหมาะสมที่สุด ไม่เกิน O (ln n ) เท่า ^{[ 1 ]}ขอบล่างที่ดีที่สุดที่ทราบสำหรับอัลกอริทึมออนไลน์แบบกำหนดได้คือ 10/3 ^{[ 2 ]}
  • กราฟแบบไม่มีทิศทางที่มีน้ำหนักหน่วยสามารถสำรวจได้ด้วยอัตราส่วนการแข่งขัน2 − ε [ ^{3 ] ซึ่งถือ เป็น}ขอบเขตที่แน่นหนาอยู่แล้วสำหรับกราฟ Tadpole ^{[ 4 ]}
• ในกรณีที่กำหนดทิศทาง เส้นทางแบบโลภจะยาวกว่าเส้นทางที่เหมาะสม ที่สุดไม่เกิน ( n − 1 ) เท่า ซึ่งตรงกับขอบเขตล่างของ n − 1 [ ^{5 ] ขอบเขต}ล่างของการแข่งขันที่คล้ายคลึงกันของΩ ( n ) ยังใช้ได้กับอัลกอริทึมแบบสุ่มที่ทราบพิกัดของแต่ละโหนดในการฝังตัวทางเรขาคณิต หากแทนที่จะเยี่ยมชมทุกโหนด ต้องค้นหาโหนด "สมบัติ" เพียงโหนดเดียว ขอบเขตของการแข่งขันจะเป็นΘ ( n ² ) บนกราฟแบบกำหนดทิศทางที่มีน้ำหนักหนึ่งหน่วย สำหรับทั้งอัลกอริทึมแบบกำหนดและแบบสุ่ม

ลำดับการท่องแบบสากลคือลำดับคำสั่งที่ประกอบการท่องกราฟสำหรับกราฟปกติ ใดๆ ที่มีจำนวนจุดยอดที่กำหนดไว้และสำหรับจุดยอดเริ่มต้นใดๆ การพิสูจน์เชิงความน่าจะเป็นถูกใช้โดย Aleliunas et al. เพื่อแสดงให้เห็นว่ามีลำดับการท่องแบบสากลที่มีจำนวนคำสั่งเป็นสัดส่วนกับO ( n ⁵ )สำหรับกราฟปกติใดๆ ที่มีจุดยอดn จุด ^{[ 6 ]}ขั้นตอนที่ระบุในลำดับนั้นสัมพันธ์กับโหนดปัจจุบัน ไม่ใช่ค่าสัมบูรณ์ ตัวอย่างเช่น ถ้าโหนดปัจจุบันคือv _jและv _jมี เพื่อนบ้าน dตัว ลำดับการท่องจะระบุโหนดถัดไปที่จะไปเยี่ยมชมv _{j +1}เป็น เพื่อนบ้าน ^{ลำดับที่}iของv _j โดย ที่ 1 ≤ i ≤ d

• การท่องกราฟหน่วยความจำภายนอก