Prim's Algorithm (Prim Algoritması)

1// Prim's Algorithm JavaScript implementasyonu
2class PrimMST {
3  constructor(graph) {
4    this.graph = graph;
5    this.vertices = graph.vertices;
6    this.edges = graph.edges;
7  }
8
9  // Ana Prim algoritması - MST hesaplar
10  findMST(startVertex = 0) {
11    const mst = [];
12    const visited = new Set();
13    const priorityQueue = new MinHeap();
14    let totalWeight = 0;
15
16    // Başlangıç düğümünü ziyaret edildi olarak işaretle
17    visited.add(startVertex);
18
19    // Başlangıç düğümünün tüm kenarlarını priority queue'ya ekle
20    this.addEdgesToQueue(startVertex, visited, priorityQueue);
21
22    // MST tamamlanana kadar devam et
23    while (!priorityQueue.isEmpty() && visited.size < this.vertices.length) {
24      const edge = priorityQueue.extractMin();
25      const { from, to, weight } = edge;
26
27      // Hedef düğüm zaten ziyaret edildiyse atla
28      if (visited.has(to)) {
29        continue;
30      }
31
32      // Kenarı MST'ye ekle
33      mst.push(edge);
34      totalWeight += weight;
35      visited.add(to);
36
37      // Yeni düğümün kenarlarını queue'ya ekle
38      this.addEdgesToQueue(to, visited, priorityQueue);
39    }
40
41    return {
42      edges: mst,
43      totalWeight: totalWeight,
44      isComplete: visited.size === this.vertices.length
45    };
46  }
47
48  // Belirtilen düğümün kenarlarını priority queue'ya ekle
49  addEdgesToQueue(vertex, visited, priorityQueue) {
50    for (const edge of this.edges) {
51      // Düğümden çıkan ve henüz ziyaret edilmemiş düğümlere giden kenarlar
52      if (edge.from === vertex && !visited.has(edge.to)) {
53        priorityQueue.insert(edge, edge.weight);
54      }
55      // Undirected graf için tersi de geçerli
56      else if (edge.to === vertex && !visited.has(edge.from)) {
57        const reverseEdge = { from: edge.to, to: edge.from, weight: edge.weight };
58        priorityQueue.insert(reverseEdge, edge.weight);
59      }
60    }
61  }
62
63  // MST'nin geçerli olup olmadığını kontrol et
64  validateMST(mst) {
65    if (mst.edges.length !== this.vertices.length - 1) {
66      return false;
67    }
68
69    // Tüm düğümlerin bağlı olup olmadığını kontrol et
70    const visited = new Set();
71    const stack = [mst.edges[0].from];
72
73    while (stack.length > 0) {
74      const current = stack.pop();
75      if (visited.has(current)) continue;
76      
77      visited.add(current);
78
79      for (const edge of mst.edges) {
80        if (edge.from === current && !visited.has(edge.to)) {
81          stack.push(edge.to);
82        } else if (edge.to === current && !visited.has(edge.from)) {
83          stack.push(edge.from);
84        }
85      }
86    }
87
88    return visited.size === this.vertices.length;
89  }
90
91  // Graf bilgilerini döndür
92  getGraphInfo() {
93    return {
94      vertexCount: this.vertices.length,
95      edgeCount: this.edges.length,
96      isConnected: this.isGraphConnected()
97    };
98  }
99
100  // Grafın bağlı olup olmadığını kontrol et
101  isGraphConnected() {
102    if (this.vertices.length === 0) return true;
103
104    const visited = new Set();
105    const stack = [this.vertices[0]];
106
107    while (stack.length > 0) {
108      const current = stack.pop();
109      if (visited.has(current)) continue;
110      
111      visited.add(current);
112
113      for (const edge of this.edges) {
114        if (edge.from === current && !visited.has(edge.to)) {
115          stack.push(edge.to);
116        } else if (edge.to === current && !visited.has(edge.from)) {
117          stack.push(edge.from);
118        }
119      }
120    }
121
122    return visited.size === this.vertices.length;
123  }
124}
125
126// Min Heap implementasyonu - Priority Queue için
127class MinHeap {
128  constructor() {
129    this.heap = [];
130  }
131
132  // Parent index hesapla
133  getParentIndex(index) {
134    return Math.floor((index - 1) / 2);
135  }
136
137  // Left child index hesapla
138  getLeftChildIndex(index) {
139    return 2 * index + 1;
140  }
141
142  // Right child index hesapla
143  getRightChildIndex(index) {
144    return 2 * index + 2;
145  }
146
147  // İki elemanın yerini değiştir
148  swap(index1, index2) {
149    [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
150  }
151
152  // Yeni eleman ekle
153  insert(element, priority) {
154    const node = { element, priority };
155    this.heap.push(node);
156    this.heapifyUp(this.heap.length - 1);
157  }
158
159  // Minimum elemanı çıkar
160  extractMin() {
161    if (this.heap.length === 0) return null;
162    if (this.heap.length === 1) return this.heap.pop().element;
163
164    const min = this.heap[0].element;
165    this.heap[0] = this.heap.pop();
166    this.heapifyDown(0);
167    return min;
168  }
169
170  // Yukarı doğru heap property koru
171  heapifyUp(index) {
172    while (index > 0) {
173      const parentIndex = this.getParentIndex(index);
174      if (this.heap[index].priority >= this.heap[parentIndex].priority) {
175        break;
176      }
177      this.swap(index, parentIndex);
178      index = parentIndex;
179    }
180  }
181
182  // Aşağı doğru heap property koru
183  heapifyDown(index) {
184    while (this.getLeftChildIndex(index) < this.heap.length) {
185      const leftChildIndex = this.getLeftChildIndex(index);
186      const rightChildIndex = this.getRightChildIndex(index);
187      
188      let smallestIndex = leftChildIndex;
189      if (rightChildIndex < this.heap.length && 
190          this.heap[rightChildIndex].priority < this.heap[leftChildIndex].priority) {
191        smallestIndex = rightChildIndex;
192      }
193
194      if (this.heap[index].priority <= this.heap[smallestIndex].priority) {
195        break;
196      }
197
198      this.swap(index, smallestIndex);
199      index = smallestIndex;
200    }
201  }
202
203  // Heap boş mu
204  isEmpty() {
205    return this.heap.length === 0;
206  }
207
208  // Heap boyutu
209  size() {
210    return this.heap.length;
211  }
212}
213
214// Kullanım örneği
215const graph = {
216  vertices: [0, 1, 2, 3, 4],
217  edges: [
218    { from: 0, to: 1, weight: 2 },
219    { from: 0, to: 3, weight: 6 },
220    { from: 1, to: 2, weight: 3 },
221    { from: 1, to: 3, weight: 8 },
222    { from: 1, to: 4, weight: 5 },
223    { from: 2, to: 4, weight: 7 },
224    { from: 3, to: 4, weight: 9 }
225  ]
226};
227
228const primMST = new PrimMST(graph);
229const result = primMST.findMST(0);
230console.log('MST Edges:', result.edges);
231console.log('Total Weight:', result.totalWeight);