深入理解鄰接表存儲結構

鄰接表是一種用於存儲圖的數據結構，它以鏈表的方式存儲相鄰頂點之間的關係並記錄對應權值。在圖論中，鄰接表也是一種常用的存儲方式。

一、鄰接表的定義

鄰接表是指將每個頂點出邊的信息存儲在該頂點的鏈表中，由數組與鏈表組成。它表示了頂點之間的鄰接關係，並且具有較好的擴展性，因為我們只需要新建一個鏈表即可實現頂點的添加。

鄰接表的實現可以使用數組存儲頂點元素，每個數組元素對應一個頂點，該元素存儲了一個指向鏈表頭部的指針，它指向該頂點的出邊鏈表。鏈表中的每個節點則表示該頂點的一條出邊，其中包含了該邊指向的鄰接節點。

// 偽代碼示例
struct EdgeNode {
    int adjVex; // 鄰接點的索引
    int weight; // 權值
    EdgeNode* next; // 指向下一個鄰接節點的指針
};

struct VertexNode {
    DataType data; // 頂點數據域
    EdgeNode* firstEdge; // 指向第一條鄰接邊的指針
};

VertexNode adjList[maxSize]; // 定義鄰接表

二、鄰接表的優缺點

1. 優點

鄰接表存儲結構對於擁有稀疏的圖來說，其空間複雜度相比於鄰接矩陣來說，得到了極大的優化。因為鄰接表只需存儲每個頂點周邊的關係，而鄰接矩陣需要維護每個節點間的具體連接狀態，所以鄰接表尤其適合擁有大量存在孤立節點或連通度較低的圖。

鄰接表還能夠表現圖中的權值，因為每個節點都可以儲存它的出邊的權。這對於計算圖的最短路、最小生成樹等問題非常有用。

2. 缺點

鄰接表的缺點在於它不擅長回答某些涉及到「定點目標」的問題，例如判斷節點A和節點B是否相連。鄰接表需要遍歷A的所有鄰接點才能判斷A和B是否連通，這一點對時間複雜度有一定影響。

另外，相比於鄰接矩陣，鄰接表的建圖時間和遍歷時間都需要更多時間。

三、鄰接表的實現

下面通過 C++ 代碼實現從文件中讀取圖數據並將其存儲為鄰接表。本示例將讀取文件中每一行數據，並通過空格分隔兩個節點和對應的邊權，最後將所有數據存儲在鄰接表中。

#include 
#include 
#include 
#include 
using namespace std;

const int MAXVEX = 100;
const int MAXSIZE = 10000;

typedef struct EdgeNode { // 邊表節點結構體
    int adjvex; // 鄰接點域，存儲該頂點對應的下標
    int weight; // 權值
    struct EdgeNode* next; // 鏈域，指向下一個鄰接點
} EdgeNode;

typedef struct VertexNode { // 頂點表節點結構體
    string data; // 頂點域，存儲頂點信息
    int in; // 記錄節點入度
    EdgeNode* firstedge; // 邊表頭指針
} VertexNode, AdjList[MAXVEX];

typedef struct GraphAdjList { // 定義鄰接表結構體
    AdjList adjList;
    int numVertexes, numEdges; // 圖的當前節點數和邊數
} GraphAdjList;

bool createFromFile(string filename, GraphAdjList& GL); // 從文件中讀取數據，建立鄰接表

int main() {
    GraphAdjList G;
    if (createFromFile("input.txt", G)) {
        cout << "Read successfully." << endl;
    } else {
        cout << "File not found." <> GL.numVertexes >> GL.numEdges; // 讀取節點數和邊數
    vector temp(MAXSIZE, -1); // 定義零時數組
    int k = 0;
    for (int i = 0; i > GL.adjList[i].data;
        GL.adjList[i].in = 0;
        GL.adjList[i].firstedge = nullptr;
    }
    for (int j = 0; j > x >> y >> weight;
        temp[k++] = x;
        temp[k++] = y;
        temp[k++] = weight;
    }
    int sum = k / 3;
    for (int i = 0; i adjvex = n;
        e->weight = weight;
        e->next = GL.adjList[m].firstedge; // 插入到邊表頭部
        GL.adjList[m].firstedge = e;
        GL.adjList[n].in++; // 記錄每個節點的入度
    }
    return true;
}

四、總結

鄰接表是一種經典的圖存儲結構，採用鏈表的方式便於快速存儲邊的信息。鄰接表能夠很好地處理稀疏圖，具有較好的擴展性，同時還記錄了邊的權重信息，在計算最短路等問題中獲得了廣泛應用。

當然，鄰接表在某些涉及到「點與點之間的關係」問題的處理速度上可能會略遜於鄰接矩陣，但是對於實現圖的許多演算法，它們所需求的時間僅僅是與頂點數量和邊長有關的，這樣在規模較大的圖的處理方面具有明顯的優勢。