[c++] C++를 사용한 그래프 분석

14 Dec 2023

그래프는 객체 간의 관계를 나타내는 자료 구조로서, 노드와 간선으로 구성됩니다. C++를 사용하여 그래프를 생성하고 분석하는 방법을 알아보겠습니다.

1. 그래프 표현

1.1 인접 행렬

그래프는 인접 행렬을 사용하여 표현할 수 있습니다. 이는 2차원 배열을 사용하여 각 노드 간의 연결 관계를 나타냅니다.

#include <iostream>
#include <vector>
using namespace std;

#define MAX_NODES 100
int graph[MAX_NODES][MAX_NODES];

void addEdge(int u, int v) {
    graph[u][v] = 1;
    // 무방향 그래프일 경우 graph[v][u]도 1로 설정
}

int main() {
    // 그래프 초기화
    for (int i = 0; i < MAX_NODES; i++) {
        for (int j = 0; j < MAX_NODES; j++) {
            graph[i][j] = 0;
        }
    }

    addEdge(0, 1);
    addEdge(1, 2);
    // 간선 추가 및 그래프 분석
    // ...
    return 0;
}

1.2 인접 리스트

인접 리스트는 각 노드마다 연결된 노드들의 리스트를 저장하는 방식으로, 구현이 간단하고 메모리를 효율적으로 사용할 수 있습니다.

#include <iostream>
#include <vector>
using namespace std;

vector<int> graph[MAX_NODES];

void addEdge(int u, int v) {
    graph[u].push_back(v);
    // 무방향 그래프일 경우 graph[v].push_back(u)도 수행
}

int main() {
    addEdge(0, 1);
    addEdge(1, 2);
    // 간선 추가 및 그래프 분석
    // ...
    return 0;
}

2. 그래프 분석

그래프 분석을 위한 알고리즘은 깊이 우선 탐색(DFS)이나 너비 우선 탐색(BFS) 등이 있습니다. 또한, 최단 경로 찾기, 연결 요소 분리, 사이클 찾기 등의 문제를 해결할 수 있습니다.

3. 참고 자료

C++ 그래프 이론과 응용, 산딸기책
C++로 배우는 알고리즘 문제해결전략, 구종만