[c++] 그래프(Graph) 데이터 구조

08 Dec 2023

그래프는 여러 노드(node)와 그 노드들을 연결하는 간선(edge)으로 구성된 데이터 구조입니다. 그래프는 노드들 간의 관계를 나타내기 위해 사용됩니다. 노드는 보통 지점이나 객체를 나타내고, 간선은 노드들 간의 관계를 나타냅니다.

그래프의 종류

무방향 그래프(Undirected Graph): 간선에 방향이 없는 그래프입니다.
방향 그래프(Directed Graph): 간선에 방향이 있는 그래프입니다.
가중 그래프(Weighted Graph): 간선에 가중치가 있는 그래프입니다.

그래프의 표현

그래프는 인접 행렬(Adjacency Matrix)이나 인접 리스트(Adjacency List)로 표현될 수 있습니다.

인접 행렬(Adjacency Matrix)

인접 행렬은 2차원 배열을 사용하여 그래프를 표현하는 방식입니다. 각 노드간의 연결 여부를 나타내기 위해 0과 1을 사용합니다.

int adjMatrix[5][5] = {
    {0, 1, 1, 0, 0},
    {1, 0, 0, 1, 0},
    {1, 0, 0, 1, 1},
    {0, 1, 1, 0, 1},
    {0, 0, 1, 1, 0}
};

인접 리스트(Adjacency List)

인접 리스트는 각 노드의 인접한 노드들을 연결 리스트로 표현하는 방식입니다. 각 노드별로 연결된 노드들을 리스트로 저장합니다.

vector<int> adjList[5];
adjList[0].push_back(1);
adjList[0].push_back(2);
adjList[1].push_back(0);
adjList[1].push_back(3);
adjList[2].push_back(0);
adjList[2].push_back(3);
adjList[2].push_back(4);
adjList[3].push_back(1);
adjList[3].push_back(2);
adjList[3].push_back(4);
adjList[4].push_back(2);
adjList[4].push_back(3);

그래프의 탐색

그래프 탐색은 그래프 내의 모든 노드를 방문하는 과정을 말합니다. 대표적으로 깊이 우선 탐색(Depth First Search, DFS)와 너비 우선 탐색(Breadth First Search, BFS)이 있습니다.

프로그래밍 언어별로 그래프 구현 및 탐색에 대한 다양한 자료 및 라이브러리가 제공되고 있으며, 실제 그래프 알고리즘을 구현하고자 한다면 해당 언어의 문서 및 관련 자료를 참고하는 것이 좋습니다.

결론

그래프는 다양한 응용 분야에서 활용되며, 이를 효과적으로 다루기 위해서는 그래프의 구조와 다양한 알고리즘에 대한 이해가 필요합니다. 다음은 그래프 알고리즘 및 응용 분야에 대해 더 자세히 배우고 싶다면 관련 자료를 찾아보는 것이 좋습니다.

참고 문헌:

Sedgewick, R., & Wayne, K. (2011). Algorithms. Pearson Education.