그래프
- 그래프는 아이템(사물 또는 추상적 개념)드로가 이들 사이의 연결 관계를 표현한다.
- 정점(Vertex) : 그래프의 구성요소로 하나의 연결점
- 간선(Edge) : 두 정점을 연결하는 선
- 차수(Degree) : 정점에 연결된 간선의 수
- 그래프는 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조
- V : 정점의 개수, E : 그래프에 포함된 간선의 개수
- V개의 정점을 가지는 그래프는 최대 V*(V-1)/2 개의 간선이 가능
- 선형 자료구조나 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소들을 표현하기에 용이하다.
그래프 유형
- 무향 그래프(Undirected Graph)
- 유향 그래프(Directed Graph)
- 가중치 그래프(Weighted Graph)
- 사이클 없는 방향 그래프(DAG, Directed Acyclic Graph)\
- 완전 그래프 : 정점들에 대해 가능한 모든 간선들을 가진 그래프
- 부분 그래프 : 원래 그래프에서 일부 정점이나 간선을 제외한 그래프
- 트리는 사이클이 없는 무향 연결 그래프이다.→ 각 노드는 최대 하나의 부모 노드가 존재할 수 있다.
- → 각 노드는 자식 노드가 없거나 하나 이상 존재할 수 있다.
- → 두 노드 사이에는 유일한 경로가 존재한다.
인접 정점
- 두 개의 정점에 간선이 존재(연결됨)하면 서로 인접해 있다고 한다.
- 완전 그래프에 속한 임의의 두 정점들은 모두 인접해 있다.
그래프 경로
- 경로(Path)란 어떤 정점(A)에서 시작하여 다른 정점(B)로 끝나는 순회로 두 정점 사이를 잇는 간선들을 순서대로 나열한 것
- 경로 중 한 정점을 최대 한 번만 지나는 경로를 단순 경로라고 한다.
- 순환 경로→ 경로에서 어떤 정점을 2번 이상 거치는 경우
- → 경로의 시작 점과 끝 점이 같음
그래프 표현
- 간선의 정보를 저장하는 방식, 메모리나 성능을 고려해서 결정
- 인접 행렬(Adjacent matrix)→ 배열의 배열(Reference Array)
- → V X V 크기의 2차원 배열을 이용해서 간선 정보를 저장 → 가중치 간선의 경우에는 INTEGER형으로, 아닌 경우에는 BOOLEAN형을 사용
- 인접 리스트(Adjacent List) → 각 정점마다 다른 정점으로 나가는 간선의 정보를 저장
- 간선 리스트(Edge List) → 간선(시작 정점, 끝 정점) 의 정보를 객체로 표현하여 리스트에 저장
인접 행렬
- 두 정점을 연결하는 간선의 유무를 행렬로 표현 → V X V 정방 행렬 → 행 번호와 열 번호는 그래프의 정점에 대응 → 두 정점이 인접되어 있으면 1, 그렇지 않으면 0으로 표현
- 무향 그래프
- i 번째 행의 합 = i 번째 열의 합 = Vi의 차수
- 유향 그래프
- 행 i의 합 = Vi의 진출 차수
- 열 i의 합 = Vi의 진입 차수
인접 리스트
- 각 정점에 대한 인접 정점들을 순차적으로 표현
- 하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결리스트로 저장
간선 리스트
- 두 정점에 대한 간선 그 자체를 객체로 표현하여 리스트로 저장
- 간선을 표현하는 두 정점의 정보를 나타냄(시작 정점, 끝 정점)
'Algorithms > 개념 정리' 카테고리의 다른 글
[문자열] 문자열 패턴 매칭 (0) | 2021.04.06 |
---|---|
[Graph] 최단 경로 (0) | 2021.03.30 |
[Graph] 최소 신장 트리(MST) (0) | 2021.03.29 |
[Graph] 서로소 집합 (0) | 2021.03.26 |
[Graph] Graph 탐색 (0) | 2021.03.25 |