Graph məlumat strukturu

[codex]

Graph nədir?

Graph (Qraf) — düyünlərdən (vertex) və onları birləşdirən kənarlardan (edge) ibarət olan bir məlumat strukturudur. Kənarlar iki düyün arasındakı əlaqəni təmsil edir.

Qraflar çoxşaxəli və geniş istifadə edilən məlumat strukturlarıdır. Onlar sosial şəbəkələr, nəqliyyat şəbəkələri, yol xəritələri və daha çox real dünya sistemlərinin modelləşdirilməsi üçün istifadə edilir.

Qraf növləri:

• İstiqamətli (Directed) və istiqamətsiz (Undirected) qraflar;
• Çəkili (Weighted) və çəkisiz (Unweighted) qraflar;
• Dövrəli (Cyclic) və dövrəsiz (Acyclic) qraflar.

Qraf alqoritmləri qoşulma (connectivity), ən qısa yol (shortest path), keçidlər (traversals) kimi problemləri həll etmək üçün vacibdir.

---

Əsas Qraf terminləri

Termin	İzah
Vertex (Düyün)	Qrafın tərkib hissəsi olan düyün (nöqtə).
Edge (Kənar)	Düyünlər arasında əlaqəni yaradan körpü.
Weighted/Unweighted (Çəkili/Çəkisiz)	Əgər kənarlara müəyyən rəqəmsal dəyər verilirsə, çəkili olur. Əks halda çəkisizdir.
Directed/Undirected (İstiqamətli/İstiqamətsiz)	Əgər əlaqə tək istiqamətlidir, istiqamətli qrafdır. İki tərəfli əlaqə varsa, istiqamətsizdir.

---

Qrafın JavaScript-də implementasiyası

Qrafı obyektlər və siyahılar vasitəsilə təmsil edə bilərik. Burada “Adjacency List” (Qonşuluq Siyahısı) istifadə edəcəyik.

class Graph {
  constructor() {
    this.adjacencyList = {};
  }
}

---

Vertex (Düyün) əlavə etmə

Yeni bir düyün (vertex) əlavə etmək üçün addVertex() metodunu yaradırıq.

Addım-addım izah:

1. addVertex metodu vertex adında bir parametr qəbul edir.
2. Əgər həmin vertex adjacency list-də yoxdursa, yeni açar (key) kimi əlavə edilir.
3. Əlavə edilən vertex-in dəyəri boş array olur (çünki hələ əlaqəsi yoxdur).

Kod:

addVertex(vertex) {
  if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
}

---

Edge (Kənar) əlavə etmə

İki düyün arasında əlaqə (kənar) yaratmaq üçün addEdge() metodunu yaradırıq.

Addım-addım izah:

1. Metod iki vertex qəbul edir (v1 və v2).
2. v1 açarını tapıb, onun array-nin içinə v2-ni əlavə edirik.
3. v2 açarını tapıb, onun array-nin içinə v1-i əlavə edirik.
4. Bununla, hər iki vertex bir-birinə bağlı olur.

Kod:

addEdge(v1, v2) {
  this.adjacencyList[v1].push(v2);
  this.adjacencyList[v2].push(v1);
}

---

Edge (Kənar) silmə

İki düyün arasındakı əlaqəni silmək üçün removeEdge() metodunu yaradırıq.

Addım-addım izah:

1. Metod iki vertex qəbul edir (v1 və v2).
2. v1 açarına baxırıq və v2-ni siyahıdan çıxarırıq.
3. v2 açarına baxırıq və v1-i siyahıdan çıxarırıq.

Kod:

removeEdge(v1, v2) {
  this.adjacencyList[v1] = this.adjacencyList[v1].filter(
    v => v !== v2
  );

  this.adjacencyList[v2] = this.adjacencyList[v2].filter(
    v => v !== v1
  );
}

---

Vertex (Düyün) silmə

Bütün əlaqələri ilə birlikdə bir vertex silmək üçün removeVertex() metodunu yaradırıq.

Addım-addım izah:

1. Metod silinməsi lazım olan vertex qəbul edir.
2. Həmin vertex-in qonşuluq siyahısı boşalana qədər onun hər bir əlaqəsini removeEdge() funksiyası ilə silirik.
3. Sonda vertex-i adjacency list-dən tamamilə silirik.

Kod:

removeVertex(vertex) {
  while (this.adjacencyList[vertex].length) {
    const adjacentVertex = this.adjacencyList[vertex].pop();
    this.removeEdge(vertex, adjacentVertex);
  }
  delete this.adjacencyList[vertex];
}

---

Nəticə

• Qraf məlumat strukturu düyünlər və onları birləşdirən kənarlardan ibarətdir.
• İstiqamətli, istiqamətsiz, çəkili və çəkisiz qraf tipləri mövcuddur.
• Adjacency List (Qonşuluq Siyahısı) qrafı təmsil etmək üçün effektiv üsuldur.
• Vertex əlavə etmə, edge əlavə etmə, edge silmə və vertex silmə əməliyyatlarını JavaScript ilə tətbiq etdik.

Qraflar geniş istifadə edilən bir məlumat strukturu olub, şəbəkələr, yol tapma alqoritmləri, sosial platformalar və daha çox sahədə tətbiq edilir.

---

mycodeschool Graph-ları çox rahat formada izah edir. Baxmağa dəyər.