✅ Graph (그래프)란?
노드(node)와 간선(edge)으로 이루어진 자료 구조
Graph 종류
그래프는 방향성에 따라 무방향 그래프(Undirected Graph), 방향 그래프(Directed Graph)로 나눌 수 있다.
1. 무방향 그래프 (Undirected Graph)
- 간선을 통해서 양 방향으로 갈 수 있다.
- 정점 A와 정점B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다.
(A, B) = (B, A) 동일
2. 방향 그래프 (Directed Graph)
- 간선에 방향성이 존재한다.
- A ➡ B로만 갈 수 있는 간선은 <A, B>로 표현한다.
<A, B>는 <B, A>와 다름
Graph 용어
- 노드(node)
위치라는 개념 (node라고도 부름) - 간선(edge)
위치 간의 관계 즉, 노드를 연결하는 선 - 인접 정점(adjacent verte)
간선에 의해 직접 연결된 정점 - 정점의 차수(degree)
무방향 그래프에서 하나의 정점에 인접한 정점의 수
➡ 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 무방향 그래프의 간선 수의 2배 - 진입 차수(in-degree)
방향 그래프에서 외부에서 오는 간선의 수 (내차수) - 진출 차수(outdegree)
방향 그래프에서 외부로 향하는 간선의 수 (외차수)
➡ 방향 그래프에 존재하는 정점의 진입 / 진출 차수의 합 = 방향 그래프의 간선의 수 - 경로 길이(path length)
경로를 구성하는 데 사용된 간선의 수 - 단순 경로(simple path)
경로 중에서 반복되는 정점이 없는 경우
🖋 Graph의 구현
graph를 코드로 표현하는 방법에는 크게 두 가지가 있는데 하나는 인접 리스트를 사용하는 방법과, 인접 배열을 사용하는 방법이 있다.
1. 인접 리스트(adjacency list)
인접 리스트는 각 노드에 인접한 다른 노드들을 하나의 연결 리스트로 표현하는 방법이다.
Nodes = {
1 : [1, 3],
2 : [2, 4],
3 : [1, 4],
4 : [2, 3],
5 : [1]
}
2. 인접 배열(adjacency matrix)
그래프를 구성하는 노드에 대해 두 노드를 연결한 간선의 유무를 저장할 때 정방행렬을 사용한다.
(행렬의 크기 = 노드의 수 x 노드의 수)
하나의 노드에서 자기 자신으로의 자체 간선은 있을 수 없으므로 인접 행렬의 대각선의 값은 항상 0이다. 무방향 그래프에서는 1[a][b]와 1[b][a]값이 같기 때문에 대각선을 기준으로 대칭을 이루고, 방향 그래프에서는 각기 다른 간선이기 때문에 대칭을 이루지 않는다.
if(A, B 연결) {
matrix[A][B] = 1;
} else {
matrix[A][B] = 0;
}
인접 리스트 vs 인접 행렬
인접 리스트 | 인접 행렬 |
간선이 적을 때 유용 | 간선이 많을 때 유용 |
장점 : 노드에 연결된 다른 노드를 쉽게 찾을 수 있다. | 장점 : 두 노드의 연결 여부를 즉시 알 수 있다. |
단점 : 연결 여부를 확인하려면 오래 걸린다. | 단점 : 연결된 다른 노드를 찾으려면 모든 노드를 조사해야 한다. |
🖋 그래프 메서드 (Method)
.addNode() : 정점(노드)를 추가
.contains() : 해당 노드의 존재유무 확인
.removeNode() : 해당 노드 제거
.hasEdge() : 두 노드 사이 간선 연결여부 확인
.addEdge() : 두 노드 사이 간선 추가
.removeEdge() : 간선 제거
'Computer Science > Data Structure' 카테고리의 다른 글
Hash Table (해시 테이블) (0) | 2021.01.23 |
---|---|
Linked List (연결 리스트) (0) | 2021.01.22 |
Stack&Queue (0) | 2021.01.20 |
댓글