ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 1"
ไปยังการนำทาง
ไปยังการค้นหา
Aoy (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย '== อ.วัฒนา ==') |
Aoy (คุย | มีส่วนร่วม) |
||
(ไม่แสดง 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 นั่นเอง เพื่อให้เห็นข้อแตกต่างจะแสดงตัวอย่างการแทนดังรูปต่อไปนี้