Kruskal 알고리즘

🌳 1. 스패닝 트리란?

스패닝 트리(Spanning Tree)는 그래프의 모든 정점을 연결하되, 사이클이 없이 간선의 수를 최소화한 트리입니다.

• 정점의 수가 N개라면, 스패닝 트리는 N - 1개의 간선으로 구성됩니다.
• 사이클이 존재하면 안 되며, 모든 정점이 연결되어 있어야 합니다.

📌 스패닝 트리는 여러 개가 존재할 수 있습니다.

---

🌟 2. 최소 스패닝 트리(Minimum Spanning Tree, MST)

최소 스패닝 트리(MST)는 말 그대로 가중치 합이 가장 작은 스패닝 트리입니다.

💡 예시 이미지:

📎 첫 번째 이미지:

• 노란 간선들은 스패닝 트리를 구성한 모습입니다. 간선 수는 N - 1.
  📎 두 번째 이미지:
• 가중치를 고려해 가장 최소 비용으로 구성된 트리입니다.
• 빨간 간선이 MST를 구성하고 있고, 총 비용은 15 + 5 + 10 + 5 + 5 = 40입니다.

---

⚙️ 3. Kruskal 알고리즘이란?

Kruskal 알고리즘은 MST를 만들기 위한 대표적인 알고리즘 중 하나입니다.

• 탐욕(Greedy) 알고리즘 기반
• 사이클 생성을 방지하기 위해 Disjoint Set (서로소 집합) 사용
• 가중치 기준 오름차순으로 간선을 하나씩 추가하며 MST 구성

---

🧭 4. 알고리즘 흐름

✅ 크루스칼 알고리즘 순서

1. 그래프의 모든 간선 정보를 가중치 기준 오름차순으로 정렬
2. 간선을 하나씩 순회하면서 사이클이 생기는지 검사
   • 사이클이 생기지 않으면 간선을 MST에 포함
   • 사이클이 생기면 해당 간선은 제외
3. 간선이 N - 1개 선택되면 완료!

---

🧩 5. Disjoint Set(서로소 집합) 복습

MST 생성 시 사이클 여부 판단을 위해 사용됩니다.

class DisjointSet {
public:
    DisjointSet(int n) : _parent(n), _rank(n, 1) {
        for (int i = 0; i < n; i++)
            _parent[i] = i;
    }

    int Find(int u) {
        if (u == _parent[u]) return u;
        return _parent[u] = Find(_parent[u]); // 경로 압축
    }

    void Merge(int u, int v) {
        u = Find(u); v = Find(v);
        if (u == v) return;

        if (_rank[u] > _rank[v]) swap(u, v);
        _parent[u] = v;
        if (_rank[u] == _rank[v]) _rank[v]++;
    }

private:
    vector<int> _parent;
    vector<int> _rank;
};

---

🧱 6. 그래프 구성 (인접 행렬 기반)

vector<Vertex> vertices;
vector<vector<int>> adjacent;

void CreateGraph() {
    vertices.resize(6);
    adjacent = vector<vector<int>>(6, vector<int>(6, -1));

    adjacent[0][1] = adjacent[1][0] = 15;
    adjacent[0][3] = adjacent[3][0] = 35;
    adjacent[1][2] = adjacent[2][1] = 5;
    adjacent[1][3] = adjacent[3][1] = 10;
    adjacent[3][4] = adjacent[4][3] = 5;
    adjacent[3][5] = adjacent[5][3] = 10;
    adjacent[5][4] = adjacent[4][5] = 5;
}

---

🔁 7. Kruskal 알고리즘 구현

struct CostEdge {
    int cost;
    int u, v;

    bool operator<(CostEdge& other) {
        return cost < other.cost; // 가중치 기준 오름차순
    }
};

int Kruskal(vector<CostEdge>& selected) {
    int totalCost = 0;
    selected.clear();
    vector<CostEdge> edges;

    // 간선 수집
    for (int u = 0; u < adjacent.size(); u++) {
        for (int v = 0; v < adjacent[u].size(); v++) {
            if (u > v || adjacent[u][v] == -1) continue;
            edges.push_back({adjacent[u][v], u, v});
        }
    }

    sort(edges.begin(), edges.end());

    DisjointSet sets(vertices.size());

    for (CostEdge& edge : edges) {
        if (sets.Find(edge.u) == sets.Find(edge.v)) continue;

        sets.Merge(edge.u, edge.v);
        selected.push_back(edge);
        totalCost += edge.cost;
    }

    return totalCost;
}

---

🚀 8. 실행 예제

int main() {
    CreateGraph();

    vector<CostEdge> selected;
    int totalCost = Kruskal(selected);

    cout << "MST 총 비용: " << totalCost << endl;
    return 0;
}

---