우리는 노드를 나타내려면 1 차원 배열로 표시 할 수 있음을 알고 있습니다. 그러나 노드 간의 관계를 위해서는 단순히 1 차원 배열로 표시 할 수 없습니다. 우리는 그것들을 2 차원 배열, 즉 매트릭스 형성 표현 방법으로 표현할 수 있습니다.
우리는 A 가이 2 차원 배열이라고 가정하고, A의 요소 AIJ는 노드 VI와 노드 VJ의 관계를 반영 할뿐만 아니라 AIJ의 값도 중량의 크기를 나타낼 수 있다고 가정합니다.
인접한 매트릭스 모델 클래스
인접 행렬 모델 클래스의 클래스 이름은 amwgraph.java입니다. 이 클래스를 통해 인접 행렬로 표시되는 그래프를 구성하고 삽입 노드를 제공하고 가장자리를 삽입하며 특정 노드의 첫 번째 인접 노드 및 다음 인접 노드를 얻을 수 있습니다.
java.util.arraylist 가져 오기;
java.util.linkedList 가져 오기;
공개 클래스 amwgraph {
개인 배열리스트 vertexlist;
// 스토리지 포인트의 링크 테이블
개인 int [] [] 가장자리;
// 가장자리를 저장하는 데 사용되는 주소 매트릭스
개인 int numofedges;
// 가장자리 수
공개 amwgraph (int n) {
// 행렬, 1 차원 배열 및 가장자리 수 초기화
가장자리 = 새로운 int [n] [n];
vertexlist = new arraylist (n);
numofedges = 0;
}
// 노드 수를 얻습니다
public int getNumofverTex () {
vertexlist.size ()를 반환합니다.
}
// 가장자리 수를 얻습니다
공개 int getNumofedges () {
Numofedges를 반환하십시오.
}
// 노드의 데이터를 반환 i
공개 대상 getValueByIndex (int I) {
반환 vertexlist.get (i);
}
// v1과 v2의 무게를 반환합니다
공개 int getweight (int v1, int v2) {
리턴 가장자리 [v1] [v2];
}
// 노드 삽입
public void insertVertex (Object Vertex) {
vertexlist.add (vertexlist.size (), vertex);
}
// 노드 삽입
public void insertedge (int v1, int v2, int weight) {
가장자리 [v1] [v2] = 무게;
numofedges ++;
}
// 노드를 삭제합니다
공개 void deleteedge (int v1, int v2) {
가장자리 [v1] [v2] = 0;
numofedges--;
}
// 첫 번째 인접 노드의 첨자를 가져옵니다
공개 int getfirstneighbor (int index) {
for (int j = 0; j <vertexlist.size (); j ++) {
if (가장자리 [index] [j]> 0) {
j;
}
}
반품 -1;
}
// 이전 인접 노드의 첨자를 기반으로 다음 인접 노드를 가져옵니다.
공개 int getnextneighbor (int v1, int v2) {
for (int j = v2+1; j <vertexlist.size (); j ++) {
if (가장자리 [v1] [j]> 0) {
j;
}
}
반품 -1;
}
}인접성 매트릭스를 구현하는 코드를 살펴 보겠습니다.
패키지 com.datrastructure.graph;
///// 고밀도 그래프 - 인접 행렬을 사용하여 표현합니다
// public class Densegraph {
//
// private int n; // 노드 수
// private int m; // 엣지 번호
// 개인 부울 감독; // 지시 된 그래프입니까?
// 개인 부울 [] [] g; // 그림의 특정 데이터
//
// // 생성자
// public densegraph (int n, 부울 지시) {
// assert n> = 0;
// this.n = n;
// this.m = 0; // 초기화에는 가장자리가 없습니다
// this.directed = 지시;
// g는 n*n의 부울 매트릭스로 초기화됩니다. 각 g [i] [j]는 거짓이며 가장자리가 없음을 나타냅니다.
// // false는 부울 유형 변수의 기본값입니다.
// g = 새로운 부울 [n] [n];
//}
//
// public int v () {
// return n;
//} // 노드 수를 반환합니다
//
// public int e () {
// 반환 m;
//} // 가장자리 수를 반환합니다
//
// // 그래프에 에지를 추가합니다
// public void addedge (int v, int w) {
//
// assert v> = 0 && v <n;
// assert w> = 0 && w <n;
//
// if (hasedge (v, w))
// 반품;
//
// // Connect v 및 w
// g [v] [w] = true;
// if (! 감독)
// g [w] [v] = true;
//
// // 가장자리 수 ++
// m ++;
//}
//
// // 그래프에 v에서 w로 가장자리가 있는지 확인
// 부울 hasedge (int v, int w) {
// assert v> = 0 && v <n;
// assert w> = 0 && w <n;
// g [v] [w]를 반환합니다.
//}
//
// // 그래프에서 정점의 모든 이웃을 반환합니다.
// // Java는 참조 메커니즘을 사용하므로 벡터를 반환하면 추가 오버 헤드가 없습니다.
// public iterable <integer> adj (int v) {
// assert v> = 0 && v <n;
// vector <integer> adjv = new 벡터 <integer> ();
// for (int i = 0; i <n; i ++)
// if (g [v] [i])
// adjv.add (i);
// retud adv;
//}
//}
java.util.arraylist 가져 오기;
Java.util.list 가져 오기;
// 인접 행렬을 사용하여 조밀 한 그래프를 나타냅니다
공개 클래스 밀도 그래프 {
개인 int n;
// 그림의 노드 수
개인 INT M;
// 그림의 가장자리 수
개인 부울 [] [] g;
// 인접 행렬 g
개인 부울 감독;
// 지시 된 그래프입니까?
Public DenseGraph (Int N, 부울 지시) {
this.n = n;
// 초기화 그래프의 노드 수입니다
this.m = 0;
// 그림의 가장자리 수는 0으로 초기화됩니다.
this.directed = 지시;
g = 새로운 부울 [n] [n];
// 인접 행렬 g는 n*n의 2 차원 행렬로 초기화됩니다.
// 색인은 그래프의 노드를 나타내고 G에 저장된 값은 노드에 가장자리가 있는지 여부입니다.
}
// 그래프에서 가장자리 수를 반환합니다
public int e () {
반환 m;
}
// 그래프에서 노드 수를 반환합니다
public int v () {
리턴 n;
}
// 그림에 지정된 두 노드 사이에 가장자리 추가
공개 void addedge (int v, int w) {
if (! hasedge (v, w)) {
// 연결 [v] [w]
g [v] [w] = true;
// 방향이없는 그래프
if (! 감독)
g [w] [v] = true;
// 그림의 측면 수 +1
m ++;
}
}
// 두 노드 사이에 가장자리가 있는지 확인
개인 부울 hasedge (int v, int w) {
g [v] [w]를 반환합니다.
}
// 모든 노드의 인접 노드를 반환 v
public iterable <integer> awnacentNode (int v) {
// awnacentl은 v의 인접한 노드를 저장하는 데 사용됩니다.
List <integer> awnacentl = new ArrayList <> ();
// v에 인접한 모든 노드를 찾아 인접한에 추가하십시오.
for (int i = 0; i <n; i ++) {
if (g [v] [i])
Adjacentl.add (i);
}
인접한 반환;
}
}
요약
위의 내용은 Java 프로그래밍에 대한이 기사의 모든 내용으로 인접 매트릭스의 밀도가 높은 그래프 표현의 코드 예제를 구현하기 위해 모든 사람에게 도움이되기를 바랍니다. 관심있는 친구들은이 사이트를 계속 참조 할 수 있습니다.
Java 데이터 구조 트리의 기본 개념 및 코드 예제 분석
Java 일반 데이터 구조 인터뷰 질문 (답변 포함)
멀티 모드 문자열 일치 알고리즘 원리 및 Java 구현 코드
단점이 있으면 메시지를 남겨 두십시오. 이 사이트를 지원해 주신 친구들에게 감사드립니다!