그래프는 나에게 있어서 항상 어려운 자료구조였다.
이번 기회에 제대로 박살내보자.
개념
그래프는 정점(Vertex)와 간선(Edge)으로 구성된 집합이다.
간선의 특징에 따라 크게 3가지로 분류할 수 있다.
1) 무방향 그래프(undirected graphs)
간선의 방향이 없는 양방향 그래프
2) 방향 그래프(directed graphs)
간선의 방향이 있는 그래프
3) 가중치 그래프(weights graphs)
간선에 가중치(weight)가 있는 그래프
기타 종류
1. 연결, 비연결 그래프
연결그래프는 무방향그래프에서 모든 정점에 대해 연결이 되어 있는 그래프
ps) 이때 트리(Tree)는 그래프의 일종으로, 사이클을 가지지 않는 연결 그래프이다.
2. 사이클, 비순환 그래프
경로상에 중복되는 정점이 없으면 비순환 그래프이다.
3. 완전 그래프
그래프의 모든 정점에 대해 직접적으로 간선이 연결되어있는 그래프
단어 뜻 그대로 그래프의 간선이 방향, 가중치가 있는지 여부를 의미한다.
용어
정점(Vertex) : 데이터를 저장하는 위치
간선(Edge) : 정점을 연결
인접 정점 : 간선에 의해 직접적으로 연결되어 있는 정점
단순 경로 : 경로 중에 반복되는 정점이 없는 경로. 한붓그리기!
차수 : 무방향그래프에서 하나의 정점에 인접한 정점의 수
진입 차수 : 외부 정점에서 들어오는 간선의 수
진출 차수 : 외부 정점으로 나가는 간선의 수
사이클 : 경로 중에서 시작 정점과 끝 정점이 같은 경로
쓰임새
연결된 노드간의 관계를 표현할때 쓰이는 자료구조이다.
음 뭔가 지하철 노선도, 이동 경로, 친구 관계?에 사용될 수 있을거같다.
구현
그래프는 인접행렬과 인접리스트를 사용해 구현할 수 있다.
인접리스트(Adjacency List)
ArrayList 이차원 배열을 통해 그래프 정보를 저장할 수 있다.
List<Integer>[] graphInfo = new ArrayList[10];
for(int v=0; v<10; v++) {
graphInfo[v] = new ArrayList<>();
}
graphInfo[1].add(2);
graphInfo[1].add(3);이런식으로 정점 v 에 대해서 인접한 정점을 리스트에 추가하고,
graphInfo[v]에 접근하여 정점 v의 인접 정보를 활용할 수 있다.
인정행렬(Adjacency Matrix)
int[][] graphInfo = new int[n+1][n+1];
graphInfo[1][2] = 1;
graphInfo[2][1] = 1; // 무방향 그래프 일때
graphInfo[1][3] = 1;
graphInfo[3][1] = 1; // 무방향 그래프 일때이런식으로 정점 v에 대해서 정점에 대해서 배열에 값을 추가하고,
graphInfo[v1][v2]에 접근하여 정점간 인접 정보를 활용할 수 있다.
인접 리스트 VS 인접 행렬
과연 그래프를 구현하는데 어떤 자료구조를 사용하는 것이 좋을까?
결론은 그래프의 간선 정보에 따라 다르다.
밀집 그래프 : 인접 행렬 활용
그래프에 간선이 많은 밀집 그래프일때 인접 행렬로 그래프를 구현하는 것이 좋다.
인접 행렬의 장점은 인접 정보를 조회할때 O(1)의 시간 복잡도에 접근할 수 있다.
하지만 처음 간선 정보를 입력할때, 모든 정점간의 입력이 필요하므로 O(N^2)의 시간 복잡도와 무조건 2차원 배열의 크기가 필요하므로 필요 이상의 공간을 차지한다는 단점을 가지고 있다.
희소 그래프 : 인접 리스트 활용
그래프에 간선이 많지 않은 희소 그래프일때 인접 리스트로 그래프를 구현하는 것이 좋다. 인접 정보를 조회할때, O(N)의 시간 복잡도에 접근할 수 있다. 필요한 공간만을 이용하기 때문에 공간의 낭비가 적다. 조회 시간 복잡도는 인접 행렬에 비해 느리다. 하지만 공간 복잡도는 인접리스트가 효율적이다.
더 공부해볼 만한 주제
disjoint-set, union-find란 무엇일까?
