그래프 기초

📌 그래프란?

그래프(Graph)는 정점(Vertex) 과 간선(Edge) 으로 구성된 비선형 자료구조로, 현실 세계의 다양한 '연결 관계'를 표현하는 데 사용됩니다.

✅ 그래프의 구성 요소

• 정점(Vertex): 데이터를 나타냄 (예: 도시, 사람, 장소 등)
• 간선(Edge): 정점 간의 연결을 의미

✅ 그래프의 종류

• 무방향 그래프(Undirected Graph): 정점 간 연결이 양방향
• 방향 그래프(Directed Graph): 정점 간 연결이 일방향
• 가중치 그래프(Weighted Graph): 간선에 비용(가중치)이 존재

---

🛠 그래프 구현 방식 3가지

1️⃣ 포인터 기반 인접 리스트 방식

void CreateGraph_1()
{
    struct Vertex
    {
        vector<Vertex*> edges; // 연결된 정점 목록 (포인터)
    };

    vector<Vertex> v(6); // 정점 6개 생성

    // 간선 연결
    v[0].edges.push_back(&v[1]);
    v[0].edges.push_back(&v[3]);
    v[1].edges.push_back(&v[0]);
    v[1].edges.push_back(&v[2]);
    v[1].edges.push_back(&v[3]);
    v[3].edges.push_back(&v[4]);
    v[5].edges.push_back(&v[4]);

    // 연결 여부 확인: 0번 → 3번
    bool connected = false;
    for (Vertex* edge : v[0].edges)
    {
        if (edge == &v[3])
        {
            connected = true;
            break;
        }
    }
}

✅ 특징

• 각 정점은 자신과 연결된 정점을 포인터로 저장
• 단점: 정점과 간선이 강하게 엮여 있어 유지보수 불편
• 장점: 구조는 직관적

---

2️⃣ 정수 기반 인접 리스트 방식

void CreateGraph_2()
{
    vector<vector<int>> adjacent(6); // 연결 목록

    adjacent[0] = { 1, 3 };
    adjacent[1] = { 0, 2, 3 };
    adjacent[3] = { 4 };
    adjacent[5] = { 4 };

    // 연결 여부 확인
    bool connected = false;
    for (int vertex : adjacent[0])
    {
        if (vertex == 3)
        {
            connected = true;
            break;
        }
    }

    // STL 활용
    vector<int>& adj = adjacent[0];
    bool connected2 = (find(adj.begin(), adj.end(), 3) != adj.end());
}

✅ 특징

• 정점 ID만 저장하여 간접적으로 연결 정보 관리
• 장점: 구조가 가볍고 간단, 포인터 사용 안 함
• 단점: 연결 여부 탐색 시 반복문 필요

---

3️⃣ 인접 행렬 방식 (Adjacency Matrix)

void CreateGraph_3()
{
    vector<vector<bool>> adjacent(6, vector<bool>(6, false));

    adjacent[0][1] = true;
    adjacent[0][3] = true;
    adjacent[1][0] = true;
    adjacent[1][2] = true;
    adjacent[1][3] = true;
    adjacent[3][4] = true;
    adjacent[5][4] = true;

    // 연결 여부 확인
    bool connected = adjacent[0][3];
}

✅ 특징

• [from][to]로 직접 연결 여부를 확인
• 장점: 접근 속도 빠름 (O(1))
• 단점: 정점 수가 많을수록 메모리 낭비 심함 (O(N^2))

---

📦 가중치 그래프 표현

vector<vector<int>> weightGraph =
{
    { -1, 15, -1, 35, -1, -1 },
    { 15, -1,  5, 10, -1, -1 },
    { -1, -1, -1, -1, -1, -1 },
    { -1, -1, -1, -1,  5, -1 },
    { -1, -1, -1, -1, -1, -1 },
    { -1, -1, -1, -1,  5, -1 },
};

• -1: 연결되지 않은 정점
• 양의 정수: 간선의 비용 또는 거리

예: weightGraph[0][1] == 15 → 0번 정점에서 1번 정점까지의 비용은 15

---