인접 목록을 사용하여 Java에 그래프를 저장하는 방법

1. 마무리

인접 목록은 그래프의 체인 저장 방법입니다. 해당 데이터 구조는 노드와 인접 점의 두 부분으로 구성됩니다.

인접 목록은 무방향 그래프, 유방향 그래프 및 네트워크를 나타내는 데 사용할 수 있습니다. 이는 무방향 그래프를 사용하여 설명됩니다.

1. 무방향 그래프

2. 무방향 그래프의 링크 테이블

3. 설명

노드 a의 인접 지점은 노드 b와 d이며, 인접 지점의 저장 인덱스는 1입니다. , 3. 헤드 삽입 방법(역순)에 따라 노드 a 뒤의 단일 연결 리스트에 넣습니다.

노드 b의 인접 포인트는 노드 a, c, d입니다. 인접 포인트의 저장 인덱스는 0, 2, 3입니다. 헤드 삽입 방법에 따라 노드 b 뒤의 단일 연결 리스트에 배치됩니다( 역순으로).

노드 c의 인접 지점은 노드 b와 d이고, 인접 지점의 저장 인덱스는 1과 3입니다. 헤드 보간 방법(역순)에 따라 노드 c 뒤의 단일 연결 리스트에 넣습니다.

노드 d의 인접 포인트는 노드 a, b, c입니다. 인접 포인트의 저장 인덱스는 0, 1, 2입니다. 이들은 헤드 삽입 방법에 따라 노드 d 뒤의 단일 연결 리스트에 배치됩니다( 역순으로).

4. 무방향 그래프의 인접 목록

의 특징은 다음과 같습니다. 무방향 그래프에 n개의 노드와 e개의 간선이 있으면 노드 테이블에는 n개의 노드가 있고 이웃 노드 테이블에는 2e개의 노드가 있습니다.

노드의 차수는 노드 뒤의 단일 연결 리스트에 있는 노드 수입니다.

2. 인접 리스트의 데이터 구조

1. 노드

에는 노드 정보 데이터와 첫 번째 인접 지점에 대한 포인터가 먼저 포함됩니다.

2. 인접 포인트

에는 인접 포인트의 저장 첨자 v와 다음 인접 포인트에 대한 포인터가 포함됩니다. 네트워크의 인접 포인트인 경우 가중치 도메인 w를 추가해야 합니다. 아래 그림과 같이 표시합니다.

3. 알고리즘 단계

1 노드와 모서리의 수를 입력합니다.

2 노드 정보를 차례로 입력하고 노드 배열 Vex[]의 데이터 필드에 저장하고 Vex[] 첫 번째 필드는 비워 둡니다.

3 각 Edge에 연결된 두 개의 노드를 차례로 입력합니다. 네트워크인 경우 Edge의 가중치도 입력해야 합니다.

무방향 그래프인 경우 a b를 입력하고 노드 a, b를 쿼리하고 노드 배열 Vex[]에 첨자 i, j를 저장하고 새로운 인접 점 s를 생성하고 s.v = j;s.next=null ; 그런 다음 i번째 노드의 첫 번째 인접 지점 앞에 노드 s를 삽입합니다(헤드 보간 방법). 무방향 그래프에는 노드 a에서 노드 b로의 간선이 있고 노드 b에서 노드 a로의 간선이 있으므로 새로운 인접 점 s2를 생성해야 합니다. s2.v = i;s2.next= null; 그리고 let s2 노드는 j번째 노드의 첫 번째 인접 지점 앞에 삽입됩니다(헤드 보간 방법).

무방향 그래프인 경우 a b를 입력하고 노드 a, b를 쿼리하고 노드 배열 Vex[]에 첨자 i, j를 저장하고 새로운 인접 점 s를 생성하고 s.v = j;s.next=null ; 그런 다음 i번째 노드의 첫 번째 인접 지점 앞에 노드 s를 삽입합니다(헤드 보간 방법).

무방향 네트워크이거나 방향성 네트워크인 경우 이웃 노드에 추가 가중치 도메인이 있다는 점을 제외하면 무방향성 그래프 또는 방향성 그래프와 동일한 방식으로 처리됩니다.

4. 구현

package graph;
 
import java.util.Scanner;
 
public class CreateALGraph {
    static final int MaxVnum = 100;  // 顶点数最大值
 
    public static void main(String[] args) {
        ALGraph G = new ALGraph();
        for (int i = 0; i < G.Vex.length; i++) {
            G.Vex[i] = new VexNode();
        }
        CreateALGraph(G); // 创建有向图邻接表
        printg(G); // 输出邻接表
    }
 
    static int locatevex(ALGraph G, char x) {
        for (int i = 0; i < G.vexnum; i++) // 查找顶点信息的下标
            if (x == G.Vex[i].data)
                return i;
        return -1; // 没找到
    }
 
    // 插入一条边
    static void insertedge(ALGraph G, int i, int j) {
        AdjNode s = new AdjNode();
        s.v = j;
        s.next = G.Vex[i].first;
        G.Vex[i].first = s;
    }
 
    // 输出邻接表
    static void printg(ALGraph G) {
        System.out.println("----------邻接表如下：----------");
 
        for (int i = 0; i < G.vexnum; i++) {
            AdjNode t = G.Vex[i].first;
            System.out.print(G.Vex[i].data + "：  ");
            while (t != null) {
                System.out.print("[" + t.v + "]\t");
                t = t.next;
            }
            System.out.println();
        }
    }
 
    // 创建有向图邻接表
    static void CreateALGraph(ALGraph G) {
        int i, j;
        char u, v;
 
        System.out.println("请输入顶点数和边数:");
        Scanner scanner = new Scanner(System.in);
        G.vexnum = scanner.nextInt();
        G.edgenum = scanner.nextInt();
        System.out.println("请输入顶点信息:");
 
        for (i = 0; i < G.vexnum; i++)//输入顶点信息，存入顶点信息数组
            G.Vex[i].data = scanner.next().charAt(0);
        for (i = 0; i < G.vexnum; i++)
            G.Vex[i].first = null;
        System.out.println("请依次输入每条边的两个顶点u,v");
 
        while (G.edgenum-- > 0) {
            u = scanner.next().charAt(0);
            v = scanner.next().charAt(0);
            i = locatevex(G, u); // 查找顶点 u 的存储下标
            j = locatevex(G, v); // 查找顶点 v 的存储下标
            if (i != -1 && j != -1)
                insertedge(G, i, j);
            else {
                System.out.println("输入顶点信息错！请重新输入！");
                G.edgenum++; // 本次输入不算
            }
        }
    }
}
 
// 定义邻接点类型
class AdjNode {
    int v; // 邻接点下标
    AdjNode next; // 指向下一个邻接点
}
 
// 定义顶点类型
class VexNode {
    char data; // VexType为顶点的数据类型，根据需要定义
    AdjNode first; // 指向第一个邻接点
}
 
// 定义邻接表类型
class ALGraph {
    VexNode Vex[] = new VexNode[CreateALGraph.MaxVnum];
    int vexnum; // 顶点数
    int edgenum; // 边数
}

5. 테스트

흰색이 출력, 녹색이 입력

위 내용은 인접 목록을 사용하여 Java에 그래프를 저장하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!