ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 1"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
(หน้าที่ถูกสร้างด้วย '== อ.วัฒนา ==')
 
 
(ไม่แสดง 2 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน)
แถว 1: แถว 1:
== อ.วัฒนา ==
+
จริง ๆ แล้วรูปแบบการจัดเก็บยังคงใช้แบบเดิมได้ แต่ข้อมูลที่จัดเก็บจะลดลง เช่น ถ้าในกราฟเป็น undirected graph มี edge จาก vertex u ไป vertex v แล้ว ถ้าแทนในadjacency matrix จะมีเลขหนึ่งทั้งจาก row ที่ u ,column ที่ v และ row ที่ v, column ที่ u แต่ถ้าเป็น directed graph  จะมีเลขหนึ่งทั้งจาก row ที่ u ,column ที่ v เท่านั้น ส่วนการเก็บแบบ adjacency list ก็เหมือนกัน ถ้าเป็น undirected graph จะมี vertex v ใน list ของ vertex u และมี vertex u ใน list ของ vertex v แต่ถ้าเป็น directed graph จะมีแค่ vertex v ใน list ของ vertex u เท่านั้น ดังนั้นจะได้ว่า จำนวนเลขหนึ่งใน ตาราง adjacency matrix และจำนวน vertex ที่เป็นลูกใน adjacency list จะลดลงครึ่งหนึ่งจากกรณีที่เป็น directed graph นั่นเอง เพื่อให้เห็นข้อแตกต่างจะแสดงตัวอย่างการแทนดังรูปต่อไปนี้
 +
 
 +
[[ไฟล์:un1.JPG]]
 +
 
 +
[[ไฟล์:dir1.JPG]]

รุ่นแก้ไขปัจจุบันเมื่อ 03:36, 16 กันยายน 2552

จริง ๆ แล้วรูปแบบการจัดเก็บยังคงใช้แบบเดิมได้ แต่ข้อมูลที่จัดเก็บจะลดลง เช่น ถ้าในกราฟเป็น undirected graph มี edge จาก vertex u ไป vertex v แล้ว ถ้าแทนในadjacency matrix จะมีเลขหนึ่งทั้งจาก row ที่ u ,column ที่ v และ row ที่ v, column ที่ u แต่ถ้าเป็น directed graph จะมีเลขหนึ่งทั้งจาก row ที่ u ,column ที่ v เท่านั้น ส่วนการเก็บแบบ adjacency list ก็เหมือนกัน ถ้าเป็น undirected graph จะมี vertex v ใน list ของ vertex u และมี vertex u ใน list ของ vertex v แต่ถ้าเป็น directed graph จะมีแค่ vertex v ใน list ของ vertex u เท่านั้น ดังนั้นจะได้ว่า จำนวนเลขหนึ่งใน ตาราง adjacency matrix และจำนวน vertex ที่เป็นลูกใน adjacency list จะลดลงครึ่งหนึ่งจากกรณีที่เป็น directed graph นั่นเอง เพื่อให้เห็นข้อแตกต่างจะแสดงตัวอย่างการแทนดังรูปต่อไปนี้

Un1.JPG

Dir1.JPG