代码之家 › 专栏 › 技术社区 › Garrick

邻接表表示的时间复杂度?

adjacency-list breadth-first-search time-complexity algorithm

10

Garrick · 技术社区 · 9 年前

我正在通过这个链接获取邻接列表表示。

http://www.geeksforgeeks.org/graph-and-its-representations/

// A utility function to print the adjacenncy list representation of graph
void printGraph(struct Graph* graph)
{
    int v;
    for (v = 0; v < graph->V; ++v)
    {
        struct AdjListNode* pCrawl = graph->array[v].head;
        printf("\n Adjacency list of vertex %d\n head ", v);
        while (pCrawl)
        {
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}

因为,这里是每一个 V 执行循环时,例如 d

所以,我认为时间复杂性就像

d0 + d1 + d2 + d3 ....... +dV where di is the degree of each vertex.

所有这些总结了O(E),但链接说时间复杂度是O(|V |+| E 124;)

不确定理解有什么问题。这里需要一些帮助

1 回复 | 直到 9 年前

1

19

Tobias Ribizel 9 年前

这里重要的是,为了使时间复杂性有效,我们需要涵盖所有可能的情况:

无论图形结构如何,外部循环都是O(|V |)执行的。
- 即使我们根本没有边,对于外循环的每次迭代,我们也必须进行恒定数量的运算(O(1))
- 每个边执行一次内循环,因此执行O(deg(v))次,其中deg(v)是当前节点的次数。
综上所述,我们得到了O(|V |*1+deg(v1)+deg(v2)+…)=O(|V |+E)。

说明仅在外回路中完成的功。因此,我们不能简单地删除| V |项。