Graph !?
- 노드와 다른 노드를 연결하는 엣지를 하나로 모아 놓은 자료 구조.
- 연결되어 있는 객체 간 관계를 표현할 수 있는 자료 구조이다.
- 정점간의 관계를 표현하는 조직도
ex)
지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로, 선수 과목 등
트리와의 관계 🧐
- 정점간의 관계를 표현하기에 트리는 그래프의 일종이다.
- 그러나, 트리와 다르게 그래프는 정점마다 간선이 없을 수도 있고 있을 수도 있다.
- 트리와 다르게 루트 노드, 부모,자식 개념이 존재 하지 않는다.
- 객체와 이에 대한 관계를 나타내는 유연한 방식으로 이해할 수 있다.
트리와 그래프 차이
트리
- 루트라는 시작 점이 존재
- 트리는 루프 발생할 수 없다.
- 부모 자식 관계가 있다.
- 순회 : pre/ in/ post : DFS || level : BFS
그래프
- 네트워크 모델
- 그래프는 Loop 발생할 수 있다.
- 부모 자식 관계가 없다.
- 탐색 : DFS, BFS
특징
- 그래프는 네트워크 모델이다. 2개 이상의 경로가 가능하다.
- 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
- self-loop뿐 아니라 loop/circuit 모두 가능하다.
- 루트 노드라는 개념이 없다.
- 부모-자식 관계라는 개념이 없다.
- 순회는 BFS, DFS로 이루어진다.
구현 방법
인접행렬(Adjacency Materix)와 인접리스트(Ajacency List) 방식이 있다.
2가지 구현 방식은 각각의 상반된 장단점을 갖고 있는데 대부분 인접리스트 형식을 많이 사용한다.
인접행렬 방식
- 인접행렬은 그래프의 노드를 2차원 배열로 만든 것이다.
- 1,2,3,4,5,6 정점을 연결하는 노드에 다른 노드들이 인접 정점이라면 1, 아니라면 0을 넣어준다.
장점
- 2차원 배열안에 모든 정점들의 간선 정보를 담기에 배열의 위치를 확인하면 두 점에 대한 연결 정보를 조회할 때 O(1)의 시간 복잡도면 가능하다.
- 구현이 비교적 간편하다.
단점
- 모든 정점에 대해 간선 정보를 대입해야 하므로 O(n^2)의 시간 복잡도가 소요된다.
- 무조건 2차원 배열이 필요하기에 필요 이상의 공간 낭비가 된다.
인접리스트 방식
- 그래프의 노드들을 리스트로 표현하는 것
- 주로 정점의 리스트 배열을 만들어 관계를 설정해준다.
장점
- 정점들의 연결 정보 탐색에 O(n)의 시간이면 가능하다.
- 필요한 만큼의 공간만 사용하기에 공간 낭비가 적다.
단점
- 특정 두 점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래 걸린다.
(배열보다 검색 속도가 느리다.) - 구현이 비교적 어렵다..
그래프의 탐색
물론 하나하나 매우 중요한 것이기에 따로 다루겠지만 여기선 간단하게 다루겠다.
-
깊이 우선탐색(DFS)
: 갈 수 있는 만큼 최대한 깊이 가고, 갈 곳이 없다면 이전 정점으로 돌아가는 방식의 그래프 순회 법.
: 재귀 호출을 이용해 구현하거나 스택을 사용하여 구현한다. -
넓이 우선탐색(BFS)
: 시작 정점 방문 후 시작 정점에 인접한 모든 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 일반적으로 Queue를 사용해서 지금 위치에서 갈 수 있는 것들을 모두 큐에 넣는 방식으로 구현한다.
developer