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