Prim's Algorithm (Prim Algoritması)

1interface Edge {
2  from: string;
3  to: string;
4  weight: number;
5}
6
7function prim(vertices: string[], edges: Edge[], startVertex: string) {
8  const mst: Edge[] = [];
9  const visited = new Set([startVertex]);
10  
11  while (visited.size < vertices.length) {
12    let minEdge: Edge | null = null;
13    
14    for (const edge of edges) {
15      const fromVisited = visited.has(edge.from);
16      const toVisited = visited.has(edge.to);
17      
18      if ((fromVisited && !toVisited) || (!fromVisited && toVisited)) {
19        if (!minEdge || edge.weight < minEdge.weight) {
20          minEdge = edge;
21        }
22      }
23    }
24    
25    if (!minEdge) break;
26    mst.push(minEdge);
27    visited.add(minEdge.from);
28    visited.add(minEdge.to);
29  }
30  return mst;
31}