여기에서 그래프 데이터 구조의 요지를 알아보세요...

이 블로그는 개념의 요점을 파악하고 엉뚱한 생각을 하지 않으려는 개발자를 위한 것입니다. 이번 포스팅에서는 그래프 데이터 구조에 대해 알아보겠습니다. 시작합시다.

그래프란 무엇입니까?

그래프는 모서리와 노드라는 두 가지 구성요소로 구성된 비선형 데이터 구조입니다.

노드: -

1. 그래프의 기본 단위
2. 정점 또는 꼭짓점이라고도 하며
3. 레이블을 지정하거나 지정하지 않을 수 있습니다.

가장자리는:-

1. 두 노드 간의 연결
2. 호라고도 알려져 있으며
3. 레이블을 지정하거나 지정하지 않을 수 있습니다.

그래프 유형: -

1. 널 그래프: 모서리가 없습니다.
2. 삼각 그래프: 노드가 하나만 있습니다.
3. 순환 그래프: 적어도 하나의 사이클을 포함합니다.
4. 사이클 그래프: 모든 노드가 연결되어 하나의 사이클을 이루고,
5. 유향 그래프: 모서리에 방향이 있습니다.
6. 무방향 그래프: 모서리에 방향이 없습니다.
7. 가중치 그래프: 각 모서리에 일부 값이 할당됩니다.
8. 연결된 그래프: 한 노드에서 다른 노드를 방문할 수 있습니다(고유한 가장자리일 필요는 없음).
9. 연결되지 않은 그래프: 하나 이상의 노드가 하나의 노드에서 연결이 끊어졌습니다.
10. 정규 그래프: 모든 정점은 동일한 수의 이웃을 가집니다.
11. 완전한 그래프: 모든 노드는 고유한 에지로 다른 노드와 연결됩니다.
12. 유향 비순환 그래프: 순환이 없는 유향 그래프
13. 이분 그래프: 노드는 세트 사이에 간선이 존재하지 않도록 2개의 세트로 나눌 수 있습니다.

그래프를 어떻게 저장하나요?

두 가지 방법이 있습니다.

1. 인접 행렬 및
2. 인접 행렬

인접 행렬은 그래프 데이터 구조를 나타내는 2차원 행렬입니다. 행과 열은 노드를 나타내고 행렬의 값은 가장자리를 나타냅니다.

위 이미지에서는 4개의 노드가 모서리로 연결되어 있습니다. 노드 A는 모든 노드에 연결되어 있으므로 A(행 또는 열)가 다른 노드의 행 또는 열과 교차하는 셀에는 값이 1로 추가됩니다. 노드 B는 노드 A에만 연결되어 노드 B가 노드 A와 교차하는 셀에서는 값이 1이 되고 다른 셀은 값이 0이 됩니다.

인접 행렬에 대한 간선을 추가하거나 삭제하는 시간 복잡도는 O(1)입니다. 다음과 같은 경우에 사용할 수 있습니다: -

1. 그래프에 가능한 최대 모서리가 있습니다.
2. 메모리 제약이 없으며
3. 그래프의 구조가 복잡합니다.

인접 목록은 여러 연결된 목록이나 배열을 사용하여 그래프를 저장합니다. 행은 노드를 나타내고(아래 이미지 확인) 행에 있는 값은 이웃을 나타냅니다.

위 이미지에는 5개의 노드가 있습니다. 노드 A는 노드 B와 노드 D에 연결되어 있으므로 첫 번째 배열에 해당 값이 있습니다. 마찬가지로 노드 B는 노드 A, 노드 C, 노드 D 및 노드 E에 연결되므로 두 번째 어레이는 두 번째 어레이에 해당 노드를 갖습니다.

간선을 검색하거나 삭제하는 데 드는 시간 복잡도는 O(n)이고 간선을 추가하는 데 걸리는 시간 복잡도는 O(1)입니다. 인접 목록은 다음과 같은 경우에 사용할 수 있습니다: -

1. 노드의 에지가 더 적습니다.
2. 메모리 제약이 있고
3. 그래프가 덜 복잡해졌습니다.

그림: 인접 목록과 인접 행렬 간의 시각적 비교.

그래프 사용 사례

그래프 데이터 구조의 인기 있는 예 중 하나는 다음과 같습니다. 축구 분야에서 각 선수는 노드로 간주될 수 있으며 이들의 상호 작용은 가장자리를 나타냅니다.

그래프는 다음과 같이 이전 예와 유사한 시나리오에서 사용됩니다. -

1. 모두가 노드인 소셜 네트워크에서
2. PC와 라우터가 노드인 컴퓨터 네트워크에서
3. 교통망 등...

위 내용은 여기에서 그래프 데이터 구조의 요지를 알아보세요...의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!