📖 그래프 기본
📌 그래프 기본
✅ 그래프
-
아이템(사물 또는 추상적 개념)들과 이들 사이의 연결 관계 포함
-
정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료구조
-
선형자료구조나 트리자료구조로 표현하기 어려운 M:N 관계 표현
-
무향 그래프(Undireted Graph) & 유향 그래프(Directed Graph)
-
가중치 그래프(Weighted Graph)
-
순환 그래프(Cycle Graph)
-
사이클 없는 방향 그래프(DAG, Directed Acyclic Graph)
- 트리는 부모가 하나이므로 이 경우는 아님
- 트리는 그래프일까?
- 완전 그래프
-
정점들에 대해 가능한 모든 간선들을 가진 그래프
-
무향 그래프다.
-
정점이 n개면 간선은 n*(n-1)/2
-
- 부분 그래프
- 원래 그래프에서 일부 정점이나 간선을 제외한 그래프
- 인접(Adjacency)
-
두 정점에 간선이 존재(연결됨)하면 서로 인접해 있다.
-
완전 그래프에 속한 임의의 두 정점들은 모두 인접
-
- 경로(Path)란 간선들을 순서대로 나열한 것
- 간선들 : (0, 2), (2, 4), (4, 6)
- 정점들 : 0 2 4 6
- 단순경로 : 경로 중 한 정점을 최대한 한번만 지나는 경로
- 0 2 4 6, 0 1 6
- 사이클(Cycle) : 시작한 정점에서 끝나는 경로
- 1 3 5 1
📌 그래프 표현 방법
✅ 그래프 표현
-
간선의 정보를 저장하는 방식, 메모리나 성능을 고려해서 결정
-
인접 행렬 (Adjacent matrix)
- |V| x |V| 크기의 2차원 배열을 이용해서 간선 정보 저장
- 배열의 배열 (Referrence Array)
-
인접 리스트 (Adjacent List)
- 각 정점마다 해당 정점으로 나가는 간선의 정보 저장
-
간선 배열 (Edge Array)
- 간선(시작 정점, 끝 정점)을 배열에 연속적으로 저장
✅ 인접 행렬
- 두 정점을 연결하는 간선의 유무를 행렬로 표현
-
|V| x |V| 정방 행렬
-
행 번호와 열 번호는 그래프의 정점에 대응
- 두 정점이 인접해있으면 1, 그렇지 않으면 0
-
무향 그래프
- i번째 행의 합 = i번째 열의 합 = Vi의 차수
-
유향 그래프
- 행 i의 합 = Vi의 진출 차수
- 열 i의 합 = Vi의 진입 차수
-
- 아래는 무향 그래프
- 아래는 유향 그래프
✅ 인접 행렬 장단점
-
장점 : 특정 정점끼리 인접한지 확인하는 것이 인접 리스트보다 빠르다.
-
단점 : 정점 대비 간선의 개수가 적다면 불필요한 메모리 공간이 낭비된다.
✅ 인접 리스트
-
각 정점에 대한 인접 정점들을 순차적으로 표현
-
하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결리스트로 저장
- ArrayList나 LinkedList를 활용하면 되겠다!
- 무 방향 그래프
- 노드 수 : 간선 수 * 2
- 각 정점의 노드 수 = 정점의 차수
- 방향 그래프
- 노드 수 : 간선의 수
- 각 정점의 노드 수 : 정점의 진출 차수
✅ 인접 리스트의 장단점
-
장점 : 인접 행렬의 메모리적 문제 해결
-
단점 : 특정 정점끼리 인접한지 확인하는데 인접행렬보다 오래 걸린다.
✅ 간선 배열
-
1차원 배열로 해도 되고, 2차원 배열로 해도 되고, Edge 클래스를 만들고 안에 int st, int ed를 넣어서 객체지향으로 사용해도 됨.
-
정점과 정점의 연결 정보인 간선을 배열에 저장
-
간선을 표현하는 두 정점의 정보를 배열 혹은 객체로 저장할 수 있다
