Time complexity of adjacency list representation?

Viewed 24080

I am going through this link for adjacency list representation.

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

I have a simple doubt in some part of a code as follows :

// 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");
    }
}

Since, here for every V while loop is executed say d times where d is the degree of each vertex.

So, I think time complexity is like

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

All this sums up O(E), but the link says that time complexity is O(|V|+|E|)


Not sure what is the problem with the understanding. Some help needed here

1 Answers
Related