Google         youtube            psv            สพม.11

กราฟแบบไดเร็กทอรี่โหนด

   เทคนิคการใช้แมตทริกติดกันเป็นกราฟ มีความต้องการเก็บข้อมูลเกี่ยวกับเอจครบทุกรูปแบบระหว่างโหนดที่เป็นไปได้ เมื่อกราฟมีN โหนดความเป็นไปได้จะมีเอจเชื่อมกันเท่ากับ N2  ซึ่งทำให้มีค่า 0 เป็นจำนวนมาก ดังนั้น การนำลิ้งค์ลิสต์มาใช้เป็นกราฟจึงมีความเหมาะสมกว่า ซึ่งจะมีเฉพาะเอจที่เชื่อมต่อกันเท่านั้น กานใช้โครงสร้างลิ้งค์ลิสต์เป็นกราฟจะมี 2 รูปแบบ คือ แบบไดเร็กทอรี่โหนด(Node Directory) และแบบมัลติลิสต์ (Multi-List) ในหัวข้อถัดไป

กราฟแบบได เร็กทอรี่โหนดประกอบด้วยสองส่วน คือ ไดเร็กทอรี่ (Directory) และเซ็ตของลิ้งค์ลิสต์ แต่ละค่าในไดเร็กทอรี่มีสำหรับแต่ละโหนดที่อยู่ในกราฟ ค่าในไดเร็กทอรี่สำหรับโหนด i  จะชี้ไปยังลิ้งค์ลิสต์ที่เชื่อมต่อไปยังโหน ดที่เชื่อมต่อกับโหนด i ลิ้งค์ลิสต์เป็นเรคคอร์ดประกอบด้วยสองเขตข้อมูล คือ ค่าความแตกต่างของแต่ละโหนด (Node Identifier) เป็นหมายเลขโหนดและตัวเชื่อมชี้ไปยังสมาชิกถัดไปในลิสต์ ดังนั้น ไดเร็กทอรี่จะหมายถึงโหนดส่วนลิ้งค์ลิสต์หมายถึงเอจ

เป็นกราฟไม่มีทิศทางเมื่อนำมาเขียนเป็นแบบไดเร็กทอรี่โหนดจะได้เป็นรูปที่ 10.11

กราฟแบบไดเร็กทอรี่โหนดที่ได้จากกราฟไม่มีทิศทางในรูปที่ 10.7

จะได้ว่ากราฟไม่มีทิศทางที่มีออเดอร์เท่ากับ N และมีเอจเท่ากับ E ค่าที่มีในไดเร็กทอรี่เท่ากับ N และค่าในลิ้งค์ลิสต์เท่ากับ 2*E

เมื่อ ใช้เป็นกราฟทิศทาง จากรูปที่ 10.8 นำมาเขียนเป็นแบบไดเร็กทอรี่โหนดก็จะได้เป็นรูปที่ 10.12 ซึ่งกราฟทิศทางที่มีออเดอร์เท่ากับ N และเอจเท่ากับ E ค่าที่มีในไดเร็กทอ รี่เท่ากับ N และค่าในลิ้งค์ลิสต์เท่ากับ E

กราฟแบบไดเร็กทอรี่โหนดที่ได้จากกราฟทิศทางในรูปที่ 10.8

เอจมีน้ำหนัก

การ ใช้กราฟแบบไดเร็กทอรี่โหนดกับเอจมีน้ำหนัก โครงสร้างข้อมูลจะต้องมีการจัดเก็บน้ำหนักของเอจ ดังในตัวอย่างกราฟทิศทางในรูปที่ 10.13 ซึ่งแต่ละโหนดเปลี่ยนเป็นรูปวงกลมที่มีชื่อกำหนดไว้ภายใน แต่ละเอจมีน้ำหนักกำหนดเป็นกราฟแสดงกิจกรรมเป็นตัวเลข โดยแต่ละโหนดเป็นเหตุการณ์ (Event) และแต่ละเอจเป็นกิจกรรมที่ต้องทำซึ่งมี น้ำหนักที่หมายถึงเวลากราฟชนิดนี้จะนำมาใช้ในการบริหารจัดการโครงการ

กราฟทิศทางกับเอจมีน้ำหนักที่ใช้ในการบริหารจัดการโครงการ

เมื่อ นำมาเขียนเป็นแบบไดเร็กทอรี่โหนดจะได้เป็นรูปที่ 10.14 โดยแต่ละเรคคอร์ดของเอจประกอบด้วยค่าความแตกต่างหรือหมายเลขของแต่ละโหน ดปลายทาง น้ำหนักของเอจและตัวเชื่อมที่ชี้ไปยังเอจถัดไป

กราฟแบบไดเร็กทอรี่โหนดที่ได้จากกราฟทิศทางในรูปที่ 10.13

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s