深入理解邻接表存储结构

邻接表是一种用于存储图的数据结构，它以链表的方式存储相邻顶点之间的关系并记录对应权值。在图论中，邻接表也是一种常用的存储方式。

一、邻接表的定义

邻接表是指将每个顶点出边的信息存储在该顶点的链表中，由数组与链表组成。它表示了顶点之间的邻接关系，并且具有较好的扩展性，因为我们只需要新建一个链表即可实现顶点的添加。

邻接表的实现可以使用数组存储顶点元素，每个数组元素对应一个顶点，该元素存储了一个指向链表头部的指针，它指向该顶点的出边链表。链表中的每个节点则表示该顶点的一条出边，其中包含了该边指向的邻接节点。

// 伪代码示例
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." << endl;
    }
    return 0;
}

bool createFromFile(string filename, GraphAdjList& GL) {
    ifstream infile(filename); // 打开文件流
    if (!infile) { // 文件不存在
        return false;
    }
    infile >> GL.numVertexes >> GL.numEdges; // 读取节点数和边数
    vector
       temp(MAXSIZE, -1); // 定义零时数组
    int k = 0;
    for (int i = 0; i < GL.numVertexes; ++i) { // 输入顶点信息，建立顶点表
        infile >> GL.adjList[i].data;
        GL.adjList[i].in = 0;
        GL.adjList[i].firstedge = nullptr;
    }
    for (int j = 0; j < GL.numEdges; ++j) { // 输入边信息，建立邻接表
        string str;
        getline(infile, str); // 读取一行
        stringstream ss(str); // 将一行字符串转换为数字
        int x, y, weight;
        ss >> x >> y >> weight;
        temp[k++] = x;
        temp[k++] = y;
        temp[k++] = weight;
    }
    int sum = k / 3;
    for (int i = 0; i < sum; ++i) { // 建立邻接表
        int m = temp[i * 3];
        int n = temp[i * 3 + 1];
        int weight = temp[i * 3 + 2];
        EdgeNode* e = new EdgeNode; // 新建邻接表节点
        e->adjvex = n;
        e->weight = weight;
        e->next = GL.adjList[m].firstedge; // 插入到边表头部
        GL.adjList[m].firstedge = e;
        GL.adjList[n].in++; // 记录每个节点的入度
    }
    return true;
}

      
     
    
   
  

四、总结

邻接表是一种经典的图存储结构，采用链表的方式便于快速存储边的信息。邻接表能够很好地处理稀疏图，具有较好的扩展性，同时还记录了边的权重信息，在计算最短路等问题中获得了广泛应用。

当然，邻接表在某些涉及到“点与点之间的关系”问题的处理速度上可能会略逊于邻接矩阵，但是对于实现图的许多算法，它们所需求的时间仅仅是与顶点数量和边长有关的，这样在规模较大的图的处理方面具有明显的优势。