Java怎麼用鄰接表儲存圖

一、點睛

鄰接表是圖的一種鍊式儲存方法，其資料結構包括兩部分：節點和鄰接點。

用鄰接表可以表示無向圖，有向圖和網。在此用無向圖進行說明。

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個節點。

節點的度數為該節點後面單鍊錶中的節點數。

二、鄰接表的資料結構

1.節點

包括節點資訊 data 和指向第 1 個鄰接點的指標 first。

2.鄰接點

包含該鄰接點的儲存下標v 和指向下一個鄰接點的指標 next，如果是網路的鄰接點，則還需增加一個權值域 w，如下圖所示。

三、演算法步驟

1 輸入節點數與邊數。

2 依序輸入節點訊息，將其儲存到節點數組 Vex[] 的 data 域中，並將 Vex[] first 域置空。

3 依序輸入每條邊依附的兩個節點，如果是網，則還需要輸入該邊的權值。

如果是無向圖，則輸入 a b,查詢節點a、b 在節點數組 Vex[] 中儲存下標 i、j，並建立新的鄰接點 s，讓 s.v = j;s .next=null;然後將節點s 插入第 i 個節點的第1 個鄰接點之前（頭插法）。在無向圖中，從節點a 到節點b 有邊，從節點b 到節點a 也有邊，因此也需要建立一個新的鄰接點s2，讓s2.v = i;s2.next=null;然後讓s2 節點插入第 j 個節點的第1 個鄰接點之前（頭插法）。

如果是無向圖，則輸入 a b,查詢節點a、b 在節點數組 Vex[] 中儲存下標 i、j，並建立新的鄰接點 s，讓 s.v = j;s .next=null;然後將節點s 插入第 i 個節點的第1 個鄰接點之前（頭插法）。

如果是無向網或有向網，則和無向圖或有向圖的處理方式一樣，只是鄰節點多了一個權值域。

四、實作

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; // 边数
}

五、測試

白色為輸出，綠色為輸入

以上是Java怎麼用鄰接表儲存圖的詳細內容。更多資訊請關注PHP中文網其他相關文章！