Минимальное использование памяти в топологической сортировке

Учитывая вашу формулу использования памяти, вам нужно не использовать более 2 байтов на ребро и не более 10 байтов на вершину (за исключением, возможно, некоторых небольших накладных расходов, которые поместятся в 4 МБ свободного места).

Ваша реализация списка смежности хранит список смежности в виде массива указателей. Это нецелесообразно, поскольку указатель имеет размер 4 или, скорее, 8 байт. Проиндексируйте свои вершины и замените указатели на вершины на uint16_t (2 байта).

Детали:

• Хранить все ребра в массиве: uint16_t edges[E]; Все ребра из определенной вершины будут храниться в этом массиве непрерывно. Сначала ребра выходят из первой вершины, затем ребра выходят из второй вершины и так далее.
• Имейте массив uint32_t vertices[V][2]; для вершин. Сохраняются два значения: индекс в массиве ребер и количество ребер за пределами этой вершины.

Легко видеть, что для представления графика используется 2E+8V байт.

Когда вы запускаете топосортировку, вам нужно подсчитывать каждую вершину (описывая, сколько внутренних ребер осталось у вершины). Используйте для этого массив uint16_t in_count[V];. uint16_t снова достаточно, так как ни одна вершина не может иметь более 1999 внутренних ребер, когда V<=2000.

Это использует дополнительные 2 байта на вершину, что дает в общей сложности 2E+10V, как требуется.

Обратите внимание, что вы можете легко сэкономить 4 байта на вершину, не сохраняя количество ребер, а вместо этого полагаясь на конечный индекс ребер для конкретной вершины, являющийся начальным индексом для следующей вершины. Вам нужно будет добавить дополнительный индекс после последней вершины, чтобы отметить конец последнего ряда ребер. Я отмечаю, что это умно, но экономит не более 8 КБ при V‹ = 2000.

(В принципе, вы также можете сэкономить больше, упаковав данные более плотно. 2000 ‹ 10**11, поэтому вы можете упаковать данные о длине ребра и индексе вершины в 11 бит, а не в uint16_t. Код начнет становиться действительно уродливым для доступа сохраненные данные).

Я думаю, что нашел самое простое решение моей проблемы. Я только начал хранить график как битовый массив

Graph* createGraph(int V) {
    Graph* graph = malloc(sizeof(struct Graph));
    graph->V = V;
    graph->visited = (int*) calloc(V, sizeof(int));
    graph->adj = (unsigned char*) calloc(((V * V) / 8 + 1), sizeof(unsigned char));
    return graph;
}

void addEdge(Graph* graph, int src, int dest) {
    int newNode = src * graph->V + dest;
    graph->adj[newNode/8] |= (1 << newNode % 8);
}

void DFS(Graph* graph, int v, Stack* stack, Data data) {
    if (graph->visited[v] == 1) {
        fprintf(data.out, "impossible to sort");
        freeGraph(graph);
        freeStack(stack);
        shutdown(data);
    }

    if (graph->visited[v] == 0) {
        graph->visited[v] = 1;
        for(int u = 0; u < graph->V; u++) {
            int n = v * graph->V + u;
            if (graph->adj[n / 8] & (1 << n % 8))
                DFS(graph, u, stack, data);
        }
        graph->visited[v] = 2;
        push(stack, v);
    }
}