그래프 데이터 구조 및 Algorithms (예)
사라 첸
⚡ 스마트 요약
그래프 데이터 구조는 정점과 간선의 비선형 집합이며, 각 간선은 두 정점을 연결합니다. 그래프는 지도, 소셜 네트워크, 웹 페이지와 같은 실제 네트워크를 모델링하며, 다양한 강력한 알고리즘을 지원합니다.
데이터 구조의 그래프란 무엇입니까?
그래프는 정점과 간선으로 구성된 비선형 데이터 구조이며, 정점은 정보나 데이터를 담고 있고, 간선은 두 정점을 연결하는 역할을 합니다.
그래프는 목적지까지의 최적 경로 찾기, 통신 및 소셜 네트워크 경로 설정과 같은 실제 문제를 해결하는 데 사용됩니다. 사용자는 그래프의 노드로 간주되며, 와이어는 사용자들을 연결하는 엣지로 표현됩니다.
모서리가 E로 표시되고 꼭지점은 V로 표시되면 그래프 G는 다음과 같이 꼭지점과 모서리의 집합으로 작성될 수 있습니다. G(V, E).
데이터 구조의 그래프 예
다음은 그래프 데이터 구조의 간단한 예입니다.
이는 단순한 무방향 그래프(그래프의 한 종류)입니다. 꼭짓점 집합은 {A, B, C, D, E, F}입니다. 두 꼭짓점은 간선을 형성합니다. 예를 들어, A와 B는 간선으로 연결되어 있습니다. 하지만 A와 F는 어떤 간선으로도 연결되어 있지 않습니다.
데이터 구조의 그래프 용어
그래프 데이터 구조에서 사용되는 몇 가지 중요한 용어는 다음과 같습니다.
| 기간 | 기술설명 |
|---|---|
| Vertex | 각 데이터 요소를 정점 또는 노드라고 합니다. 위 이미지에서 A, B, C, D, E는 정점입니다. |
| 모서리(호) | 두 노드 또는 정점 사이를 연결하는 링크를 간선(호)이라고 합니다. 간선은 두 개의 끝점을 가지며 (시작 정점, 끝 정점)으로 표현됩니다. |
| 방향이 지정되지 않은 가장자리 | 양방향 엣지입니다. |
| 방향성 가장자리 | 단방향 모서리입니다. |
| 가중치 가장자리 | 값이 표시된 모서리. |
| 도 | 그래프에서 한 정점에 연결된 간선의 수를 차수라고 합니다. |
| 인도 | 정점에 연결된 들어오는 가장자리의 총 수입니다. |
| 외도 | 정점에 연결된 나가는 가장자리의 총 개수입니다. |
| 자가 루프 | 두 끝점이 일치하는 모서리를 자체 루프라고 합니다. |
| 인접 | 정점들 사이에 간선이 연결되어 있으면 두 정점은 인접해 있다고 합니다. |
데이터 구조의 그래프 유형
다음은 가장 일반적인 목록입니다. 데이터 구조의 그래프 유형:
- 방향성 그래프
- 무향 그래프
- 가중 그래프
- 양방향 그래프
- 무한 그래프
- 널 그래프
- 간단한 그래프
- 멀티 그래프
- 완전한 그래프
- 연결된 그래프
- 순환 그래프
- 방향성 비순환 그래프 (DAG)
- 사이클 그래프
- 이분 그래프
- 오일러 그래프
- 해밀턴 그래프
데이터 구조에서 그래프를 표현하는 방법은 무엇인가요?
그래프는 일반적으로 두 가지 표현 방식 중 하나를 사용하여 메모리에 저장됩니다. 어떤 방식을 선택하느냐에 따라 그래프가 사용하는 메모리 양과 일반적인 연산 실행 속도가 달라집니다.
- 인접 행렬: 정점 i와 정점 j 사이에 간선이 존재하면 셀 [i][j]는 1(또는 간선 가중치)이고, 그렇지 않으면 0인 2차원 V × V 배열입니다. 간선 조회는 O(1)이지만 공간은 O(V²)을 사용하므로 밀집 그래프에 가장 적합합니다.
- 인접 목록: 각 정점이 인접한 정점들의 리스트를 저장하는 리스트 배열입니다. 공간 복잡도는 O(V + E)이며 희소 그래프에 효율적이므로 대부분의 실제 그래프에서 사용됩니다.
이에 대한 자세한 내용은 다음에서 확인할 수 있습니다. 그래프의 인접 리스트 및 행렬 표현 튜토리얼.
그래프 데이터 구조의 응용
그래프는 다양한 용도로 사용됩니다. 그래프를 활용하는 알고리즘도 많습니다. 다음은 그래프의 몇 가지 응용 사례입니다.
- Google 지도 앱은 그래프를 사용하여 두 도로의 교차점을 찾고 두 위치 사이의 거리를 계산합니다. 예를 들어, Dijkstra출발지와 목적지 사이의 최단 거리를 찾기 위해서입니다.
- 페이스북은 그래프를 이용하여 사용자들의 공통 친구를 찾습니다. 페이스북의 알고리즘은 각 사용자를 그래프의 노드로 간주합니다.
- 자원 할당에는 DAG(방향 비순환 그래프)가 사용됩니다. DAG는 자원 간의 의존성을 확인합니다.
- The Google 검색 엔진은 그래프를 사용하여 웹사이트 순위를 매깁니다.
- 지도ping 이 장치는 그래프 데이터 구조를 사용합니다.
- A 라우터 그리고 해당 프로토콜은 그래프를 사용하여 목적지까지의 경로를 학습합니다.
