การแสดงกราฟด้วย Adjacency List เป็นการแสดงผลแบบ linked list ในการแสดงผลนี้เรามีอาร์เรย์ของลิสต์ ขนาดอาร์เรย์คือ V โดย V คือจำนวนจุดยอด กล่าวอีกนัยหนึ่ง เรามีอาร์เรย์เก็บ V ลิสต์ที่แตกต่างกัน หากหัวลิสต์คือจุดยอด u หมายความว่าจะเก็บจุดยอดติดจัตุรัสทั้งหมดของ u
ความซับซ้อนของการแสดงผลด้วย Adjacency List
การแสดงผลนี้ใช้พื้นที่ O(V+2E) สำหรับกราฟไม่มีทิศทาง และ O(V+E) สำหรับกราฟมีทิศทาง หากจำนวนเส้นเชื่อมเพิ่มขึ้น พื้นที่ที่ต้องการก็จะเพิ่มขึ้นตามไปด้วย
Input:
Output:
อัลกอริทึม
add_edge(adj_list, u, v)
Input: จุดยอด u และ v ของเส้นเชื่อม {u,v} และ adjacency list
Output: Adjacency List ของกราฟ G
Begin
Append v ลงในลิสต์ที่ index u
Append u ลงในลิสต์ที่ index v
End
ตัวอย่างโค้ด
#include <iostream>
#include <list>
#include <iterator>
using namespace std;
void displayAdjList(list<int> adj_list[], int v) {
for(int i = 0; i<v; i++) {
cout << i << "--->";
list<int> :: iterator it;
for(it = adj_list[i].begin(); it != adj_list[i].end(); ++it) {
cout << *it << " ";
}
cout << endl;
}
}
void add_edge(list<int> adj_list[], int u, int v) {
// เพิ่ม v ลงในลิสต์ u และ u ลงในลิสต์ v
adj_list[u].push_back(v);
adj_list[v].push_back(u);
}
main(int argc, char* argv[]) {
int v = 6; // มี 6 จุดยอดในกราฟ
// สร้างอาร์เรย์ของลิสต์ขนาด 6
list<int> adj_list[v];
add_edge(adj_list, 0, 4);
add_edge(adj_list, 0, 3);
add_edge(adj_list, 1, 2);
add_edge(adj_list, 1, 4);
add_edge(adj_list, 1, 5);
add_edge(adj_list, 2, 3);
add_edge(adj_list, 2, 5);
add_edge(adj_list, 5, 3);
add_edge(adj_list, 5, 4);
displayAdjList(adj_list, v);
}
ผลลัพธ์
0--->4 3 1--->2 4 5 2--->1 3 5 3--->0 2 5 4--->0 1 5 5--->1 2 3 4
