[알고리즘] 그래프 참고 슬라이드

[질문 1]

에지가 n−1개인 연결된 그래프는 트리인가?

✅ 정답: 예 (항상 트리)

• 트리의 정의: 연결되어 있고 사이클이 없으며 간선이 정확히 n-1개
• 조건 만족: 연결 + n-1개의 간선이면 사이클이 있을 수 없음 → 트리임

---

[질문 2]

에지가 n−1개인 사이클이 없는 그래프는 트리인가?

❗ 정답: 아니오 (반드시 연결되었다는 보장이 없음)

• 반례: 정점 5개, 간선 4개지만 연결되지 않은 2개의 구성요소 → 트리가 아님
• 요점: 사이클이 없고 간선 수 n-1이면 트리인지 여부는 연결성까지 확인해야 함

---

[질문 3]

에지 개수가 n−1을 초과하면 반드시 사이클이 존재하는가?

✅ 정답: 예

• 사이클 없는 그래프(즉, 포리스트)의 최대 간선 수는 n-1
• n개의 정점에 대해 n개 이상 간선이 있다면 사이클이 반드시 존재함

---

[질문 4]

사이클이 존재하면 반드시 에지 개수가 n−1을 초과하는가?

✅ 정답: 예

• 반례가 없음. 사이클이 생기려면 최소한 n개의 간선 이상 필요
• 트리는 n-1개고, 여기서 간선 하나만 추가돼도 반드시 사이클 생김

---

[질문 5]

주어진 그래프가 트리인지 검사하는 가장 간단한 방법은?

✅ 정답:

연결되어 있고 간선 개수가 n−1개인지 확인하면 됨

• **O(n + m)**으로 DFS/BFS로 연결 확인하고, 간선 수 체크하면 됨

 

구현코드

트리여부판단

// 트리 여부 판별 프로그램 (독립 실행)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 그래프가 트리인지 판단하는 함수
bool isTree(const vector<vector<int>>& adj, int nodeCount, int edgeCount) {
    if (edgeCount != nodeCount - 1)
        return false; // 간선 수 조건 위배

    vector<bool> visited(nodeCount, false);
    queue<int> q;
    q.push(0);
    visited[0] = true;

    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (int next : adj[cur]) {
            if (!visited[next]) {
                visited[next] = true;
                q.push(next);
            }
        }
    }

    for (bool v : visited)
        if (!v) return false; // 연결 안 된 노드 존재

    return true; // 연결 + 간선 수 조건 만족 → 트리
}

int main() {
    // 예제 그래프 (정점 5개, 간선 4개)
    int nodeCount = 5;
    int edgeCount = 4;
    vector<vector<int>> adj(nodeCount);

    adj[0].push_back(1); adj[1].push_back(0);
    adj[0].push_back(2); adj[2].push_back(0);
    adj[1].push_back(3); adj[3].push_back(1);
    adj[1].push_back(4); adj[4].push_back(1);

    if (isTree(adj, nodeCount, edgeCount))
        cout << "이 그래프는 트리입니다.\n";
    else
        cout << "이 그래프는 트리가 아닙니다.\n";

    return 0;
}

 

질문:
Kruskal과 Prim의 MST 알고리즘은 음수 가중치가 있는 경우에도 성립할까?

---

✅ 정답:

예, Kruskal과 Prim 알고리즘 모두 음수 가중치가 있는 경우에도 MST를 정확히 구할 수 있습니다.

---

🔍 이유 설명:

🟢 Kruskal 알고리즘

• 간선을 가중치 오름차순으로 정렬하고,
• 사이클이 생기지 않도록 최소 간선을 선택함.
• 가중치가 음수라도 상관없이 오름차순 정렬이 가능하므로 정상 동작함.

🟢 Prim 알고리즘

• 현재 정점과 연결된 간선 중 가장 작은 가중치 간선을 선택함.
• 가중치가 음수라도, 가장 작은 값이면 선택됨.
• 우선순위 큐에서 음수도 정상 비교되므로 문제 없음.

// 통합 그래프 알고리즘 구현 파일: SCC, DFS, MST(Prim/Kruskal), Clustering, Widest Path, DAG Topo Sort
// 각 기능별 실행 선택 방식으로 구성
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <fstream>
#include <algorithm>
#include <tuple>

using namespace std;

// ========================== 공통 변수 ==========================
int V, E;
vector<vector<pair<int, int>>> adj; // 가중치 포함 그래프
vector<vector<int>> graph, rev_graph;
vector<bool> visited;
vector<int> parent;

// ========================== DFS ==========================
void dfs_util(int u) {
    visited[u] = true;
    cout << u << " ";
    for (auto [v, _] : adj[u]) if (!visited[v]) dfs_util(v);
}
void DFS() {
    visited.assign(V, false);
    cout << "DFS 순회: "; dfs_util(0); cout << endl;
}

// ========================== Topological Sort (DAG 전용) ==========================
vector<int> topo_result;
void topo_dfs(int u) {
    visited[u] = true;
    for (auto [v, _] : adj[u]) if (!visited[v]) topo_dfs(v);
    topo_result.push_back(u);
}
void TopologicalSort() {
    visited.assign(V, false); topo_result.clear();
    for (int i = 0; i < V; i++) if (!visited[i]) topo_dfs(i);
    reverse(topo_result.begin(), topo_result.end());
    cout << "Topological Sort 결과: ";
    for (int x : topo_result) cout << x << " ";
    cout << endl;
}

// ========================== SCC (Kosaraju) ==========================
stack<int> finish_order;
vector<vector<int>> SCCs;
void dfs1(int u) {
    visited[u] = true;
    for (int v : graph[u]) if (!visited[v]) dfs1(v);
    finish_order.push(u);
}
void dfs2(int u, vector<int>& comp) {
    visited[u] = true; comp.push_back(u);
    for (int v : rev_graph[u]) if (!visited[v]) dfs2(v, comp);
}
void SCC_Kosaraju() {
    visited.assign(V, false);
    for (int i = 0; i < V; ++i) if (!visited[i]) dfs1(i);

    visited.assign(V, false);
    while (!finish_order.empty()) {
        int u = finish_order.top(); finish_order.pop();
        if (!visited[u]) {
            vector<int> comp; dfs2(u, comp);
            SCCs.push_back(comp);
        }
    }
    cout << "총 SCC 개수: " << SCCs.size() << endl;
    for (size_t i = 0; i < SCCs.size(); ++i) {
        cout << "SCC " << i + 1 << ": ";
        for (int v : SCCs[i]) cout << v << " "; cout << endl;
    }
}

// ========================== Kruskal MST ==========================
struct Edge { int u, v, w; };
vector<Edge> edges;
int find(int u) { return parent[u] == u ? u : parent[u] = find(parent[u]); }
bool unite(int u, int v) {
    u = find(u); v = find(v);
    if (u == v) return false;
    parent[v] = u; return true;
}
void Kruskal() {
    parent.resize(V); for (int i = 0; i < V; ++i) parent[i] = i;
    sort(edges.begin(), edges.end(), [](Edge a, Edge b) { return a.w < b.w; });
    int mst_cost = 0;
    cout << "Kruskal MST 간선: \n";
    for (Edge e : edges) {
        if (unite(e.u, e.v)) {
            cout << e.u << " - " << e.v << " : " << e.w << endl;
            mst_cost += e.w;
        }
    }
    cout << "MST 총 비용: " << mst_cost << endl;
}

// ========================== Prim MST ==========================
void Prim() {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    vector<int> dist(V, 1e9); dist[0] = 0;
    vector<bool> inMST(V, false);
    pq.push({0, 0}); int mst_cost = 0;
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (inMST[u]) continue;
        inMST[u] = true; mst_cost += d;
        for (auto [v, w] : adj[u]) if (!inMST[v] && w < dist[v]) {
            dist[v] = w; pq.push({w, v});
        }
    }
    cout << "Prim MST 총 비용: " << mst_cost << endl;
}

// ========================== Widest Path ==========================
void WidestPath(int src) {
    vector<int> width(V, 0); width[src] = 1e9;
    priority_queue<pair<int, int>> pq; pq.push({1e9, src});
    while (!pq.empty()) {
        auto [w, u] = pq.top(); pq.pop();
        for (auto [v, cost] : adj[u]) {
            int min_width = min(w, cost);
            if (min_width > width[v]) {
                width[v] = min_width;
                pq.push({width[v], v});
            }
        }
    }
    cout << "Widest path 값: \n";
    for (int i = 0; i < V; ++i)
        cout << "0 → " << i << ": " << width[i] << endl;
}

// ========================== 입력 및 실행 ==========================
void loadGraph(const string& fname) {
    ifstream in(fname);
    if (!in) { cerr << "파일 열기 실패!\n"; exit(1); }
    in >> V >> E;
    adj.assign(V, {});
    graph.assign(V, {}); rev_graph.assign(V, {}); edges.clear();
    for (int i = 0; i < E; ++i) {
        int u, v, w; in >> u >> v >> w;
        adj[u].push_back({v, w});
        graph[u].push_back(v);
        rev_graph[v].push_back(u);
        edges.push_back({u, v, w});
    }
    in.close();
}

int main() {
    cout << "그래프 입력 파일명 입력 (예: input.txt): ";
    string fname; cin >> fname;
    loadGraph(fname);

    cout << "\n1: DFS\n2: Topological Sort\n3: SCC (Kosaraju)\n4: Kruskal MST\n5: Prim MST\n6: Widest Path (0기준)\n선택: ";
    int op; cin >> op;
    if (op == 1) DFS();
    else if (op == 2) TopologicalSort();
    else if (op == 3) SCC_Kosaraju();
    else if (op == 4) Kruskal();
    else if (op == 5) Prim();
    else if (op == 6) WidestPath(0);
    else cout << "잘못된 입력\n";
    return 0;
}

/*
📘 사용법:
- input.txt: 정점 수, 간선 수, 각 간선(u v w) 형식
예시:
8 10
0 1 1
1 2 1
2 0 1
2 3 5
3 4 3
4 5 2
5 3 1
6 5 7
6 7 4
7 6 6

- 실행: g++ -o graph_alg graph_alg.cpp && ./graph_alg

✏️ 각 알고리즘별 주석 포함 완전 구현
*/