So verwenden Sie eine Adjazenzliste zum Speichern von Diagrammen in Java

1. Der letzte Schliff

Die Adjazenzliste ist eine verknüpfte Speichermethode für Diagramme. Ihre Datenstruktur besteht aus zwei Teilen: Knoten und Adjazenzpunkten.

Adjazenzlisten können zur Darstellung ungerichteter Graphen, gerichteter Graphen und Netzwerke verwendet werden. Dies wird anhand eines ungerichteten Graphen erklärt.

1. Ungerichteter Graph

2. Linktabelle des ungerichteten Graphen

# 🎜🎜 #

3. Beschreibung

Die benachbarten Punkte von Knoten a sind die Knoten b und d, und die Speicherindizes ihrer benachbarten Punkte sind 1 und 3. Gemäß der Kopfinterpolation Methode (umgekehrte Reihenfolge) und fügen Sie sie in die einfach verknüpfte Liste hinter Knoten a ein.

Die benachbarten Punkte von Knoten b sind die Knoten a, c und d. Die Speicherindizes seiner benachbarten Punkte sind 0, 2 und 3. Gemäß der Kopfinterpolationsmethode (umgekehrte Reihenfolge). sie hinter Knoten b in einer einfach verknüpften Liste.

Die benachbarten Punkte von Knoten c sind die Knoten b und d, und die Speicherindizes ihrer benachbarten Punkte sind 1 und 3. Sie werden gemäß der Kopfeinfügungsmethode in die einfach verknüpfte Liste hinter Knoten c eingefügt (umgekehrte Reihenfolge).

Die benachbarten Punkte des Knotens d sind die Knoten a, b, c. Die Speicherindizes seiner benachbarten Punkte sind 0, 1, 2. Setzen Sie sie gemäß der Kopfinterpolationsmethode (umgekehrte Reihenfolge) zurück Knoten d in einer einfach verknüpften Liste.

4. Ungerichteter Graph

Die Eigenschaften der Adjazenzliste sind wie folgt: Wenn es n Knoten und e Kanten im ungerichteten Graphen gibt, dann gibt es n Knoten im Knotentabelle und die Adjazenzliste. Die Knotentabelle enthält 2e Knoten.

Der Grad eines Knotens ist die Anzahl der Knoten in der einfach verknüpften Liste hinter dem Knoten.

2. Datenstruktur der Adjazenzliste

1. Knoten

enthält zuerst Knoteninformationsdaten und einen Zeiger auf den ersten benachbarten Punkt.

2. Benachbarter Punkt

enthält den Speicherindex v des benachbarten Punkts und den Zeiger auf den nächsten benachbarten Punkt Wenn es sich um einen benachbarten Punkt im Netzwerk handelt, muss eine Gewichtsdomäne w hinzugefügt werden, wie in der folgenden Abbildung dargestellt.

3. Algorithmusschritte

1 Geben Sie die Anzahl der Knoten und die Anzahl der Kanten ein.

2 Geben Sie der Reihe nach die Knoteninformationen ein, speichern Sie sie im Datenfeld des Knotenarrays Vex[] und lassen Sie das erste Feld Vex[] leer.

3 Geben Sie nacheinander die beiden Knoten ein, die an jeder Kante angebracht sind. Wenn es sich um ein Netzwerk handelt, müssen Sie auch das Gewicht der Kante eingeben.

Wenn es sich um einen ungerichteten Graphen handelt, geben Sie ein b ein, fragen Sie die Knoten a, b ab, speichern Sie die Indizes i, j im Knotenarray Vex[], erstellen Sie einen neuen benachbarten Punkt s, sei s.v = j ;s .next=null;Fügen Sie dann Knoten s vor dem ersten benachbarten Punkt des i-ten Knotens ein (Kopfinterpolationsmethode). In einem ungerichteten Diagramm gibt es eine Kante von Knoten a zu Knoten b und eine Kante von Knoten b zu Knoten a. Daher muss ein neuer Adjazenzpunkt s2 erstellt werden. Sei s2.v = i;s2.next= null; und dann let Der s2-Knoten wird vor dem ersten benachbarten Punkt des j-ten Knotens eingefügt (Kopfinterpolationsmethode).

Wenn es sich um einen ungerichteten Graphen handelt, geben Sie ein b ein, fragen Sie die Knoten a, b ab, speichern Sie die Indizes i, j im Knotenarray Vex[], erstellen Sie einen neuen benachbarten Punkt s, sei s.v = j ;s .next=null;Fügen Sie dann Knoten s vor dem ersten benachbarten Punkt des i-ten Knotens ein (Kopfinterpolationsmethode).

Wenn es sich um ein ungerichtetes Netzwerk oder ein gerichtetes Netzwerk handelt, wird es auf die gleiche Weise verarbeitet wie ein ungerichteter Graph oder ein gerichteter Graph, mit der Ausnahme, dass die benachbarten Knoten eine weitere Gewichtsdomäne haben.

4. Implementierung

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.Test

Weiß ist Ausgabe, Grün ist Eingabe

#

Das obige ist der detaillierte Inhalt vonSo verwenden Sie eine Adjazenzliste zum Speichern von Diagrammen in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!