418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 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 นั่นเอง