자료구조 - 그래프(Graph) 그림으로 쉽게 이해하기
안녕하세요.
로스윗의 코딩캠프입니다.
오늘은 많은 사람들이 궁금해하시고 많이들 헷갈려하시는 내용을 바탕으로
자료구조 - 그래프(Graph) 그림으로 쉽게 이해하기에 대해서 같이 알아보겠습니다.
그림으로 쉽게 이해할 수 있으니 끝까지 잘 따라와주세요 :)
바로 시작하겠습니다.
- 그래프(Graph)란?
이번 포스팅에서는 그래프의 자료구조에 대해서 알아보겠습니다.
우선 그래프는 vertex와 edge로 구성된 자료구조입니다. vertex는 우리가 여태 써왓던 노드와 비슷한 개념이고 edge는 vertex간에 연결 관계를 나타냅니다. 그리고 두 vertex가 edge로 연결되어 있다면 두 vertex는 '인접해있다'고 말합니다.
앞에서 배운 트리도 그래프의 일종이지만 그래프는 트리보다 훨씬 더 넓은 범위를 포함하고 있습니다.
- 자료구조 그래프의 활용 예시
그래프는 굉장히 다양한 곳에서 많이 활용되고 있습니다.
우리가 너무너무 잘 알고 있는 자동차의 네비게이션 길찾기 기능에서 이 그래프를 이용한 탐색 알고리즘이 적용되어 있고, 게임에서 캐릭터의 이동에 활용되는 알고리즘도 이 그래프의 자료구조를 기반으로 합니다. 그리고 검색에서 사용되는 지식 그래프도 이름에서 알수 있듯이 그래프의 자료구조를 기반으로 합니다.
- 지식 그래프란?
지식 그래프가 생소하실 수 있는데요, 간단히 설명드리자면 전통적인 방식의 검색기능은 키워드 기반으로 해당 키워드에 대한 정보는 빠르게 얻을 수 있지만 그와 연결된 정보는 찾기 어렵다는 한계가 있었습니다. 지식 그래프는 각 객체의 연결성을 edge로 연결시켜서 그와 연결된 정보를 함께 탐색해줍니다. 이렇게 데이터들 간에 연관관계가 있을 때 그 연관정보를 가장 잘 관리할 수 있는 자료구조가 그래프이기 때문에 그래프를 사용하는 것입니다.
- 쾨니히스베르크의 다리 문제
그래프의 대표적인 문제중 하나로 쾨니히스베르크의 다리 문제가 있습니다.
쾨니히스베르크의 다리 문제는 '왼쪽 그림과 같은 지형이 있을 때 A, B, C, D중 임의의 한 곳에서 출발 했을 때 모든 다리를 한 번씩 건널 수 있는가'에 대한 문제입니다. 여러분도 잠시 한 번 생각해보시기 바랍니다.
왼쪽 그림을 그래프로 나타내면 오른쪽과 같은 vertex와 edge로 나타낼 수 있고, 이 문제에 대한 답은 '정답없음'으로 결론이 났었습니다. 그래프는 vertex와 edge로 구성되어 있다면 굉장히 다양한 형태로 나타낼 수 있습니다. 그리고 그 특징들에 따라서 그래프들의 종류를 구분할 수 있습니다.
- 방향그래프(directed graph)
먼저 방향그래프입니다.
그래프에서 vertex간의 관계인 edge는 방향성을 가질 수 있습니다. 아래 그림처럼 화살표로 방향을 표시할 수 있는 그래프를 방향그래프라고 합니다. 반대로 방향이 없는 그래프는 무방향 그래프라고 해서 undirected graph라고 합니다. 방향이 있는 그래프에서는 무조건 방향의 순서대로만 노드를 이동시킬 수 있습니다.
- 가중치 그래프
가중치 그래프는 edge에 가중치가 주어진 그래프입니다.
이 가중치는 양수도 될 수 있고 음수가 될 수도 있습니다. 아래 그림과 같은 가중치 그래프에서 A에서 B로 이동할 수 있는 경로는 두가지가 있습니다.
A에서 B로 바로 이동하거나 또는 A에서 C를 거쳐서 B로 이동하는 방법이 있습니다.
만약 가중치가 없다면 A에서 B로 바로 가는것이 가장 빠른 방법이겠지만 이 그래프의 edge에는 가중치가 있습니다. 그래서 A에서 B노드로 바로 이동할때는 7이라는 비용을 소모하지만 A에서 C를 거쳐서 B를 갈 경우 1과 2를 거쳐 총 3이라는 비용을 소모하게 됩니다. 그래서 C를 거쳐가는 것이 더 효율적인 방법이 되는거죠.
이렇게 가중치가 있는 그래프에서 한 vertex에서 다른 vertex까지의 최단경로를 찾기 위해서 다익스트라 알고리즘이나 벨만포드 알고리즘을 사용할 수 있습니다. 이 두 알고리즘에 대해서는 추후 포스팅 하도록 하겠습니다. 그리고 그래프의 vertex는 자기 자신을 가리키는 edge를 가질 수도 있는데 그때 이 edge를 루프(loop)라고 합니다.
- 순환 그래프(cyclic graph)
순환그래프란 어느 한 vertex에서 어떤 경로를 지나서 다시 그 vertex로 돌아오는 그래프를 말합니다.
아래 그림의 그래프 모두 사이클이 있는 순환그래프 입니다.
첫번째 그래프은 딱 봐도 자기들끼리 사이클을 만들고 있고, 두번째 그래프는 일부에서 사이클을 구성하고 있습니다. 세번재 그래프도 역시 사이클을 돌고 있습니다. 그리고 사이클이 없는 그래프는 uncyclic graph라고 합니다. 앞에서 배운 트리는 사이클이 없고, 방향이 있는 directed uncyclic graph의 한 종류가 됩니다.
- 그래프 구현
자료구조 그래프를 구현하는 방법은 보통 두가지가 있습니다. 그리고 각각의 장단점에 대해서도 알아보겠습니다.
1) 인접 행렬을 이용한 벙법
첫 번째는 인접행렬을 이용한 방법입니다. 인접 행렬은 2차원 배열로 표현할 수 있는데 오른쪽 그림과 같은 그래프가 있을 때
연결된 vertex의 위치에는 1, 아닌 경우에는 0이나 음수를 넣어서 표시를 할 수 있습니다.
위 행렬 표를 보면 A에서 다시 A로 연결되는 edge 즉, loop가 없기 때문에 이 위치에는 0이 들어갑니다. A와 B는 서로 edge로 연결되어 있기 때문에 1이 들어가게 되고 A와 B는 서로 연결이 되어 있지 않기 때문에 0이 들어가게 됩니다. 이런식으로 우선은 직관적으로 vertex간의 연결 정보를 파악하기 쉽다는 장점이 있는 반면에 노드 개수가 n개라면 표처럼 n제곱에 해당하는 메모리 공간을 사용해야 한다는 단점도 있습니다. 그리고 노드간의 연결정보인 edge를 추가하거나 삭제하는 연산은 간단하지만 새로운 노드를 추가하게 되면 연산의 복잡도가 올라가게 됩니다.
2) 인접리스트 방식
두번째 방식은 인접리스트 방식입니다.
여기서는 vertex의 개수 만큼만 list를 생성하게 됩니다. 그래서 자신을 기준으로 연결된 vertex만 리스트에 저장을 하게됩니다. A노드 같은 경우에는 B와 D와 연결되어 있기 때문에 B와 D의 정보를 리스트에 갖게 되고, B노드 같은 경우에는 A와 C와 연결되어 있기 때문에 A와 C의 정보를 리스트에 갖게 됩니다. 나머지 vertex도 동일하게 적용이 되겠죠.
인접리스트 방식은 인접행렬보다 메모리 공간을 효율적으로 쓸 수 있다는 장점이 있습니다. 그리고 노드를 새로 추가하거나 삭제하는 것도 인접행렬보다 훨씬 더 수월합니다. 하지만 리스트만 보고 vertex같의 연결관계를 파악하는데는 인접행렬보다 시간이 더 소요된다는 단점이 있습니다.
오늘은 이렇게 자료구조 - 그래프(Graph) 그림으로 쉽게 이해하기에 대해서 알아보았습니다.
다음 포스팅도 많이 기대해주세요!
감사합니다.
'컴퓨터 공학 > 자료구조와 알고리즘' 카테고리의 다른 글
| 자료구조 - 그래프 탐색 DFS 그림으로 쉽게 이해하기 (0) | 2023.01.02 |
|---|---|
| 자료구조 - 그래프 탐색 BFS 그림으로 쉽게 이해하기 (0) | 2023.01.01 |
| 자료구조 - 힙(Heap) 그림으로 쉽게 이해하기 (0) | 2022.12.25 |
| 자료구조 - 이진탐색트리(BST) 그림으로 쉽게 이해하기 (0) | 2022.12.21 |
| 자료구조 트리탐색 - 후위탐색(Postorder) 그림으로 쉽게 이해하기 (0) | 2022.12.19 |
