一、简介和特点

邻接表是一种常用的图存储结构，它使用链表来表示图中顶点之间的邻接关系。本文实现的邻接表类可以高效地表示稀疏图，并支持动态添加顶点和边。

‌主要特点‌：

1. 空间效率：特别适合存储稀疏图

2. 动态扩展：可以灵活添加顶点和边

3. 直观表示：直接反映图的连接关系

4. 权重支持：可以存储边的权重信息

5. 简单接口：提供基本的图操作功能

二、与其他实现的优点

相比邻接矩阵实现，这种邻接表实现有以下优势：

1. 1‌.空间节省‌：只存储实际存在的边

2. ‌2.动态扩展‌：无需预先确定图的大小

3. ‌3.高效遍历‌：可以快速访问某个顶点的所有邻接点

4. ‌4.权重灵活‌：每条边可以存储不同的权重值

5. ‌5.实现简洁‌：指针操作直观反映图结构

三、实现步骤解析

1. ‌定义边结构‌：创建包含目标顶点、边数据和next指针的边节点

2. ‌定义顶点结构‌：创建包含顶点数据和第一条边指针的顶点节点

3. ‌图类设计‌：

• 提供默认和指定大小的构造函数

• 维护顶点计数器

4. ‌核心操作实现‌：

• 添加边：在指定顶点的边链表中插入新边

• 添加顶点：设置顶点数据并增加计数

5. ‌辅助功能‌：

• 打印整个图的邻接表表示

四、完整代码和注释

#include<iostream>
using namespACe std;

// 边结构体，表示图中的边
struct edge
{
    int nextnum;        // 边指向的顶点编号
    int data;           // 边存储的数据(如权重)
    edge* next=nullptr; // 指向下一条边的指针
};

// 顶点结构体，表示图中的顶点
struct listnode
{
    int data;           // 顶点存储的数据
    edge* first=nullptr;// 指向第一条边的指针
};

// 图类，使用邻接表实现
class graph{
    listnode* g;        // 邻接表数组
    int n = 0;          // 顶点计数器
    
public:
    // 指定大小的构造函数
    graph(int num){
        g = new listnode[num]; // 分配顶点数组
    }
    
    // 默认构造函数(默认大小1001)
    graph(){
        g = new listnode[1001];
    }
    
    // 添加边的方法
    void addedge(int head, int tail, int data){
        edge* tmp = g[head].first; // 获取顶点的第一条边
        
        // 如果顶点没有边，直接添加为第一条边
        if (!tmp) {
            g[head].first = new edge;
            g[head].first->data = data;
            g[head].first->nextnum = tail;
        }
        else {
            // 否则遍历到边链表末尾添加新边
            while (tmp->next) 
                tmp = tmp->next;
            tmp->next = new edge;
            tmp->next->data = data;
            tmp->next->nextnum = tail;
        }
    }
    
    // 添加顶点的方法
    void addnode(int k, int data){
        g[k].data = data; // 设置顶点数据
        n++;              // 增加顶点计数
    }
    
    // 打印图的邻接表表示
    void print(){
        for (int i = 0;i < n;i++){
            cout << g[i].data << "->"; // 打印顶点数据
            edge* tmp = g[i].first;    // 获取第一条边
            
            // 遍历打印所有邻接边
            while (tmp) {
                cout << tmp->nextnum<<"("<<tmp->data << ")->";
                tmp = tmp->next;
            }
            cout <<"null"<< endl; // 边链表结束标记
        }
    }
};

五、总结

本文介绍了一种邻接表实现的图数据结构，通过详细的代码注释和分步解析，展示了图的基本操作实现。邻接表在表示稀疏图时具有明显的空间优势，适合处理顶点多但边相对少的图结构。理解这种实现方式对于学习图算法和网络分析有重要意义。