그래프 데이터 구조 및 Algorithms (예)

데이터 구조의 그래프란 무엇입니까?

그래프는 꼭짓점과 간선으로 구성된 비선형 데이터 구조로, 꼭짓점에는 정보나 데이터가 포함되고 간선은 한 쌍의 꼭짓점 사이를 연결하는 역할을 합니다.

목적지까지의 최적 경로 찾기, 통신 및 소셜 네트워크 경로 찾기와 같은 실제 단어 문제를 해결하는 데 사용됩니다. 사용자는 그래프에서 노드로 간주되며 와이어는 사용자를 연결하는 가장자리입니다.

모서리가 E로 표시되고 꼭지점은 V로 표시되면 그래프 G는 다음과 같이 꼭지점과 모서리의 집합으로 작성될 수 있습니다. G (V, E)

다음은 그래프 데이터 구조의 간단한 예입니다.

단순한 무방향 그래프(그래프의 한 종류)입니다. 여기서 정점 세트는 {A, B, C,D,E,F}입니다. 두 개의 정점이 가장자리를 만듭니다. 예를 들어 A와 B는 모서리로 연결되어 있습니다. 그러나 A와 F는 어떤 모서리와도 연결되어 있지 않습니다.

그래프 데이터 구조에서 사용되는 몇 가지 중요한 용어는 다음과 같습니다.

기간	기술설명
Vertex	모든 데이터 요소를 정점 또는 노드라고 합니다. 위 이미지에서 A, B, C, D, E는 정점입니다.
모서리(호)	두 노드나 정점 사이를 연결하는 링크를 모서리(Arc)라고 합니다. 두 개의 끝이 있으며 (startingVertex, endVertex)로 표시됩니다.
방향이 지정되지 않은 가장자리	양방향 엣지입니다.
방향성 가장자리	단방향 모서리입니다.
가중치 가장자리	가치가 있는 엣지.
도	그래프에서는 정점에 연결된 모서리의 수를 차수라고 합니다.
인도	정점에 연결된 들어오는 가장자리의 총 수입니다.
외도	정점에 연결된 나가는 가장자리의 총 개수입니다.
자가 루프	두 끝점이 일치하는 모서리를 자체 루프라고 합니다.
인접	모서리가 연결되어 있으면 정점이 인접해 있다고 합니다.

다음은 가장 일반적인 목록입니다. 데이터 구조의 그래프 유형:

그래프에는 많은 사용 사례가 있습니다. 그래프를 많이 사용하는 알고리즘이 많이 있습니다. 그래프의 몇 가지 응용 프로그램은 다음과 같습니다.

Google 지도는 그래프를 사용하여 두 도로의 교차점을 찾고 두 위치 사이의 거리를 계산합니다.
예를 들어, Dijkstra, 소스와 대상 위치 사이의 최단 거리를 찾는 데 사용됩니다.
Facebook은 그래프를 사용하여 사용자의 상호 친구를 찾습니다. 해당 알고리즘은 각 사용자를 그래프의 노드로 간주합니다.
자원 할당에는 DAG(Direct Acylic Graph)가 사용됩니다. 리소스의 종속성을 확인합니다.
Google 검색 엔진은 그래프를 사용하여 웹사이트 순위를 생성합니다.
매핑 장치는 그래프 데이터 구조를 사용합니다.
라우터 t의 프로토콜은 그래프를 사용하여 대상 경로의 경로를 학습합니다.