تخيل Facebook:
الاتصال في الاتجاهين
مثال: صداقة Facebook
الاتصال في اتجاه واحد
مثال: متابعة Twitter
كل edge ليه تكلفة/وزن
مثال: المسافات على الخريطة
كل الـ edges متساوية
مثال: شبكة الأصدقاء
Edges: A-B, A-C, A-D, B-D, C-D
إزاي نخزن الـ Graph في الكود؟
جدول 2D: كل خلية بتقول لو فيه edge ولا لأ
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 1 |
| B | 1 | 0 | 0 | 1 |
| C | 1 | 0 | 0 | 1 |
| D | 1 | 1 | 1 | 0 |
✓ مناسب لو:
الـ graph dense (edges كتير)
كل node عندها list بالـ neighbors بتوعها
✓ مناسب لو:
الـ graph sparse (edges قليلة)
| العملية | Matrix | List |
|---|---|---|
| Space | O(V²) | O(V+E) |
| Check if Edge exists | O(1) | O(V) |
| Find all neighbors | O(V) | O(degree) |
| Add Edge | O(1) | O(1) |
| الأفضل لـ | Dense Graphs | Sparse Graphs |
💡 متى تستخدم إيه؟
class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
}
}
addEdge(v1, v2) {
this.adjacencyList[v1].push(v2);
this.adjacencyList[v2].push(v1);
}
getNeighbors(vertex) {
return this.adjacencyList[vertex] || [];
}
hasEdge(v1, v2) {
return this.adjacencyList[v1]?.includes(v2);
}
}