그래프 :
데이터들의 관계를 여러 개의 노드(node)와 이들을 연결하는 간선(edge)으로 표현한 자료구조이다.
노드는 정점(vertex)이라고도 하며, 방향성 있는 간선을 arc라고 하기도 한다.
그래프는 대표적인 비선형 자료구조다.
비선형 자료구조는 선형 자료구조와 달리 데이터를 일렬로 구성하지 않고,
자료 순서나 관계가 복잡한 자료구조를 말한다.
데이터 요소를 계층적으로 저장, 표현해 분기점이나 사이클 등이 존재한다.
비선형 자료구조는 선형 자료구조보다 복잡하지만 다양한 문제를 해결할 때 활용할 수 있다.
다른 노드로 나가는 간선을 해당 노드(정점)의 outdegree(도, 길)라고 하며,
들어오는 간선을 indegree라고 한다.
그래프의 장점
- 복잡한 관계를 직관적으로 표현할 수 있다.
- 네트워크 구조를 표현할 수 있어서 소셜 네트워크, 전력망, 노선도 등의 문제를 다룰 수 있다.
가장 대표적인 것이 네비게이션의 최단 경로 안내 - 다양한 최적화 문제를 풀 수 있다.
-> 최단 경로 문제나 최소 신장 트리 문제 등 다양한 그래프 알고리즘을 사용하여 최적화 할 수 있다.
단점
- 데이터의 규모가 커질수록 계산 비용이 증가한다.
대형 그래프에서는 탐색 비용과 알고리즘의 수행 시간 등이 중요한 문제가 될 수 있다. - 그래프의 구성이 복잡하면 이를 이해하기 어려울 수 있다.
- 방향성 그래프에서는 경로의 유무가 중요하므로, 경로가 존재하지 않는 경우에는
이를 고려하여 알고리즘을 설계해야 한다.
극복 방향
-> 분할 정복, 동적 계획법(DP) 등의 최적화 알고리즘을 사용하여 계산 비용을 줄일 수 있다.
->그래프를 단순화하여, 경로가 존재하지 않는 경우에도 유용한 결과를 도출할 수 있도록 만든다.
예로, 가중치를 조절하여 일정 이하의 가중치를 가진 간선들은 무시하는 방법을 생각할 수 있다.
그래프의 특징
- 방향성(Directionality): 그래프의 간선은 방향성을 가질 수 있다. 그래프의 방향성은 한 쪽 방향으로만 이동할 수 있다. 양방향도 구현할 수 있음. 방향성이 있는 그래프를 방향 그래프라고 한다
- 무방향성(Unidirectionality): 간선은 방향성이 없을 수 있다. 없는 경우 양 쪽 방향으로 모두 이동할 수 있다.
방향성이 없는 그래프를 무방향/양방향 그래프라고 한다. - 가중치(Weight): 간선에는 가중치를 부여할 수 있다.
가중치를 부여한 그래프를 가중치 그래프라고 부르며, 거리, 비용, 우선순위 등을 나타낼 때 사용한다. - 연결성(Connectivity): 노드와 노드 사이에 간선이 존재하면, 두 노드는 연결되었다고 말한다.
그래프가 연결되어 있는 경우 연결 그래프 라고 하고, 그렇지 않은 경우 비연결 그래프라고 한다. - 사이클(Cycle): 한 노드에서 시작하여 경로를 따라가다 마침내 자기 자신으로 돌아오는 경로를 사이클이라고 부른다. 사이클이 없는 그래프를 비순환 그래프, 사이클이 있는 그래프를 순환 그래프라고 한다.
>> 순환 그래프의 기준은? 한 노드는 사이클에 참여하지 않아도 순환 그래프인가?
- 일부라도 사이클이 가능한 그래프면 순환 그래프 - 차수(Degree): 그래프에서 한 노드에 인접한 간선의 수를 차수라고 부른다.
무방향 그래프에서는 노드의 차수가 연결된 노드의 수와 같으며, 방향 그래프에서는 인접한 노드의 수와 나가는 노드의 수로 구분된다.
무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배
그래프의 종류
- 무방향(양방향) 그래프: 간선에 방향성이 없는 그래프를 무방향(Undirectionality) 그래프라고 한다.
방향성이 강제되지 않는다는 얘기는 양쪽 방향으로 모두 이동할 수 있다는 의미다. - 방향성 그래프: 방향성을 갖는 그래프는 정해진 한 쪽 방향으로만 이동할 수 있다.
방향(Directed) 그래프 또는 유향 그래프(digraph)라고 부른다.
[백준10971번 외판원 순회 2]를 보면 입력으로 주어지는 2차원 배열이 그래프의 특징을 갖고 있다. - 가중치 그래프: 간선에 가중치가 있는 그래프
- 이분 그래프(Bipartite Graph): 무방향 그래프에서 노드를 두 그룹으로 나누었을 때,
같은 그룹 내의 노드는 서로 인접하지 않고, 다른 그룹의 노드와만 인접하는 그래프이다. - 순환 그래프: 단순 경로의 시작 정점과 종료 정점이 동일한 경우
-> 단순경로란/경로 중에서 반복되는 정점이 없는 경우 - 비순환 그래프(Acyclic Graph): 사이클이 없는 그래프이다. 방향 그래프에서, 유향 비순환 그래프(DAG)라고도 한다.
모든 노드로 이동 가능한 무방향 그래프를 완전 그래프
주어진 그래프의 일부 노드와 간선으로 이뤄진 그래프가 부분 그래프
>> 연결 그래프의 기준은?
무방향 그래프에서 간선이 연결되지 않은 동떨어진 노드가 있으면 비연결 그래프.
무방향 그래프에서 모든 노드에 하나 이상 간선이 연결되어 있으면 연결 그래프.
모든 노드로 양방향 이동 가능한 방향 그래프를 강결합 그래프라고 한다.
떨어진 간선, 노드가 있으면 단절 그래프
루트가 없는 트리도 그래프입니다.
그래프 표현, 구현 방식
간선: E
노드: V
가중치: W
인접 행렬: O(V^2)의 공간 복잡도, 메모리 필요
인접 리스트: O(V+E) 메모리 필요 -> 간선이 적은 경우 유리함
인접 행렬: 2차원 배열로 정점 간의 간선의 존재 여부를 1 또는 0으로 표현
인접 리스트: 정점 개수만큼 리스트를 만들어 각각의 정점 리스트에 간선 추가
각 구현 방법의 특징
- 인접 행렬로 표현하는 경우 항상 노드 개수의 제곱만큼 메모리가 필요한데 간선이 매우 적은 경우 비효율적이다. 탐색을 할 때도 연결되지 않은 간선까지 확인해야 되기 때문에 느리다.
- 인접 리스트는 메모리도 조금만 사용하며 탐색할 때도 연결된 간선만 보기 때문에 빠르다.
인접 리스트 -> 배열 또는 해시테이블과 각 인덱스마다 존재하는 또 다른 리스트(배열, 동적 가변 크기 배열)를
이용해서 인접 리스트를 표현
정점의 번호만 알면 이 번호를 배열의 인덱스로 하여 각 정점의 리스트에 쉽게 접근할 수 있다.
무방향 그래프는 간선을 두 번 저장한다.
한 번은 a 정점에 인접한 간선을 저장하고, 다른 한 번은 b에 인접한 간선을 저장한다.
정점의 수 : N, 간선의 수 : E인 무방향 그래프의 경우
N의 리스트, N개의 배열, 2E개의 노드가 필요
인접 행렬 -> 노드 N개 일 때 NxN Boolean 행렬로 M[ i ][ j ]가 true라면 i -> j로의 간선이 있다는 뜻이다.
0과 1을 사용하기도 한다.
무방향 그래프를 인접 행렬로 표현한다면 이 행렬은 대칭 행렬이 된다.
-> 방향 그래프는 대칭 행렬이 안 될 수도 있다.
인접 리스트를 사용한 그래프 알고리즘들 또한 인접 행렬에서도 사용이 가능하다.
- 인접 행렬은 조금 효율성이 떨어진다.
- 인접 리스트는 어떤 노드에 인접한 노드들을 쉽게 찾을 수 있지만
인접 행렬에서는 인접한 노드를 찾기 위해 모든 노드를 전부 순회해야 한다.
상황에 따라 어떤 방식으로 구현할 지 선택해야 한다.
인접 리스트
그래프 내에 적은 숫자의 간선을 갖는 희소 그래프의 경우
인접 행렬
그래프에 간선이 많이 존재하는 밀집 그래프의 경우
그래프를 순회하는 방식이 DFS와 BFS로 나뉜다.
출처:
그래프(Graph)에 대해 알아보자
트리와 그래프 모두 대표적인 비선형 자료구조이다. 선형자료구조와 다르게 데이터 요소들이 계층적으로 연결되어 있다. 그렇다면 비선형 자료구조란 무엇일까? 비선형자료구조란? > 비선형 자
velog.io
https://laboputer.github.io/ps/2017/09/29/graph/
[자료구조 1] 그래프(Graph) 이해하기
그래프(Graph)가 무엇이고 어디에 활용되는지 알아봅니다. 그리고 그래프와 관련된 기초 문제를 풀어봅니다.
laboputer.github.io
https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html
[자료구조] 그래프(Graph)란 - Heee's Development Blog
Step by step goes a long way.
gmlwjd9405.github.io
'알고리즘' 카테고리의 다른 글
| LCS (Longest Common Subsequence) (2) | 2024.01.25 |
|---|---|
| 최소 신장 트리란? (0) | 2024.01.21 |
| 이진 탐색 알고리즘 (0) | 2024.01.19 |
| B-Tree란? (0) | 2024.01.19 |
| 피보나치 수열(반복문, 재귀함수) (0) | 2024.01.16 |
