图的这种实现是否与边数呈线性关系？

Question

我有一个 class，它类似于加权有向图的邻接矩阵表示。假设该图有 n 个顶点。它是这样工作的：

首先，分配n²个槽来存放整数（存储在名为graph的变量中），形式为n个数组，每个数组有n 个整数。
为边分配权重，其中graph[i][j]表示从顶点i到顶点j的边的权重。
取消分配图中任何未使用的槽

示例代码：

class DiGraph {
    public:
        Graph() {}
        Graph(size_t n) {
            graph.resize(n);
            for (size_t i = 0; i < n; i++) {
                graph[i] = new int[n]{-1};
            }
        }
        void addEdge(int from, int to, int weight) {
            graph[from][to] = weight;
        }
        int& getEdge(int from, int to) {
            return *(graph[from] + to);
        }
        void finalizeGraph() {
            for (size_t i = 0; i < n; i++) {
                for (size_t j = 0; j < n; j++) {
                    if (graph[i][j] == -1) {
                        delete &graph[i][j];
                    }
                }
            }
        }
    private:
        vector<int*> graph;
};

现在我想实现一种算法，该算法只适用于图的现有边。换句话说，除了输入图中已经存在的边之外，该算法不应该创建新的边。我想高效地使用内存，同时实现对两个顶点之间任意边的 O(1) 访问。

图的上述实现的space复杂性有效地与边数成线性关系吗？

Answer 1

不，它不是，除非你能证明你分配和释放边缘的方式独立于 n，根据你的描述，这是不可能的。

请记住，Big O 符号考虑的是算法的最坏情况。由于您首先分配 n^2 个槽，然后删除 non-existing 个边，因此最坏情况下您的算法运行时间是 O(n^2)，而不是 O(n)。换句话说，随着 n 的增长，您的算法运行时间也会随着 O(n^2) 增长，因为您必须分配和取消分配不存在的边。这是真的，除非你能证明你分配和释放边缘的方式独立于 n.

为了在边方面达到线性运行时，您需要一个不同的数据结构，其中边的工作量为 O(m)，其中 m 是边的数量。

但是，您可以争辩说，如果给出这样的图，即删除 non-existing 条边，则每条边的访问时间可以是 O(1)，假设您的数据结构支持它.

图的这种实现是否与边数呈线性关系？

Is this implementation of a graph effectively linear in the number of edges?

c++

data-structures

space-complexity

directed-graph