Problem Set Answers: Graphs

1. Adjacency matrix for the undirected graph:

   
                 [0] [1] [2] [3] [4] [5] [6] [7]
    [0]  A     [0]  0   1   1   1   0   0   0   0
    [1]  B     [1]  1   0   1   0   0   1   0   0
    [2]  C     [2]  1   1   0   1   1   0   0   0
    [3]  D     [3]  1   0   1   0   0   0   0   0
    [4]  E     [4]  0   0   1   0   0   1   1   1
    [5]  F     [5]  0   1   0   0   1   0   1   0
    [6]  G     [6]  0   0   0   0   1   1   0   0
    [7]  H     [7]  0   0   0   0   1   0   0   0
   
   

   Adjacency list for the undirected graph:

   

   Adjacency matrix for the directed graph:

   
                 [0] [1] [2] [3] [4] [5] [6] [7] [8]
    [0]  A     [0]  0   1   1   0   0   0   0   0   0
    [1]  B     [1]  0   0   1   0   0   0   0   1   0
    [2]  C     [2]  0   0   0   1   1   0   0   0   0
    [3]  D     [3]  0   0   0   0   0   0   0   1   0
    [4]  E     [4]  0   0   0   0   0   0   1   0   0
    [5]  F     [5]  0   0   0   0   0   0   1   0   1
    [6]  G     [6]  0   0   1   0   0   0   0   0   0
    [7]  H     [7]  0   0   0   0   0   0   1   0   0
    [8]  I     [8]  0   0   1   0   0   0   0   0   0
   
   

   Adjacency list for the directed graph:

   

2. DFS undirected: A B C D E F G H

   DFS directed: A B D H G C E F I

3. BFS undirected: A B C D F E G H

   BFS directed: A B C D H E G F I

4. DFS undirected: 1 2 3 5 6 11 7 10 4 9 8

   DFS directed: 1 4 3 2 9 7 6 5 8 11 10

5. BFS undirected: 1 2 7 9 3 4 5 7 8 10 11 6

   BFS directed: 1 4 6 3 7 5 11 2 10 8 9

6.  

   

7.  

   
8. There are two MSTs for this graph. Either can be generated by Kruskal or by Prim; it depends on which edge you choose when you have equal weights.
   

Email Me | Office Hours | My Home Page | Department Home | MCC Home Page

© Copyright Emmi Schatz 2017