[Algorithm] Graphs - Prim's Algorithm - 하고싶은거하는

프림 알고리즘 (Prim’s Algorithm)

프림 알고리즘은 최소 신장 트리 (Minimum Spanning Tree, MST) 를 구하는 방법 중 하나입니다. 주어진 가중치가 있는 무방향 그래프에서 모든 노드를 연결하는 가장 짧은 경로 집합을 찾는 데 사용됩니다. MST는 실제 네트워크에서 비용을 최소화하는 연결망을 만드는 데 매우 유용합니다.

알고리즘 설명:

주어진 그래프에서 임의의 노드를 선택해 시작합니다.
선택된 노드에서 인접한 모든 간선 중 가장 작은 가중치의 간선을 선택해 연결합니다.
연결된 새로운 노드를 포함하여, 다시 인접한 모든 간선 중 가장 작은 가중치의 간선을 선택해 트리에 추가합니다.
이 과정을 모든 노드가 연결될 때까지 반복합니다.

프림 알고리즘은 주로 네트워크 설계, 전기 회로, 도로 연결 시스템과 같은 최소한의 비용으로 연결해야 하는 다양한 실제 문제에서 사용됩니다.

JavaScript 예제

function primMST(graph) {
  const key = new Array(graph.length).fill(Infinity); // 각 노드의 최소 가중치 저장
  const parent = new Array(graph.length).fill(-1); // 각 노드의 부모 노드 저장
  const inMST = new Array(graph.length).fill(false); // MST에 포함 여부

  key[0] = 0; // 시작 노드의 가중치는 0
  for (let count = 0; count < graph.length - 1; count++) {
    let minKey = Infinity,
      u = -1;

    // 최소 가중치의 노드를 선택
    for (let v = 0; v < graph.length; v++) {
      if (!inMST[v] && key[v] < minKey) {
        minKey = key[v];
        u = v;
      }
    }

    inMST[u] = true; // 선택된 노드를 MST에 포함

    // 선택된 노드와 인접한 노드의 가중치를 업데이트
    for (let v = 0; v < graph.length; v++) {
      if (graph[u][v] && !inMST[v] && graph[u][v] < key[v]) {
        key[v] = graph[u][v];
        parent[v] = u;
      }
    }
  }

  // 결과 출력
  for (let i = 1; i < graph.length; i++) {
    console.log(`${parent[i]} - ${i} \t${graph[i][parent[i]]}`);
  }
}

// 예시 그래프 (인접 행렬)
const graph = [
  [0, 2, 0, 6, 0],
  [2, 0, 3, 8, 5],
  [0, 3, 0, 0, 7],
  [6, 8, 0, 0, 9],
  [0, 5, 7, 9, 0],
];

primMST(graph);

Rust 예제

use std::cmp::Ordering;
use std::collections::BinaryHeap;

#[derive(Copy, Clone, Eq, PartialEq)]
struct Edge {
    weight: usize,
    node: usize,
}

impl Ord for Edge {
    fn cmp(&self, other: &Self) -> Ordering {
        other.weight.cmp(&self.weight) // 최소 힙으로 사용하기 위해 역순으로 정렬
    }
}

impl PartialOrd for Edge {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn prim_mst(graph: &Vec<Vec<(usize, usize)>>, start: usize) {
    let mut in_mst = vec![false; graph.len()];
    let mut min_heap = BinaryHeap::new();

    min_heap.push(Edge { weight: 0, node: start });

    while let Some(Edge { weight, node }) = min_heap.pop() {
        if in_mst[node] {
            continue;
        }
        in_mst[node] = true;

        println!("선택된 간선: {} (가중치: {})", node, weight);

        for &(neighbor, edge_weight) in &graph[node] {
            if !in_mst[neighbor] {
                min_heap.push(Edge {
                    weight: edge_weight,
                    node: neighbor,
                });
            }
        }
    }
}

fn main() {
    let graph = vec![
        vec![(1, 2), (3, 6)],    // 0번 노드와 연결된 노드들
        vec![(0, 2), (2, 3), (3, 8), (4, 5)], // 1번 노드와 연결된 노드들
        vec![(1, 3), (4, 7)],    // 2번 노드와 연결된 노드들
        vec![(0, 6), (1, 8), (4, 9)], // 3번 노드와 연결된 노드들
        vec![(1, 5), (2, 7), (3, 9)] // 4번 노드와 연결된 노드들
    ];

    prim_mst(&graph, 0);
}

설명:

JavaScript에서는 인접 행렬을 사용하여 그래프를 표현하고, 각 노드의 최소 가중치를 관리합니다.
Rust에서는 이진 힙을 사용하여 간선의 가중치에 따라 노드를 선택하는 방식으로 최소 신장 트리를 구합니다.

사용 예시:

네트워크 설계: 여러 도시를 최소한의 비용으로 연결하는 도로 또는 통신망 설계.
전력망 설계: 최소 비용으로 전기망을 연결.
컴퓨터 그래픽: 그래프 기반의 도형 처리.

프림 알고리즘은 연결된 그래프에서 비용이 최소인 트리를 찾는 문제에서 매우 유용하게 사용됩니다.

Prim’s Algorithm

Prim’s Algorithm is a way to find the Minimum Spanning Tree (MST). In a given weighted, undirected graph, it helps to find the shortest set of edges that connects all nodes. MST is useful in real-world scenarios where you need to connect networks at the minimum possible cost.

Algorithm Explanation:

Start from any node in the graph.
From the selected node, pick the edge with the smallest weight to connect to an adjacent node.
Include the new node and repeat the process by selecting the smallest weight edge among all adjacent edges.
Repeat this until all nodes are connected.

Prim’s algorithm is particularly useful in real-world problems like designing networks, electrical circuits, or road connections that minimize costs.

JavaScript Example

function primMST(graph) {
  const key = new Array(graph.length).fill(Infinity); // Store the minimum weights
  const parent = new Array(graph.length).fill(-1); // Store parent nodes
  const inMST = new Array(graph.length).fill(false); // Tracks if the node is in the MST

  key[0] = 0; // Start from the first node
  for (let count = 0; count < graph.length - 1; count++) {
    let minKey = Infinity,
      u = -1;

    // Select the node with the smallest weight
    for (let v = 0; v < graph.length; v++) {
      if (!inMST[v] && key[v] < minKey) {
        minKey = key[v];
        u = v;
      }
    }

    inMST[u] = true; // Add the selected node to MST

    // Update adjacent nodes with new minimum weight
    for (let v = 0; v < graph.length; v++) {
      if (graph[u][v] && !inMST[v] && graph[u][v] < key[v]) {
        key[v] = graph[u][v];
        parent[v] = u;
      }
    }
  }

  // Output the MST
  for (let i = 1; i < graph.length; i++) {
    console.log(`${parent[i]} - ${i} \t${graph[i][parent[i]]}`);
  }
}

// Sample graph (adjacency matrix)
const graph = [
  [0, 2, 0, 6, 0],
  [2, 0, 3, 8, 5],
  [0, 3, 0, 0, 7],
  [6, 8, 0, 0, 9],
  [0, 5, 7, 9, 0],
];

primMST(graph);

Rust Example

use std::cmp::Ordering;
use std::collections::BinaryHeap;

#[derive(Copy, Clone, Eq, PartialEq)]
struct Edge {
    weight: usize,
    node: usize,
}

impl Ord for Edge {
    fn cmp(&self, other: &Self) -> Ordering {
        other.weight.cmp(&self.weight) // Reverse ordering for minimum heap
    }
}

impl PartialOrd for Edge {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn prim_mst(graph: &Vec<Vec<(usize, usize)>>, start: usize) {
    let mut in_mst = vec![false; graph.len()];
    let mut min_heap = BinaryHeap::new();

    min_heap.push(Edge { weight: 0, node: start });

    while let Some(Edge { weight, node }) = min_heap.pop() {
        if in_mst[node] {
            continue;
        }
        in_mst[node] = true;

        println!("Selected Edge: {} (Weight: {})", node, weight);

        for &(neighbor, edge_weight) in &graph[node] {
            if !in_mst[neighbor] {
                min_heap.push(Edge {
                    weight: edge_weight,
                    node: neighbor,
                });
            }
        }
    }
}

fn main() {
    let graph = vec![
        vec![(1, 2), (3, 6)],    // Connections from node 0
        vec![(0, 2), (2, 3), (3, 8), (4, 5)], // Connections from node 1
        vec![(1, 3), (4, 7)],    // Connections from node 2
        vec![(0, 6), (1, 8), (4, 9)], // Connections from node 3
        vec![(1, 5), (2, 7), (3, 9)] // Connections from node 4
    ];

    prim_mst(&graph, 0);
}

Explanation:

JavaScript uses an adjacency matrix to represent the graph and manages minimum weights for each node.
Rust uses a binary heap to maintain the minimum weight and processes nodes based on the lowest weight edge.

Usage:

Network Design: Optimizing the cost to connect multiple cities with roads or communication networks.
Electrical Grid Design: Connecting multiple stations with minimum wiring cost.
Computer Graphics: Graph-based shape processing.

Prim’s Algorithm is widely used in scenarios where you need to find the minimum cost to connect all parts of a system.

[Algorithm] Graphs - Prim's Algorithm

그레프 - 프림 알고리즘