Graph Exercises

Prerequisite Graph

1. The graph above illustrates the prerequisite structure for eight computer science courses. Answer the following questions:
   • Is this graph directed?
   • Is this graph weighted?
   • Does this graph contain any cycles?
   • Would you describe this graph as sparse? or dense?
   • What is the in degree of CS 240?
   • What is the out degree of CS 240?
   • Ignoring the edge directions, what is the largest clique in this graph?
   • Ignoring the edge directions, how many connected components does this graph have?
   • Draw the in-memory representation of this graph both as an adjacency matrix and an adjacency list. Construct your adjacency list so that edge lists are sorted by course number. You may label each vertex using an integer, where each course is numbered in order: CS149->0, CS159->1 ...
     
     
     
     
     
     
     
     
     
     
   • For this example, which of these graph representations is more memory-efficient?

2. The following code snippets implement depth-first search and breadth-first search respectively.

   
   void graphTraverse(Graph G) {
       int v;
       for (v=0; v<G.nodeCount(); v++)
           G.setValue(v, null); // Initialize
       for (v=0; v<G.nodeCount(); v++)
           if (G.getValue(v) != VISITED)
               doTraversal(G, v); // Replace with either DFS or BFS
   }
   
   void DFS(Graph G, int v) {
       PreVisit(G, v);
       G.setValue(v, VISITED);
       int[] nList = G.neighbors(v);
       for (int i=0; i< nList.length; i++)
           if (G.getValue(nList[i]) != VISITED)
              DFS(G, nList[i]);
       PostVisit(G, v);
   }
   
   void BFS(Graph G, int v) {
       LQueue Q = new LQueue(G.nodeCount());
       Q.enqueue(v);
       G.setValue(v, VISITED);
       while (Q.length() > 0) { // Process each vertex on Q
           v = (Integer)Q.dequeue();
           PreVisit(G, v);
           int[] nList = G.neighbors(v);
           for (int i=0; i< nList.length; i++)
               if (G.getValue(nList[i]) != VISITED) { // Put neighbors on Q
                   G.setValue(nList[i], VISITED);
                   Q.enqueue(nList[i]);
               }
           PostVisit(G, v);
       }
    }

   • In what order will the vertices in the prerequisite graph be visited in a depth-first traversal?  
     
     
     
   • In what order will they be visited in a breadth-first traversal?
     
     
     
     
     

3. Draw the in-memory representations of the undirected version of the graph above. (In other words, every directed edge is replaced by an undirected edge.)