图的邻接表存储及遍历操作

邻接表是一种常用的图的存储结构，它通过链表来表示每个顶点的邻接点集合。邻接表的具体实现可以使用数组加链表的方式，也可以使用纯链表的方式。

邻接表存储结构的优点是可以很方便地遍历某个顶点的邻接点，而且可以节省空间。但是，对于需要查找两个顶点之间是否有边的操作，邻接表的效率就不如邻接矩阵了。

下面是邻接表的存储结构定义：

// 邻接表的存储结构定义
#define MAX_VERTEX_NUM 100  // 最大顶点数
typedef struct ArcNode {   // 边结点
    int adjvex;            // 邻接点在顶点数组中的下标
    struct ArcNode *next;  // 指向下一个边结点的指针
    // 也可以在这里存储边的权值等信息
} ArcNode;
typedef struct VNode {     // 顶点结点
    char data;             // 顶点的数据
    ArcNode *firstarc;     // 指向第一个边结点的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {           // 邻接表
    AdjList vertices;      // 顶点数组
    int vexnum, arcnum;    // 顶点数和边数
} ALGraph;

邻接表的遍历可以使用深度优先搜索（DFS）或广度优先搜索（BFS）算法。下面是DFS的遍历代码：

// 邻接表的深度优先搜索遍历
void DFS(ALGraph *G, int v, bool visited[]) {
    visited[v] = true;
    printf("%c ", G->vertices[v].data);  // 访问顶点v
    ArcNode *p = G->vertices[v].firstarc;
    while (p != NULL) {                  // 遍历v的所有邻接点
        int w = p->adjvex;
        if (!visited[w]) {
            DFS(G, w, visited);
        }
        p = p->next;
    }
}

BFS的遍历代码如下：

// 邻接表的宽度优先搜索遍历
void BFS(ALGraph *G, int v, bool visited[]) {
    visited[v] = true;
    printf("%c ", G->vertices[v].data);  // 访问顶点v
    queue<int> Q;                        // 使用队列存储待访问的顶点
    Q.push(v);
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        ArcNode *p = G->vertices[u].firstarc;
        while (p != NULL) {              // 遍历u的所有邻接点
            int w = p->adjvex;
            if (!visited[w]) {
                visited[w] = true;
                printf("%c ", G->vertices[w].data);  // 访问顶点w
                Q.push(w);
            }
            p = p->next;
        }
    }
}

以上就是邻接表的存储和遍历操作。需要注意的是，邻接表的实现也可以使用其他数据结构，这里给出的只是一种常见的方式。