有人可以向我解释这个结构吗？

Question

我正在研究图论算法。我知道什么是图，什么是边等等。我在 c++ 中有这个脚本的第一部分，它声明了一些变量和一些结构，然后定义了一个添加边的函数。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

const int M = 500;
struct struct_edge
{
    int v; 
    struct_edge * n;  
};

typedef struct_edge * edge;  
struct_edge pool[M * M * 2]; 
edge top = pool, adj[M];    
int V, E, match[M], qh, qt, q[M], father[M], base[M];   
bool inq[M], inb[M], ed[M][M];   
void add_edge(int u, int v)
{
    top->v = v, top->n = adj[u], adj[u] = top++;
    top->v = u, top->n = adj[v], adj[v] = top++;
}

如果这还不够，我会放脚本的其他部分。我有一些问题无法理解为什么 struct_edge 有一个指向另一个 struct_edge 的指针（它是边而不是节点！）。我有一些严重的问题来理解这个声明： edge top = pool, adj[M]; top 是一个指向 struct_edge 的指针，它在内部有一个 struct 数组和一个 int 数组？！？如需完整代码，您可以查看此 link http://codeforces.com/blog/entry/49402

Answer 1

为了回答您的第一个问题，该图存储为 邻接列表 格式。每个节点都有一个关联的链表的边 (struct_edge)，每个边都有一个索引 (int v;) 到边缘末端的节点，和指向下一条边的指针 (struct_edge* n;)。索引指向 adj[M] 数组，该数组存储构成图形的 M 个节点。

第二个问题，pool是struct_edge的静态声明数组，OP用它来制作堆栈分配器，即新节点通过递增 top 来分配，它是指向堆栈顶部的指针。 top 被初始化为 pool 这是堆栈的基础（数组的开始）。

编辑：您链接的维基媒体图的指针排列图：

（注意索引从0开始而不是1，所以图表中的节点1对应代码中的v = 0）

有人可以向我解释这个结构吗？

Somebody can explain me this struct?

c++

struct

graph-theory