인접한 테이블의 방향되지 않은 그래프 소개
인접 테이블의 방향이없는 그래프는 인접 테이블로 표시되는 방향이없는 그래프를 나타냅니다.
위의 그림 G1에는 "a, b, c, d, e, e, g"의 7 개의 정점이 포함되어 있으며 "(a, c), (a, d), (a, f), (b, c), (c, d), (e, g), (f, g)"의 7 개의 가장자리를 포함합니다.
위 그림의 오른쪽에있는 매트릭스는 의도를 나타내는 메모리에서 G1의 인접성입니다. 각 정점에는 "정점의 인접한 지점의 시퀀스 번호"를 기록하는 링크 된 목록이 포함되어 있습니다. 예를 들어, 두 번째 정점 (정점 C)에 포함 된 링크 된 목록에 포함 된 노드의 데이터는 각각 "0, 1, 3"이며; 이 "0, 1, 3"은 "A, B, D"및 "A, B, D"의 서열 번호에 해당합니다. 이는 모두 인접한 지점입니다. 이것은 그림의 정보를 기록하는 방법입니다.
인접성 테이블의 방향되지 않은 그래프의 코드 설명
1. 기본 정의
public class ListUDG {// The vertex that adjaces the table corresponding to the linked list private class ENode {int ivex;// The position of the vertex that the edge points to ENode nextEdge;// Pointer to the next arc}// The vertex that adjaces the table in the table private class VNode {char data;// Vertex information ENode firstEdge;// Pointer to the first arc that attaches to the Vertex}; private vnode [] mvexs; // vertex array ...}(01) ListUdg는 인접 테이블에 해당하는 구조입니다. MVEXS는 정점 정보를 저장하는 1 차원 배열입니다.
(02) vnode는 인접 테이블의 정점에 해당하는 구조입니다. 데이터는 정점에 포함 된 데이터이며, FirstEdge는 정점에 포함 된 링크 된 목록의 헤더 포인터입니다.
(03) Enode는 테이블의 정점에 포함 된 링크 된 목록에 인접한 노드에 해당하는 구조입니다. IVEX는 VEX 에서이 노드에 해당하는 정점의 인덱스이고 Nextedge는 다음 노드를 가리 킵니다.
2. 행렬을 만듭니다
매트릭스를 생성하는 두 가지 방법이 있습니다. 하나는 알려진 데이터를 사용하고 다른 하나는 사용자가 수동으로 데이터를 입력해야합니다.
2.1 그래프 작성 (제공된 행렬 사용)
/ * * 그래프 생성 (제공된 행렬 사용) * * 매개 변수 설명 : * vexs -vertex array * edges -edge array */public listudg (char [] vexs, char [] [] edges) {// "vertex"및 "edge"int vlen = vexs.length; int elen = edges.length; // mexs = new " vnode [vlen]; for (int i = 0; i <mvexs.length; i ++) {mvexs [i] = new vnode (); mvexs [i] .data = vexs [i]; mvexs [i] .firstedge = null;} // "edges"를 초기화합니다. Edge C1 = Edges [i] [0]; char c2 = 가장자리 [i] [1]; // 가장자리의 시작 정점 및 끝 부분을 읽습니다 int p1 = getposition (edges [i] [0]); int p2 = getposition (edges [i] [1]); // new ernode (); node 1.// indode (); node1에서 "p1이있는 링크 된 목록의 끝"if (mvexs [p1] .firstedge == null) mvexs [p1] .firstedge = node1; else linklast (mvexs [p1] .firstedge, node1); // node2enode node2 = new enode (); node2.ivex = p1; // 링크 node2 "p2]가있는 링크 된 목록의 끝". else linklast (mvexs [p2] .firstedge, node2);}}이 기능은 인접 테이블의 방향이없는 그래프를 작성하는 것입니다. 실제로,이 방법에 의해 생성 된 방향 그래프는 위의 그림 G1입니다. 통화 코드는 다음과 같습니다.
char [] vexs = { 'a', 'b', 'c', 'd', 'e', 'f', 'g'}; char [] edges = new char [] [] { 'a', 'c'}, { 'a', 'd'}, { 'a', 'f'}, { 'b', 'c'}, { 'e', 'g'}, { 'f', 'g'}}; listudg pg; pg = new ListUdg (vexs, 가장자리);2.2 그래프 만들기 (직접 입력)
/ * * 그래프 생성 */public listudg () {// "버전 번호"및 "Edge Number"System.out.printf를 입력하십시오. 1)))))))))))))))))))))))))))) vnode (); mvexs [i] .data = readchar (); mvexs [i] .firstedge = null;} // "Edge"// mmatrix = new int [vlen] [vlen]; for (int i = 0; i <elen; i ++) {// gate system의 시작 및 끝 vertex. i); char c1 = readchar (); char c2 = readchar (); int p1 = getposition (c1); int p2 = getPosition (c2); // node1enode node1 = new enode (); node1.ivex = p2; // int mvexs [p1] .firstedge = node1; else linklast (mvexs [p1] .firstedge, node1); // node2enode node2 = new enode (); node2.ivex = p1; // 링크 node2 "p2]가있는 링크 된 목록의 끝". else linklast (mvexs [p2] .firstedge, node2);}}이 함수는 사용자의 입력을 읽고 입력 데이터를 해당 무의미한 그래프로 변환합니다.
인접 테이블의 방향이없는 그래프의 전체 소스 코드
import java.io.ioexception; import java.util.scanner; public class listudg {// 링크 된 목록에 인접한 정점은 테이블 개인 클래스 enode {int iivex; // 엣지가 enode nextedge; // pointer to the table to the the the the the the the the the the the the the the the the the the the the the table to the the the table to the the table을 가리키는 정점의 위치에있는 링크 된 목록에 vnode {char data; // vertex Information enode firstedge; // vertex}에 첨부 된 첫 번째 아크에 대한 포인터; private vnode [] mvexs [] mvexs; // vertex array/ * * 그래프 생성 (직접 입력 데이터) */public listudg () {// "vertex numb = readInt (); system.out.printf ( "입력 에지 번호 :"); int elen = readint (); if (vlen <1 || elen <1 || (elen> (vlen*(vlen*(vlen -1)))) {system.out.out.printf ( "입력 오류 : Invalid arameters!/n"); reture "). vnode [vlen]; for (int i = 0; i <mvexs.length; i ++) {system.out.printf ( "vertex (%d) :", i); mvexs [i] = new vnode (); mvexs [i] .data = readchar (); mvexs [i] .firstedge = null; int [vlen] [vlen]; for (int i = 0; i <elen; i ++) {// 엣지 시스템의 시작 및 종료 정점을 읽습니다. enode (); node1.ivex = p2; // node1을 "p1이있는 링크 된 목록의 끝"if (mvexs [p1] .firstedge == null) mvexs [p1] .firstedge = node1; else linklast (mvexs [p1] .firstedge, node1); // node2enode node2 = new enode (); node2.ivex = p1; // 링크 node2 "p2]가있는 링크 된 목록의 끝". else linklast (mvexs [p2] .firstedge, node2);}}/ * * 그래프 생성 그래프 생성 (제공된 행렬 사용) * * 매개 변수 설명 : * vexs -vertex array * edges -edge array */public listudg (char [] vexs, char [] [] edges) {// vertex number "int vlen; = edges.length; // "vertex"mvexs = new vnode [vlen]; for (int i = 0; i <mvexs.length; i ++) {mvexs [i] = new vnode (); mvexs [i] .data = vexs [i]; mvexs [i] .firstedgegegeg = null; 0; i <elen; i ++) {// 가장자리의 시작 정점을 읽습니다. char c1 [i] [0]; char c2 = 가장자리 [i] [1]; node1 = new enode (); node1.ivex = p2; // node1을 "p1에있는 링크 된 목록의 끝"if (mvexs [p1] .firstedge == null) mvexs [p1] .firstedge = node1; else linklast (mvexs [p1] .firstedge, node1); // node2enode node2 = new enode (); node2.ivex = p1; // 링크 node2 "p2]가있는 링크 된 목록의 끝". else linklast (mvexs [p2] .firstedge, node2);}}/** 노드 노드를 목록의 마지막으로 연결*/private void linklast (enode list, enode node) {enode p = list; {for (int i = 0; i <mvexs.length; i ++) if (mvexs [i] .data == ch) return i; return -1;}/** 입력 문자*/private char readchar () {char ch = '0'; do {ch = (char) system.in.read () catch (ioexctort e). {e.printstacktrace ();}} while (! 그래프*/public void print () {system.out.printf ( "list graph :/n"); for (int i = 0; i <mvexs.length; i ++) {system.out.printf ( "%d (%c) :", i, mvexs [i] .data); enode node = mvexs [i] .firstedgegege; while (node! = null) {System.out.printf ( "%d (%c)", node.ivex, mvexs [node.ivex] .data); node = node.nextedge;} system.out.printf ( "/n");}} public static void main (string [] args) {] vex = ',', ',', ',', ',', ',', 'a', ', 'd', 'e', 'f', 'g'}; char [] [] [] edges = new char [] [] { 'a', 'c'}, { 'a', 'd'}, { 'a', 'f'}, { 'b', 'c'}, { 'c', 'd'}, { 'e', 'g'}, 'g'}}; listudg pg; // custom "그래프"(입력 행렬 큐 "// pg = new listudg (); // 기존"그래프 "pg = new listudg (vexs, 가장자리); pg.print (); // print diagram}} 사용요약
위는 인접 테이블의 Java 언어의 전체 소스 코드를 구현하는 것에 대한이 기사의 모든 내용입니다. 모든 사람에게 도움이되기를 바랍니다. 관심있는 친구들은이 사이트를 계속 참조 할 수 있습니다.
Java 계산 수학 표현 코드에 대한 자세한 설명
Java의 가변 길이 매개 변수 코드에 대한 자세한 설명
완벽한 숫자 코드 분석을위한 Java 언어 솔루션
단점이 있으면 메시지를 남겨 두십시오. 이 사이트를 지원해 주신 친구들에게 감사드립니다!