- 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?

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?

- In what order will the vertices in the prerequisite graph be
visited in a depth-first traversal?
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.)