Adjacency Matrix ของกราฟเป็นเมทริกซ์สี่เหลี่ยมขนาด V x V โดย V คือจำนวนจุดยอดของกราฟ G ในเมทริกซ์นี้ ทั้งสองด้านจะมีจุดยอด V จุด ถ้ากราฟมีเส้นเชื่อมจากจุดยอด i ไปยัง j ใน Adjacency Matrix ที่แถว i และคอลัมน์ j จะเป็น 1 (หรือค่าที่ไม่ใช่ศูนย์สำหรับกราฟถ่วงน้ำหนัก) มิฉะนั้นจะเป็น 0
ความซับซ้อนของการแสดงผลด้วย Adjacency Matrix:
การแสดงผลด้วย Adjacency Matrix ใช้พื้นที่ O(V²) ขณะคำนวณ เมื่อกราฟมีจำนวนเส้นเชื่อมสูงสุดและต่ำสุด ในทั้งสองกรณีพื้นที่ที่ต้องการจะเท่ากัน
Input:
Output:
| 0 |
1 |
2 |
3 |
4 |
5 |
|
|---|---|---|---|---|---|---|
| 0 |
0 |
0 |
0 |
1 |
1 |
0 |
| 1 |
0 |
0 |
1 |
0 |
1 |
1 |
| 2 |
0 |
1 |
0 |
1 |
0 |
0 |
| 3 |
1 |
0 |
1 |
0 |
0 |
1 |
| 4 |
1 |
1 |
0 |
0 |
0 |
1 |
| 5 |
0 |
1 |
1 |
1 |
1 |
0 |
อัลกอริทึม
add_edge(u, v)
Input: จุดยอด u และ v ของเส้นเชื่อม {u,v}
Output: Adjacency matrix ของกราฟ G
Begin
adj_matrix[u, v] := 1
adj_matrix[v, u] := 1
End
ตัวอย่างโค้ด
#include <iostream>
using namespace std;
int vertArr[20][20]; // adjacency matrix เริ่มต้นเป็น 0
int count = 0;
void displayMatrix(int v) {
int i, j;
for(i = 0; i < v; i++) {
for(j = 0; j < v; j++) {
cout << vertArr[i][j] << " ";
}
cout << endl;
}
}
void add_edge(int u, int v) {
// ฟังก์ชันเพิ่มเส้นเชื่อมในเมทริกซ์
vertArr[u][v] = 1;
vertArr[v][u] = 1;
}
main(int argc, char* argv[]) {
int v = 6; // มี 6 จุดยอดในกราฟ
add_edge(0, 4);
add_edge(0, 3);
add_edge(1, 2);
add_edge(1, 4);
add_edge(1, 5);
add_edge(2, 3);
add_edge(2, 5);
add_edge(5, 3);
add_edge(5, 4);
displayMatrix(v);
}
ผลลัพธ์
0 0 0 1 1 0 0 0 1 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 0 0 0 1 0 1 1 1 1 0
