그래프를 구현하는 방법
그래프 정리
그래프(Graph)에 대해 알아보자
트리와 그래프 모두 대표적인 비선형 자료구조이다. 선형자료구조와 다르게 데이터 요소들이 계층적으로 연결되어 있다. 그렇다면 비선형 자료구조란 무엇일까? 비선형자료구조란? > 비선형 자
velog.io
위의 벨로그에 그래프에 대한 개념정리가 매우 잘되어있어서, 읽어보면 좋을것 같다
- 노드 = 정점
- 간선 = 엣지 : 노드 사이를 연결하는 선 (두 노드 사이의 연결관계)
그래프를 구현하는 방법
1️⃣ 엣지 리스트
엣지 리스트란 엣지를 중심으로 그래프를 표현하는 방법이다.
엣지리스트는 배열에 출발노드, 도착노드를 저장하여 그래프를 표현한다. 엣지에 가중치가 있는경우 출발노드, 도착노드, 가중치를 저장하여 그래프를 표현한다.
- 가중치가 없는 경우
가중치가 없는 그래프인 경우, 출발노드와 도착노드만을 저장하면 되므로 배열의 열은 2개면 충분하다.
1에서 2로 뻗어나가는 엣지는 [1,2]
2에서 5로 뻗어나가는 엣지는 [2,5]
이처럼, 방향이 있는 그래프는 순서에 맞게 노드를 배열에 저장하는 방식으로 표현한다.
각각의 행은 두 노드의 연결관계를 나타내고 있으므로 엣지를 의미한다.
이렇게 노드를 배열에 저장하여 엣지(연결관계) 를 표현하므로 엣지 리스트라 한다.
- 가중치가 있는 경우
가중치가 있는 경우는 가중치를 저장하는 열을 하나 더 추가하면 된다.
하지만 엣지리스트의 경우, 특정 노드와 관련된 엣지를 탐색하기는 쉽지 않다.
특정 노드와 관련된 엣지를 탐색하기 위해선 엣지 리스트 전체를 순회(출발노드와 도착노드 모두 확인해야함) 하며 특정 노드를 찾아야한다.
따라서 그래프에 N개의 엣지가 있는 경우, 특정 노드와 관련된 엣지를 찾기 위해선 O(N) 이 필요하다.
이러한 시간복잡도는 엣지의 개수가 많아질수록, 특정 노드와 관련된 엣지를 찾는것은 매우 많은 시간이 걸리게 될 것이다.
2️⃣ 인접행렬
인접행렬은 엣지 리스트와 반대로 노드를 중심으로 그래프를 표현하는 방법이다.
노드의 개수를 N 이라고 할때, NxN 크기의 2차원 배열을 이용하여 노드 사이의 관계를 나타낸다.
- 가중치가 없는 경우
1에서 2로 향하는 엣지를 1행2열에 1을 저장하는 방식으로 표현한다.
1을 저장하는 이유는 가중치가 없기 때문이다. 가중치가 있는 엣지라면 가중치의 값을 저장하면 된다.
이처럼 인접행렬로 그래프를 표현하는 것은, 엣지를 노드를 기준으로 표현한다.
- 가중치가 있는 경우
인접행렬로 그래프를 나타내는것은, 엣지의 여부와 가중치의 값을 배열에 접근하면 바로 확인 할 수 있다는 장점이 있다.
예를 들어, 3에서4로 향하는 엣지의 가중치를 알고 싶다면 A[3][4] 의 값을 읽으면 되므로 시간복잡도는 O(1) 이 된다.
하지만, 특정 노드와 관련되어있는 모든 엣지를 탐색하려면 엣지리스트와 동일하게 N번 접근해야하므로 시간복잡도는 O(N)이 걸린다.
또한 노드의 개수가 엄청나게 많을 경우, 2차원 배열 선언 자체를 할 수 없는 문제점도 있다. ( N*N개가 필요한데 N이 10만개만 되어도 엄청나게 많은 메모리공간을 필요로하게 됨)
3️⃣ 인접 리스트
인접 리스트는 ArrayList 자료형을 사용하여 그래프를 표현한다. 노드의 개수만큼 ArrayList를 선언한다.
ArrayList 배열을 만들어, 특정 노드와 연결관계가 있는 노드들을 차례대로 저장한다.
🧐 ArrayList를 쓰는 이유?
특정 노드와 연결되어있는 노드들을 저장하는 방식이 인접 리스트 방식이다.
이런 경우 2차원 배열을 이용해서도 구현 할 수 있을 것이다. 그런데 ArrayList를 이용해서 배열을 만들어 쓰는 이유가 뭘까?
배열의 경우, 생성과 동시에 크기가 선언되어야한다. 그렇기 때문에 그래프 전체를 파악하여 특정 노드에 연결된 엣지의 개수(노드의 개수와 동일)를 파악 할 수 있다면 크기를 선언해줄 수 있지만, 그렇지 않은 경우 공간을 비효율적으로 사용하게 될 수 있다.
그래서 크기가 가변적인 ArrayList를 이용한 배열을 만들어서 노드를 추가해주는 것이다.
ArrayList에 대한 내용은 아래 블로그를 읽어보면 될 것 같다
🧱 자바 ArrayList 구조 & 사용법 정리
ArrayList 컬렉션 자바의 컬렉션 프레임워크를 접한다면 가장 먼저 배우는 컬렉션이 ArrayList 일 것이다. 자료구조(Data Structure) 이라고 해서 무언가 방대하게 느껴져 접근이 어려울 것 처럼 느끼겠지
inpa.tistory.com
- 가중치가 없는 경우
가중치가 없는 경우, 노드와 연결되어있는 노드들만 차례대로 저장해준다.
- 가중치가 있는 경우
가중치가 있는 경우 자료형으로 클래스를 사용한다.
도착노드, 가중치를 갖는 클래스를 선언하여 ArrayList에 저장한다.
public class Node{
int startNode; // 출발노드
int value; // 가중치
Node(int startNode,int value){
this.startNode=startNode;
this.value=value;
}
인접 리스트를 이용한 그래프 구현 방법은, 위에서 제시한 두 방법들이 가지고 있는 문제점들을 보완한다.
- 특정 노드와 관련된 모든 엣지를 탐색하기 매우 용이하다 (1번의 값을 모두 읽으면 된다)
- 공간 효율이 좋아 노드의 개수가 많아지더라도 메모리 초과 에러가 발생하지 않는다
그래서 일반적으로 그래프를 구현할때는 인접 리스트를 이용한다.
🐸 출처
그래프 개념 정리 벨로그 : https://velog.io/@kwontae1313/트리와-그래프에-대해-알아보자
노드와 엣지 이미지 : 더북 모두의 인공지능 기초 수학 https://thebook.io/080246/0171/
그래프 그림 : Do it! 알고리즘 코딩 테스트 자바 편