IC312: Data Structures (FA17)


Home Policy Calendar Units Assignments Resources

HW 9: Graphs

Solution

You can find the solution here

Overview

This is a written homework assignment. It is due in class, in hard-copy.

Due Date

This homework is due Wed. 20 Nov. in class

Grading

The assignment is graded out of 100 points. The value of questions are described below.

Submission and Starter Code

Submission must occur in hard copy at the start of class.

Problems

Consider the Adjacency list representation of a graph below:

A: [(A, C, 6), (A, G, 5)]
B: [(B, C, 7), (B, D, 8), (B, G, 5)]
C: [(C, A, 6), (C, B, 7), (C, E, 3), (C, F, 7), (C, G, 3), (C, H, 9)]
D: [(D, B, 8), (D, H, 8)]
E: [(E, C, 3), (E, F, 4)]
F: [(F, E, 4), (F, C, 7)]
G: [(G, A, 5), (G, B, 5), (G, C, 3)]
H: [(H, C, 9), (H, D, 8)]
  1. [10 points] Describe the important properties of the graph above, using the terminology we know about graphs. (Is it directed/undirected, cyclic/acyclic, connected/unconnected, etc.)
  2. [15 points] Draw a picture of the graph above.
  3. [20 points] Show the adjacency matrix representation of the graph above.
  4. [20 points] Perform a depth-first traversal of the graph above, starting with node A at the top of the stack, and list the order the nodes are visited in. Show your work.
  5. [20 points] Perform a breadth-first traversal of the graph above, starting at node A, and list the order the nodes are visited in. Show your work.
  6. [15 points] Draw an undirected, unweighted graph with 7 vertices, and the following degrees of each vertex: \[2, 3, 1, 4, 4, 5, 1\] Label each vertex with its degree in your final, neatly drawn graph.