Java用鄰接表存儲圖的示例代碼

Posted on by

一、點睛

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

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

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用鄰接表存儲圖的示例代碼的詳細內容，更多關於Java鄰接表存儲圖的資料請關註WalkonNet其它相關文章！

推薦閱讀：