Question

A tree can be considered as a structured graph. Write a C++ function that receives a BST object and returns its corresponding graph representation, implemented via an adjacency list. What will be the impact on the search complexity?

Answer 1

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

The important thing here is that for the time complexity to be valid, we need to cover every possible situation:

• The outer loop is executed O(|V|) regardless of the graph structure.
  • Even if we had no edges at all, for every iteration of the outer loop, we would have to do a constant number of operations (O(1))
  • The inner loop is executed once for every edge, thus O(deg(v)) times, where deg(v) is the degree of the current node.
  • Thus the runtime of a single iteration of the outer loop is O(1 + deg(v)). Note that we cannot leave out the 1, because deg(v) might be 0 but we still need to do some work in that iteration
• Summing it all up, we get a runtime of O(|V| * 1 + deg(v1) + deg(v2) + ...) = O(|V| + |E|).