Проблемы удаления / вставки вершины в графе

Question

Я пытаюсь реализовать граф на C, используя массив для хранения вершин и матрицу смежности для хранения ребер.

Все вершины имеют «имя», имя - это их индекс в массиве.Например, если я добавлю вершину, указав ей индекс «2», она будет помещена в третью позицию массива, чтобы, если я хочу проверить, смежны ли две вершины в матрице, это можно сделать в O (1).

Если массив заполнится, я сделаю realloc, увеличивая его размер, чтобы каждое добавление было успешным.

Что ж, есть некоторые проблемы.

• * 1010Что делать, если я удалю узел?В массиве будет неиспользуемое пространство, так что это пустая трата памяти.(Я не могу сдвинуть все другие вершины, потому что может случиться так, что вершина с именем «10» будет перемещена в другую позицию, поэтому, если я хочу проверить смежность с узлом «10», результат будет смежным с другим узлом)

• Что если я добавлю узел с именем "50", а длина массива составит всего 10?Я должен выделить массив не менее 51 позиции, и там будет много неиспользуемого пространства.

У вас есть какие-либо советы или решения?

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;
}