[C++ - TIL] 그래프 자료구조 구현 및 인접 행렬 관리

🎮 주제 : 그래프 자료구조 구현 및 인접 행렬 관리

태그 : #C++ #자료구조 #그래프 #인접행렬 #이중포인터 #메모리관리

---

📌 학습 요약

1. 그래프의 구조와 표현 : 정점(Vertex)과 간선(Edge)의 관계를 정의하고, 2차원 배열을 이용한 **인접 행렬(Adjacency Matrix)**로 연결 상태를 표현하는 방식 숙지
2. 이중 포인터(int**)의 활용 : 런타임에 결정되는 정점의 개수에 맞춰 행과 열을 각각 동적 할당하여 유연한 행렬 구조 설계
3. 메모리 할당 및 해제 로직 : 행별로 할당된 배열을 먼저 삭제하고 최종적으로 행을 가리키는 포인터 배열을 삭제하는 이중 해제 프로세스 정립
4. 동적 배열 확장(resize) : 정점의 개수가 늘어날 때 기존 데이터를 보존하며 새로운 저장 공간을 확보하는 재할당 전략 구현
5. 예외 처리와 안정성 : 인덱스 범위 검사(i >= size) 및 중복 할당 방지 로직을 통해 메모리 누수와 런타임 오류 방지

---

🛠 주요 코드 및 구현 상세

1. 이중 포인터를 이용한 인접 행렬 동적 할당

void InitializeMatrix(int size) {
    if (matrix != nullptr) return; // 중복 할당 방지

    matrix = new int*[size];
    for (int i = 0; i < size; i++) {
        matrix[i] = new int[size];
        for (int j = 0; j < size; j++) {
            matrix[i][j] = 0; // 초기 상태는 연결 없음(0)
        }
    }
}

2. 무방향 그래프의 간선(Edge) 추가

void edge(int i, int j) {
    // 1. 범위 검사 (size-1까지가 유효 인덱스)
    if (i >= size || j >= size || i < 0 || j < 0) {
        cout << "index out of range" << endl;
        return;
    }

    // 2. 행렬이 할당되지 않았다면 할당
    if (matrix == nullptr) InitializeMatrix(size);

    // 3. 무방향이므로 대칭으로 1 설정
    matrix[i][j] = 1;
    matrix[j][i] = 1;
}

3. 안전한 메모리 해제 (소멸자)

~Graph() {
    if (matrix != nullptr) {
        // 각 행(int 배열)을 먼저 해제
        for (int i = 0; i < size; i++) {
            delete[] matrix[i];
        }
        // 행을 가리키던 포인터 배열 해제
        delete[] matrix;
    }
    // 정점 정보 배열 해제
    delete[] vertex;
}

---

✅ 주요 문법 및 개념 정리

구분 인접 행렬 (Adjacency Matrix) 인접 리스트 (Adjacency List)

공간 복잡도	$O(V^2)$ (정점의 제곱에 비례)	$O(V + E)$ (정점과 간선 합에 비례)
연결 확인	$O(1)$ (즉시 확인 가능)	$O(Degree(V))$ (리스트 순회 필요)
적합한 상황	간선이 많은 밀집 그래프(Dense)	간선이 적은 희소 그래프(Sparse)
장점	구현이 단순하고 직관적	메모리 효율성이 뛰어남

💡 주의 : 인덱스 경계값 검사

• 오류 : if (i > size) → size가 5일 때 i가 5인 경우를 통과시킴. 그러나 인덱스는 0~4까지만 유효하므로 matrix[5] 접근 시 크래시 발생
• 수정 : if (i >= size) → 정점 개수와 인덱스가 같아지는 시점부터 차단해야 안전함

---

✨ 느낀 점

• 그래프 구현에서 동적 배열과 2차원 배열(이중 포인터)의 유기적인 관계를 깊이 있게 이해함
• 메모리 할당 시 매번 새로 할당하면 기존 주소를 잃어버려 누수가 발생한다는 점을 통해 nullptr 체크의 중요성을 깨달음
• 소멸자에서 delete[]를 단계별로 수행하지 않으면 힙 메모리에 고립된 블록이 남게 된다는 사실을 인지하며 정교한 설계를 연습함
• resize 함수를 통해 동적으로 크기를 조절하는 방식을 익히며 STL vector의 내부 동작 원리를 다시 한번 체감함
• 무방향 그래프의 대칭적 특성을 인접 행렬의 [i][j]와 [j][i] 쌍으로 표현하는 논리적 명쾌함을 경험함