อัลกอริทึมพื้นฐานของกราฟ

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