-
[자료구조] 그래프개발/자료구조와 알고리즘 2022. 2. 16. 00:55
그래프
트리와 같이 노드와 간선으로 연결된 형태를 그래프라고 한다.
싸이클이 형성될 수 있기 때문에 계층적 자료구조라기 보다는 전체를 나타내는 형태로 생각할 수 있다.
따라서 부모-자식 관계나 루트노드 같은 성질이 없다.
위 그림에서 A-B-E-C-A의 사이클이 있다.
그래프에는 여러가지 특징이 있다.
먼저, 방향이 있는 그래프와 방향이 없는 그래프로 나눌 수 있다.
위에서 그린 그래프는 방향이 없는 그래프이고, 방향이 있는 그래프는 다음과 같다.
방향이 있을 때는 해당 방향으로만 진행할 수 있다는 특징이 있다.
다음으로는 모든 노드가 연결되어있지 않아도 된다는 것이다.
이를 비연결그래프, disjoint 그래프라 한다.
반면 모든 노드가 서로 연결되어있는 그래프는 완전그래프라 한다.
간선에 가중치를 둘 수 있다.
쉽게 예를 들면 거리라고 생각할 수 있다.
A에서 C로 가는 방법은 A-C로 바로 가는 것과, A-B-E-C를 가는 방법이 있다.
가중치를 거리라고 생각할 때, A-B-E-C로 가는 방법이 거리가 1 더 가까움을 알 수 있다.
그래프의 구현
그래프는 두가지 방법으로 구형할 수 있다.
먼저 인접행렬 방식이다.
각 노드에서 연결된 노드를 1로 하고, 연결되지 않은 노드는 0의 값을 갖는 행렬을 만든다.
만약 가중치가 있는 그래프일 경우 1대신 가중치를 넣을 수 있다.
인접행렬의 장점
- 두 노드를 연결하는 간선의 존재 여부를 $O(1)$만에 찾을 수 있다.
단점
- 그래프에 존재하는 모든 간선의 수는 $O(N^2)$만에 찾을 수 있다.
- 차지하는 메모리 공간이 크다.
그래프에 간선이 많을 경우 주로 사용
두번째로는 인접리스트 방식이다.
인접 리스트 방식은 각 노드에서 갈 수 있는 노드를 리스트형태로 저장한다.
이번에는 가중치까지 함께 저장한 모습이다.
인접리스트의 장점
- 모든 간선을 찾을 때 $O(N)$
단점
- 특정 두 노드가 연결되었는지 확인하려면 시간이 오래 걸린다.
그래프에 간선이 적을 경우 주로 사용
그래프의 탐색
그래프의 노드를 모두 찾기 위한 탐색방법에는 크게 두 가지가 있다.
- 깊이 우선 탐색 (DFS)
시작 노드로부터 연결된 노드들을 스택에 넣어 하나씩 탐색하는 방법
이렇게 탐색할 경우 그래프의 깊이를 먼저 탐색하게 된다.
주로 모든 노드를 방문할 필요가 있을 때 이 방법을 선택한다.
- 너비 우선 탐색 (BFS)
시작 노드로부터 연결된 노드들을 큐에 넣어서 하나씩 탐색하는 방법
이렇게 탐색할 경우 각 노드에 연결된 모든 노드를 먼저 탐색하게 되므로 너비 우선 탐색이라 한다.
주로 두 노드 사이의 최단 경로를 찾을 때 이 방법을 사용한다.
'개발 > 자료구조와 알고리즘' 카테고리의 다른 글
[알고리즘] 이진 탐색 (0) 2022.03.04 [자료구조] 해시(Hash) (0) 2022.02.21 [자료구조] 힙(Heap) (0) 2022.02.05 [자료구조] 이진 탐색 트리(Binary Search Tree) (0) 2022.01.31 [자료구조] 트리 (0) 2022.01.26