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