아크 세트를 인접 행렬 및 인접 테이블로 표현하는 방법은 무엇입니까?

그림 표현 : 인접 매트릭스 및 인접 테이블 변환에 대한 아크

이 기사는 지시 된 아크 세트를 인접 행렬 및 인접 테이블의 두 가지 일반적인 표현으로 변환하는 방법을 보여줍니다. 예를 들어 다음 아크 세트를 사용합니다 : ⟨v0, v1, v1, v1, v1, v3, v2, v3. 이 아크 세트는 4 개의 정점 (v0, v1, v2, v3)이있는 방향 그래프를 설명합니다.

먼저, 이러한 아크를 해석합시다. V1의 정점에자가 루프로 표시되는 ⟨V1, V1; v1에서 v3로 가리키는 방향 에지로 표시되는 ⟨V1, V3; v2에서 v3을 가리키는 지시 된 가장자리로 표시되는 ⟨v2, v3.

인접한 매트릭스 표현 :

인접 행렬은 2 차원 배열을 사용하여 그래프를 나타냅니다. 배열의 행과 열은 각각 그래프의 정점에 해당합니다. 정점 I에서 vertex j로 가장자리가있는 경우, 매트릭스 요소 A _IJ 는 1입니다. 그렇지 않으면 가중 그래프의 경우 _IJ는 가장자리의 무게를 저장할 수 있습니다.

주어진 아크 세트를 기반으로 4x4 인접 매트릭스를 만들 수 있습니다.

<code> v0 v1 v2 v3 v0 0 1 0 0 v1 0 1 0 1 v2 0 0 0 1 v3 0 0 0 0</code>

인접 테이블 표현 :

인접한 테이블은 특히 희소 그래프의 경우 더 우주 절약 그래프 표현 방법입니다. 배열의 각 요소가 정점에 해당하는 배열을 사용하고 해당 정점에 인접한 정점을 저장하는 링크 된 목록을 가리 킵니다.

주어진 아크 세트에 따라 해당 인접 테이블은 다음과 같습니다.

 <code>v0: v1 v1: v1, v3 v2: v3 v3:</code>

이것은 V0이 V1에 연결되어 있음을 의미합니다. V1은 자체 (자체 루프) 및 v3에 연결되어 있습니다. V2는 v3에 연결되어 있습니다. V3에는 오래된 가장자리가 없습니다.

요약 :이 기사에서는 아크 세트를 인접 행렬 및 인접 테이블로 변환하는 방법을 보여줍니다. 이 두 가지 표현 방법에는 고유 한 장점과 단점이 있습니다. 선택된 메소드는 특정 응용 프로그램 시나리오와 그래프의 특성 (예 : 그래프의 희소성)에 따라 다릅니다.

위 내용은 아크 세트를 인접 행렬 및 인접 테이블로 표현하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!