关于《算法设计手册》v3中邻接表insert_edge函数的疑问

我正在研读Skiena所著的《Algorithm Design Manual v3》，知道书中有一些笔误，但不确定当前遇到的是笔误还是自己理解错了。下面是书中用邻接表创建图的代码：

typedef struct edgenode {
    int y;                   /* adjacency info */
    int weight;              /* edge weight, if any */
    struct edgenode *next;   /* next edge in list */
} edgenode;

typedef struct {
    edgenode *edges[MAXV+1];  /* adjacency info */
    int degree[MAXV+1];       /* outdegree of each vertex */
    int nvertices;            /* number of vertices in the graph */
    int nedges;               /* number of edges in the graph */
    int directed;             /* is the graph directed? */
} graph;

void insert_edge(graph *g, int x, int y, bool directed) {
    edgenode *p;        /* temporary pointer */

    p = malloc(sizeof(edgenode));    /* allocate edgenode storage */

    p->weight = 0;
    p->y = y;
    p->next = g->edges[x];

    g->edges[x] = p;    /* insert at head of list */

    g->degree[x]++;

    if (!directed) {
        insert_edge(g, y, x, true);
    } else {
        g->nedges++;
    }
}

我理解void insert_edge(graph *g, int x, int y, bool directed)函数是通过将节点加入edges数组来连接索引为x和y的节点，但对其中这段代码逻辑感到困惑：

p->y = y;
p->next = g->edges[x];

g->edges[x] = p;    /* insert at head of list */

假设首次输入x=3、y=4的有向图，我预期是3 -> 4，但：

1. p->y = y我能理解，即x的邻接点是y；
2. edges数组初始为null，p->next = g->edges[x]会让3的next为null而非4，这让我疑惑；
3. g->edges[x] = p的操作也让我困惑，我误以为应该是p.next = y且y.next = NULL。

代码逻辑解析 #

这段代码用的是标准的邻接表头插法，你的困惑源于对邻接表存储结构的误解，拆解说明如下：

• 邻接表的核心存储逻辑：
  graph里的edges数组，每个元素是一个edgenode*指针，代表对应顶点的邻接边链表表头。每个edgenode不是顶点，而是一条从当前顶点出发的边：

  • y字段：这条边指向的目标顶点编号；
  • next字段：指向同起点的下一条边，而非目标顶点的指针。

• 针对x=3、y=4的有向图实例：

  1. 初始状态下，g->edges[3]为NULL，说明顶点3还没有任何出边；
  2. 新建edgenode指针p，p->y = 4明确这条边是从3指向4；p->next = g->edges[3]即p->next = NULL，因为这是3的第一条出边，后面没有其他边；
  3. g->edges[3] = p把这个新边节点设为顶点3的邻接链表表头。此时顶点3的邻接链表就是p（指向4），p->next为NULL，完全符合3 -> 4的预期。

• 纠正你的误解：
  你错误地认为edgenode的next是指向目标顶点的指针，但实际上这里的顶点并没有单独的结构体，只是用数组索引（比如3、4）来代表顶点编号。next的作用是把同一个顶点的所有出边串联成链表，方便遍历该顶点的所有邻接点。

• 补充insert_edge的整体逻辑：
  当插入无向边时，会递归调用自身插入反向的有向边（insert_edge(g, y, x, true)）；只有处理有向边（包括递归时的反向边）时才会增加nedges计数，避免重复统计无向边的数量。

内容的提问来源于stack exchange，提问作者VIAGC