# IC312: Data Structures (FA16)

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. 21 Nov. in class

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.