📝 그래프의 정의
연결되어있는 객체간의 관계를 표현한 자료구조이다.
❗ 관련 용어
정점 (vertex) : 노드(node), 데이터가 저장되는 위치
간선 (edge) : 링크(link), 정점 간의 관계, 노드를 연결하는 선
인접 정점 (adjacent vertex) : 간선에 의해 직접 연결된 정점
정점의 차수 (degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수
진입 차수 (in-degree) : 방향 그래프에서 외부에서 오는 간선의 수 (내차수)
진출 차수 (out-degree) : 방향 그래프에서 외부로 향하는 간선의 수 (외차수)
경로 길이(path length) : 경로를 구성하는 간선의 수
단순 경로(simple path) : 경로 중에서 반복되는 정점이 없는 경우
사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우
🎯 그래프의 특징
- 트리도 그래프의 한 종류, 사이클이 허용되지 않는 그래프를 말한다.
- 그래프는 네트워크 모델이다.
- 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
- self-loop 뿐만 아니라 loop/circuit 모두 가능하다.
- 루트 노드라는 개념이 없다.
- 부모-자식 관계라는 개념이 없다.
- 순회는 DFS나 BFS로 이루어진다.
- 그래프는 순환(Cyclic) 혹은 비순환(Acyclic)이다.
- 그래프는 크게 방향 그래프와 무방향 그래프가 있다.
- 간선의 유무는 그래프에 따라 다르다.
그래프 표현방법
1) 인접행렬
- 무방향 그래프를 구현하면 정점들을 배열의 인덱스로 표현한다.
- 주 정점이 연결되면 1, 연결되지 않으면 0으로 표현하고 자기 자신으로 연결되는 loop가 없으므로 배열의 대각선은 모두 0이 된다.
- 방향 그래프를 구현하면 정점들을 배열의 인덱스로 표현하고 해당 정점에서 다른 정점으로 가는 간선이 있다며 1로 없다면 0으로 표현한다.
2) 인접리스트
- 무방향 그래프를 인접리스트로 구현하면 각각 정점을 head로 시작해 인접한 노드들을 전부 연결리스트로 연결해준다.
- 방향 그래프를 구현할 때는 각 정점을 head로 시작해 들어가는 노드를 전부 연결리스트로 연결한다.
❗ 인접행렬과 인접리스트의 효율성
1) 정점은 많은데 간선수가 적은 희소 그래프를 구현하려면 인접리스트가 효율적이다.
- 인접행렬의 공간복잡도는 O(V^2)
- 인접리스트의 공간복잡도는 O(V+E) (V-정점의개수, E-간선의 개수)
2) 정점이 적고 간선의 수가 많은 밀집 그래프는 인접행렬로 구현하는것이 효과적이다.
- 행렬의 접근성 때문에 인접행렬은 정점과의 연결을 파악할 때 인덱스를 이용하므로 O(1)이면 충분
- 인접리스트는 해당 노드를 찾을 때까지 탐색을 진행해야 하므로 많은 시간이 필요
그래프의 탐색
깊이 우선 탐색 (DFS : Depth First Search)
- DFS는 그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 다른 정점으로 계속 나아가는 방법을 우선으로 하는 탐색법이다.
너비 우선 탐색(BFS : Breadth First Search)
- BFS는 그래프 상에 존재하는 임의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다.
- BFS에서는 큐 자료구조를 이용해 탐색 순서를 설정할 수 있다.
- 주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다
참고자료
도라에몽 암기빵