กราฟ (Graph) เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น อีกชนิดหนึ่ง กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อน
กราฟ เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นที่ประกอบ ด้วยกลุ่มของสิ่งสองสิ่งคือ
1 โหนด Nodes หรือ เวอร์เทกซ์Vertexes
2 เส้นเชื่อมระหว่างโหนด เรียก เอ็จ Edges
โหนดสองโหนดในกราฟแบบไม่มีทิศทางถือว่าเป็นโหนดที่ใกล้กัน Adjacent ถ้ามีเอ็จเชื่อมจากโหนดที่หนึ่งไปโหนดที่สอง กราฟแบบมีทิศทาง เป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง
ในการปฏิบัติการกับโครงสร้างกราฟ สิ่งที่ต้องการจัดเก็บ จากกราฟโดยทั่วไปก็คือ เอ็จ การจัดเก็บกราฟด้วยวิธีเก็บโหนดและพอยน์เตอร์นี้ยุ่งยาก ในการจัดการเพิ่มขึ้นเนื่องจากต้องเก็บโหนดและพอยน์เตอร์ในแถวลำดับ 2 มิติ อย่างไรก็ตามทั้งสองวิธีไม่เหมาะกับกราฟที่มีการเปลี่ยนแปลง ตลอดเวลา ควรใช้ในกราฟที่ไม่มีการเปลี่ยนแปลงตลอดการใช้งาน
การท่องไปในกราฟgraph traversalคือกระบวนการเข้าไปเยือนโหนดในกราฟ มี2วิธีคือ
1. การท่องแบบกว้าง
2. การท่องแบบลึก
DTS9-02/09/2552
ไม่มีความคิดเห็น:
แสดงความคิดเห็น