Cara menggunakan senarai bersebelahan untuk menyimpan graf di Jawa

1. Sentuhan penamat

Senarai bersebelahan ialah kaedah penyimpanan berantai untuk graf struktur datanya terdiri daripada dua bahagian: nod dan titik bersebelahan.

Senarai bersebelahan boleh digunakan untuk mewakili graf tidak terarah, graf terarah dan rangkaian. Ini dijelaskan menggunakan graf tidak berarah.

1. Graf tidak berarah

2 Jadual terpaut graf tidak berarah

3 .Penjelasan

Titik bersebelahan nod a ialah nod b dan d, dan indeks storan bagi titik bersebelahannya ialah 1 dan 3. Letakkannya ke dalam senarai berpaut tunggal di belakang nod a mengikut kaedah sisipan kepala (urutan terbalik ).

Titik bersebelahan nod b ialah nod a, c, dan d Indeks storan bagi titik bersebelahannya ialah 0, 2, dan 3. Letakkannya ke dalam senarai terpaut tunggal di belakang nod b mengikut kepala. kaedah sisipan (tertib terbalik).

Titik bersebelahan nod c ialah nod b dan d, dan indeks storan bagi titik bersebelahannya ialah 1 dan 3. Ia dimasukkan ke dalam senarai berpaut tunggal di belakang nod c mengikut kaedah interpolasi kepala (terbalik pesanan).

Titik bersebelahan nod d ialah nod a, b, c Subskrip storan titik bersebelahannya ialah 0, 1, 2. Mengikut kaedah interpolasi kepala (tertib terbalik), masukkannya ke dalam satuan. senarai terpaut di belakang nod d tengah.

4. Ciri-ciri senarai bersebelahan graf tidak berarah

adalah seperti berikut Jika terdapat n nod dan tepi dalam graf tidak berarah, maka terdapat n nod dalam jadual nod dan. 2e dalam jadual nod jiran.

Dasar nod ialah bilangan nod dalam senarai terpaut tunggal di belakang nod.

2. Struktur data senarai bersebelahan

1 Nod

termasuk data maklumat nod dan penunjuk ke titik bersebelahan pertama.

2 Titik bersebelahan

termasuk subskrip storan v titik bersebelahan dan penunjuk ke titik bersebelahan seterusnya, jika ia bersebelahan titik rangkaian , maka domain berat w perlu ditambah, seperti yang ditunjukkan dalam rajah di bawah.

3. Langkah-langkah algoritma

1 Masukkan bilangan nod dan tepi.

2 Masukkan maklumat nod secara bergilir-gilir, simpannya dalam medan data tatasusunan nod Vex[] dan biarkan medan pertama Vex[] kosong.

3 Masukkan dua nod yang dipasang pada setiap tepi secara bergilir-gilir Jika ia adalah rangkaian, anda juga perlu memasukkan berat tepi.

Jika ia adalah graf tidak terarah, masukkan a b, pertanyaan nod a, b, simpan subskrip i, j dalam tatasusunan nod Vex[], buat titik bersebelahan baharu s, biarkan s.v = j;s . next=null;Kemudian masukkan nod s sebelum titik bersebelahan pertama nod ke-i (kaedah interpolasi kepala). Dalam graf tidak berarah, terdapat tepi dari nod a ke nod b, dan terdapat tepi dari nod b ke nod a, jadi titik bersebelahan baharu s2 perlu dibuat, biarkan s2.v = i;s2.next= null; dan kemudian biarkan Nod s2 dimasukkan sebelum titik bersebelahan pertama nod ke-j (kaedah interpolasi kepala).

Jika ia adalah graf tidak terarah, masukkan a b, pertanyaan nod a, b, simpan subskrip i, j dalam tatasusunan nod Vex[], buat titik bersebelahan baharu s, biarkan s.v = j;s . next=null;Kemudian masukkan nod s sebelum titik bersebelahan pertama nod ke-i (kaedah interpolasi kepala).

Jika ia merupakan rangkaian tidak terarah atau rangkaian terarah, ia diproses dengan cara yang sama seperti graf tidak terarah atau graf terarah, kecuali nod bersebelahan mempunyai domain berat tambahan.

4. Perlaksanaan

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.

Atas ialah kandungan terperinci Cara menggunakan senarai bersebelahan untuk menyimpan graf di Jawa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!