저장 구조
그래프를 저장하기 위해 그래프에 노드와 가장자리가 모두 있음을 알고 있습니다. 전원 그래프의 경우 각 모서리에도 가중치가 있습니다. 일반적으로 사용되는 그래프 스토리지 구조의 두 가지 주요 유형이 있습니다.
인접한 매트릭스 인접 테이블
인접한 매트릭스
우리는 노드를 나타내려면 1 차원 배열로 표시 할 수 있음을 알고 있습니다. 그러나 노드 간의 관계를 위해서는 단순히 1 차원 배열로 표시 할 수 없습니다. 우리는 그것들을 2 차원 배열, 즉 매트릭스 형성 표현 방법으로 표현할 수 있습니다.
우리는 A 가이 2 차원 배열이라고 가정하고, A의 요소 AIJ는 노드 VI와 노드 VJ의 관계를 반영 할뿐만 아니라 AIJ의 값도 중량의 크기를 나타낼 수 있다고 가정합니다.
다음은 방향되지 않은 그래프의 인접 매트릭스 표현의 예입니다.
위의 그림에서 우리는 방향되지 않은 그래프의 인접 행렬이 대칭 행렬이며 대칭 행렬이어야 함을 알 수 있습니다. 그리고 왼쪽 상단 모서리에서 오른쪽 하단 모서리까지 대각선의 값은 0입니다 (대각선은 동일한 노드를 나타냅니다).
지시 된 그래프의 인접 행렬은 무엇입니까?
가중 그래프의 경우 AIJ의 값을 사용하여 중량의 크기를 나타낼 수 있습니다. 위의 두 그래프는 무게가없는 그래프이므로 값은 모두 1입니다.
인접 테이블
그래프의 인접 매트릭스 저장 방법은 N*N 행렬을 사용한다는 것을 알고 있습니다. 이 매트릭스가 조밀 한 매트릭스 인 경우 (예 : 그래프가 완전한 그래프 일 때) 물론 인접성 행렬 저장 방법이 선택됩니다.
그러나이 매트릭스가 드문 매트릭스 인 경우 인접한 테이블 스토리지 구조는 더 공간 절약 저장 구조입니다.
위의 무향 그래프의 경우 인접 테이블을 사용하여 다음과 같이 표시 할 수 있습니다.
각 노드에 연결된 노드는 인접한 노드입니다.
인접 매트릭스와 인접성 테이블의 비교
그래프의 노드 수가 작고 많은면이 있으면 인접 행렬을 사용하는 효율이 더 높습니다.
노드의 수가 매우 크고 가장자리 수가 동일한 노드의 전체 그래프의 가장자리 수보다 훨씬 작은 경우 인접 테이블 스토리지 구조를 채택하는 것이 더 효율적입니다.
인접성 매트릭스의 Java 구현
인접한 매트릭스 모델 클래스
인접 행렬 모델 클래스의 클래스 이름은 amwgraph.java입니다. 이 클래스를 통해 인접 행렬로 표시되는 그래프를 구성하고 삽입 노드를 제공하고 가장자리를 삽입하며 특정 노드의 첫 번째 인접 노드 및 다음 인접 노드를 얻을 수 있습니다.
import java.util.arraylist; import java.util.linkedlist;/** * @description 인접한 매트릭스 모델 클래스 * @author beanlam * @time 2015.4.17 */public arraylist vertexlist; // stac 가장자리 public amwgraph (int n) {// 매트릭스 초기화, 1 차원 배열 및 가장자리 숫자 = new int [n] [n]; vertexlist = new arraylist (n); numofedges = 0; } // 노드 수를 가져옵니다. 공개 int getNumofVertex () {return vertexlist.size (); } // 가장자리 수를 가져옵니다. 공개 int getNumofedges () {return numofedges; } // 노드 I의 데이터를 반환합니다 I 공개 객체 getValueByIndex (int i) {return vertexlist.get (i); } // v1, v2 public int getweight (int v1, int v2) {return edges [v1] [v2]; } // 노드 삽입 공용 void insertVertex (Object vertex) {vertexlist.add (vertexlist.size (), vertex); } // 노드 삽입 공용 void inserged (int v1, int v2, int weight) {가장자리 [v1] [v2] = 무게; numofedges ++; } // 노드 삭제 public void deleteedge (int v1, int v2) {가장자리 [v1] [v2] = 0; numofedges--; } // 첫 번째 인접 노드 공개 int getfirstneighbor (int index)의 인덱스를 가져옵니다 (or (int j = 0; j <vertexlist.size (); j ++) {if (edges [index] [j]> 0) {return j; }} 반환 -1; } // 이전 인접 노드 공개 int getnextneighbor (int v1, int v2) {for (int j = v2+1; }} 반환 -1; }}인접 매트릭스 모델 클래스 테스트
다음으로 다음 지시 된 그래프를 기반으로 테스트 모델 클래스를 설정하십시오.
estamwgraph.java 테스트 프로그램은 다음과 같습니다.
/** * amwgraph 클래스의 @description test 클래스 * @author beanlam * @time 2015.4.17 */public class adcamwgraph {public static void main (string args []) {int n = 4, e = 4; //는 각각 노드의 수와 가장자리의 수를 나타냅니다. 식별 amwgraph 그래프 = 새로운 amwgraph (n); for (문자열 레이블 : labels) {graph.insertvertex (label); // 삽입 노드} // 4 개의 모서리 삽입 그래프 .insertedge (0, 1, 2); graph.insertedge (0, 2, 5); graph.insertedge (2, 3, 8); graph.insertedge (3, 0, 7); System.out.println ( "노드 수는"+Graph.getNumofVertex ()); System.out.println ( "가장자리 수는"+Graph.getNumofedges ()); graph.deleteedge (0, 1); // <v1, v2> edge system.out.println ( "삭제 후 <v1, v2> edge ..."); System.out.println ( "노드 수는"+Graph.getNumofVertex ()); System.out.println ( "가장자리 수는"+Graph.getNumofedges ()); }}콘솔의 출력 결과는 다음 그림에 나와 있습니다.
요약
위는 저장 구조 및 인접 행렬 코드 예제에 대한 Java 언어 설명에 대한이 기사의 모든 내용입니다. 모든 사람에게 도움이되기를 바랍니다. 관심있는 친구는이 사이트의 다른 관련 주제를 계속 참조 할 수 있습니다. 단점이 있으면 메시지를 남겨 두십시오.