การแวะผ่านกราฟ
คือ การที่แวะไปที่ทุกๆ โหนดของกราฟ สำหรับเทคนิคในการแวะผ่านมี 2 แบบ
1.แนวกว้าง (Breadth first traversal)
2. แนวลึก (Depth first traversal)
หลักการทำงานของการแวะผ่านกราฟนั้นคือ หารที่ไปแต่ละโหนด 1 ครั้ง สำหรับการที่โหนดไปที่ต้นไม้นั้นมีเพียง 1 วิถีจากรากไปยังโหนด แต่สำหรับในกราฟนั้นมีหลายวิถีระหว่างคู่ของโหนด ดังนั้นเพื่อป้องกันการที่ไปโหนดซ้ำซ้อนจึงจำเป็นต้องทำเครื่องหมาย (เลเบล) บริเวณโหนดที่ได้รับการแวะผ่านเสร็จเรียบร้อยแล้วจึงไม่สามารถไปแวะได้อีก นอกจากนี้ยังมีการทำเครื่องหมายให้กับเส้นเชื่อมที่ตามหลังมา สำหรับเส้นเชื่อมที่ทำเครื่องหมายไปแล้วไม่สามารถใช้เป็นวิถีอีก ดังนั้นเลเบลสามารถเก็บใช้ข้อมูลของโหนด หรือเส้นเชื่อมว่าได้รับการแวะผ่านแล้ว
การแวะผ่านแนวกว้าง (Breadth first traversal) วิธีการนี้ทำขึ้นโดยเลือก 1 โหนด เป็นจุดเริ่มต้น หลังจากนั้นไปแวะผ่านและทำเครื่องหมายที่โหนดนั้น ต่อมาโหนดอื่นที่เชื่อมต่อกับโหนดนั้นจะได้รับการแวะผ่าน และทำเครื่องหมายตามลำดับ ในที่สุดโหนดที่ยังไม่ได้แวะผ่านไปแล้ว ได้ทำการแวะผ่านและทำเครื่องหมาย จนกระทั้งทุกๆ โหนดในกราฟได้รับการแวะผ่านครบถ้วน
รูปที่ 16 กราฟน้ำหนักมีทิศทาง
การแวะผ่านในแนวกว้างของกราฟในรูปที่ 16 นั้น จะไปที่โหนดแบบเรียงตามลำดับ ดังนี้คือ 1,2,3,4,5,6,8,7 หรือตามที่โหนดเรียงตามลำดับอีกแบบหนึ่ง ดังนี้คือ 1,3,2,6,5,4,7,8อัลกอริทึมการแวะผ่าน ใช้คิวเพื่อเก็บโหนดในกราฟแต่ละระดับที่ได้แวะผ่านไปแวะผ่านโหนดที่นำไปเก็บไว้นั้น จะได้รับการดำเนินงานทีละโหนดและโหนดประชิดก็ได้ไปการแวะผ่าน จนกระทั่งทุกโหนดได้รับการแวะผ่าน เงื่อนไขจบการทำงานของอัลกอริทึมนี้ คือการที่คิวว่าง
การแวะผ่านแนวลึก
การแวะผ่านแนวลึก (Depth first traversal) ทำงานคล้ายกับการแวะผ่านทีละระดับของต้นไม้ โดยกำหนดวิถีแรก จากรากลงไปที่ใบและอีกทางหนึ่งจากรากไปที่ใบจนกระทั้งมีการแวะผ่านหมดทุกโหนด
รูปที่ 17 กราฟน้ำหนักมีทิศทาง
