กราฟ (Graph)เป็นโครงสร้างข้อมูลที่นำไปใช้เกียวกับการแก้ปัญหาในงานที่ซับซ้อน กราฟจะประกอบด้วย 2 สิ่งคือ
-โหนด Nodes หรือเวอร์เทกซ์
-เส้นเชื่อมระหว่างโหนด เรียกว่า เอ็จ และเอ็จของกราฟจะแบ่งเป็น 2 แบบคือ แบบที่มีทิศทางและไม่มีทิศทาง
1.กราฟแบบไม่มีทิศทาง เป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง (Empty Graph)แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด หรือเชื่อมตัวเอง เอ็จไม่มีทิศทางกำกับ ลำดับของการเชื่อมต่อกันไม่สำคัญ นั่นคือไม่มีโหนดใดเป็นโหนดแรก (First Node) หรือไม่มีโหนดเริ่มต้น และไม่มีโหนดใดเป็นโหนดสิ้นสุด
โหนดสองโหนดในกราฟแบบไม่มีทิศทางถือว่าเป็นโหนดที่ใกล้กัน (Adjacent) ถ้ามีเอ็จเชื่อมจากโหนดที่หนึ่งไปโหนดที่สอง
กราฟ (ก) แสดงกราฟที่มีลักษณะ ต่อเนื่อง(Connected) เป็นกราฟที่มีเส้นทางเชื่อมจากโหนดใด ๆ ไปยังโหนดอื่นเสมอ
กราฟ (ข) แสดงกราฟที่มีลักษณะเป็น วีถี(Path) มีเส้นทางเชื่อมไปยังโหนดต่าง ๆ อย่างเป็น
ลำดับ โดยแต่ละโหนดจะเป็นโหนดที่ใกล้กันกับโหนดที่อยู่ถัดไป
กราฟ (ค) แสดงกราฟที่เป็นวัฎจักร (Cycle)ซึ่งต้องมีอย่างน้อย 3 โหนด ที่โหนดสุดท้ายต้องเชื่อมกับโหนดแรก
กราฟ (ง) แสดงกราฟที่มีลักษณะ ไม่ต่อเนื่อง(Disconnected) เนื่องจากไม่มีเส้นทางเชื่อมจากโหนด 3 ไปยังโหนดอื่นเลย
กราฟ (จ) แสดงกราฟที่เป็นทรี โดยทรีเป็นกราฟที่ต่อเนื่อง ไม่มีทิศทาง และไม่เป็นวัฏจักร
2.กราฟแบบมีทิศทาง เป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกรา-าง (Empty Graph) แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด เอ็จมีทิศทางกำกับแสดงลำดับของการเชื่อมต่อกัน โดยมีโหนดเริ่ต้น(Source Node) และ โหนดสิ้นสุด (Target Node)รูปแบบต่าง ๆ ของกราฟแบบมีทิศทางเหมือนกับรูปแบบ ของกราฟไม่มีทิศทาง ต่างกันตรงที่กราฟแบบนี้จะมีทิศทางกำกับด้วยเท่านั้น
การแทนกราฟในหน่วยความจำในการปฏิบัติการกับโครงสร้างกราฟ สิ่งที่ต้องการจัดเก็บ จากกราฟโดยทั่วไปก็คือ เอ็จ ซึ่งเป็นเส้นเชื่อมระหว่างโหนดสองโหนด มีวิธีการ จัดเก็บหลายวิธี วิธีที่ง่ายและตรงไปตรงมาที่สุดคือ การเก็บเอ็จในแถวลำดับ 2 มิติ
การท่องไปในกราฟ คือการเข้าไปเยื่อนโหนดที่อยู่ในกราฟโดยหลักการทำงานแต่ล่ะโหนดจะมีการเยื่อนเพียงครั้งเดียวแต่จะมีเทคนิคการท่องอยู่ 2 แบบคือ
1.การท่องแบบกว้าง จะเริ่มที่โหนดแรกต่อมาจะไปเยื่อนโหนดที่อยู่ใกล้กับโหนดแรกจนครบทุกโหนด
2.การท่องแบบลึก การท่องไปที่ระลำดับต่อไปเยื่อนไปทุกโหนดจนสุดและทำการย้อนกลับตามแนวเดิมที่ท่องไปจนครบทุกโหนด
DTH 09-02-09-2552
ไม่มีความคิดเห็น:
แสดงความคิดเห็น