การแทนกราฟด้วยรายการโยงประชิด
การใช้รายการโยงเพื่อประหยัดเนื้อที่ในการเก็บข้อมูลของกราฟมีผู้นิยมใช้กันแพร่หลาย ตัวอย่างเช่น โครงสร้างเครือข่ายระบบคอมพิวเตอร์เพื่อควบคุมการจราจรของเมืองหลวง การสร้างโปรแกรมเพื่อควบคุมปริมาณการจราจรบนถนนหลวง โดยโหนดของกราฟใช้แทนสี่แยก เส้นเชื่อมใช้แทนถนน น้ำหนักของเส้นเชื่อมใช้แทนปริมาณการจราจร เส้นเชื่อมสำหรับถนนเดินทางเดียวนั้นมีน้ำหนัก 1 ตัว เส้นเชื่อมสำหรับถนนที่มีรถวิ่งสวนทางมีน้ำหนัก 2 ตัว ในกรณีนี้ถ้าใช้เมตริกซ์ประชิดแล้ว สำหรับกราฟที่มี n โหนดเขียนโดยใช้เมทริกซ์ขนาด N แต่ถ้าใช้รายการโยง โปรแกรมใช้โหนดเท่าที่จำเป็นเท่านั้น คือ ในกราฟประกอบด้วยเส้นเชื่อมที่ใช้เก็บข้อมูลเท่านั้น
เมื่อพิจารณากราฟแล้วพบว่า มีวิถีเข้าไปยังรายชื่อโหนดของแต่ละโหนดในกราฟ การเข้าไปที่โหนด i โดยชี้ไปที่รายการโยงซึ่งแทนโหนดที่เชื่อมกับโหนด i อันที่จริงระเบียนที่นำมาประกอบเป็นรายการโยง นั้นมี 2 เขต คือ
1. ชื่อโหนด
2. ตัวชี้ที่เชื่อมกับโหนดประชิดในรายการ
รูปที่ 12 กราฟไม่ระบุทิศทาง
เมื่อเขียนรายชื่อโหนดแทนกราฟไม่ระบุทิศทางของรูปที่ 12ได้ดังนี้
รูปที่ 13 รายการโยง ใช้เก็บข้อมูลของกราฟไม่ระบุทิศทาง
รูปที่ 14 กราฟระบุทิศทาง
รูปที่ 15 รายการโกง ใช้เก็บข้อมูลของกราฟระบุทิศทาง
0 ความคิดเห็น:
แสดงความคิดเห็น