c - 在图中删除/插入顶点的问题

Question

我试图在 C 中使用数组来存储顶点和邻接矩阵来存储边来实现图形。

顶点都是“命名的”，名称是它们在数组中的索引。例如，如果我通过给它索引“2”来添加顶点，它将被放置在数组的第三个位置，这样如果我想检查矩阵中的两个顶点是否相邻，它可以在 O(1) 中完成。

如果数组已满，我将进行重新分配以增加其大小，以便每次添加都成功。

嗯，有一些问题。

• 如果我删除一个节点怎么办？数组中会有未使用的空间，所以很浪费内存。（我不能移动所有其他顶点，因为可能会发生名为“10”的顶点将移动到不同的位置，所以如果我想检查节点“10”的相邻节点，结果将是另一个节点的相邻节点）

• 如果我添加一个名为“50”的节点并且数组长度只有 10 怎么办？我必须分配一个至少有 51 个位置的数组，并且会有很多未使用的空间。

您有任何提示或解决方案吗？

标签： cgraph

Answer 1

不要使用数组。使用双链表。这样，您可以随意添加和删除节点。

这是一个粗略的例子：

typedef struct node {
    int vertex;
    node prev;
    node next;
} *node;

node *global;

void insert_node(node a)
{
    global->next = a;
    global->next->vertex = global->vertex + 10;
    global->next->prev = global;
    global = global->next;
}

void delete_node(node b)
{
    while( global->prev )
        global = global->prev;
    while( global != b )
        global = global->next;

    global->prev->next = global->next;
    global->next->prev = global->prev;

    while( global->next )
        global = global->next;

    free(b);
}

node create_node(void)
{
    node ret;
    ret = malloc(sizeof(*ret));
    memset(ret, 0, sizeof(*ret));
    insert_node(ret);
    return global;
}