隣接リストを使用して Java にグラフを保存する方法

1. 最後の仕上げ

隣接リストはグラフの連鎖保存方法であり、そのデータ構造はノードと隣接ポイントの 2 つの部分で構成されます。

隣接リストは、無向グラフ、有向グラフ、およびネットワークを表すために使用できます。これを無向グラフを使用して説明します。

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 です。これらは、頭部補間方法（逆順）。

4. 無向グラフ

隣接リストの特徴は次のとおりです. 無向グラフに n 個のノードと e 個のエッジがある場合、ノード テーブルには n 個のノードと 2e 個のエッジが存在します隣接ノード テーブルのノード。

ノードの次数は、そのノードの背後にある単一リンク リスト内のノードの数です。

2.隣接リストのデータ構造

1.Node

には、まずノード情報データと最初の隣接点へのポインタが含まれます。

2. 隣接ポイント

隣接ポイントの記憶添字 v と、隣接ポイントの場合は次の隣接ポイント next へのポインタが含まれます。ネットワーク の場合、次の図に示すように、重みドメイン w を追加する必要があります。

3. アルゴリズムのステップ

1 ノードとエッジの数を入力します。

2 ノード情報を順番に入力し、ノード配列 Vex[] のデータ フィールドに格納し、Vex[] の最初のフィールドは空白のままにします。

3 各エッジに接続されている 2 つのノードを順番に入力します。ネットワークの場合は、エッジの重みも入力する必要があります。

無向グラフの場合は、 b を入力し、ノード a、b をクエリし、添え字 i、j をノード配列 Vex[] に格納し、新しい隣接点 s を作成します ( s.v = j;s とします)。 next=null;次に、i 番目のノードの最初の隣接点の前にノード s を挿入します (先頭補間法)。無向グラフでは、ノード a からノード b へのエッジがあり、ノード b からノード a へのエッジがあるため、新しい隣接点 s2 を作成する必要があります。s2.v = i;s2.next= とします。 null; and then let j 番目のノードの最初の隣接点の前に s2 ノードを挿入します (先頭補間法)。

無向グラフの場合は、 b を入力し、ノード a、b をクエリし、添え字 i、j をノード配列 Vex[] に格納し、新しい隣接点 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 中国語 Web サイトの他の関連記事を参照してください。