Question

1. 
   Use the weighted digraph for problems below:
   

      V = {a, b, c, d, e, f, g, h}
   
      E = {(a,b,6), (a,d,3), (b,c,2), (b,e,5), (c,f,4), (d,e,9), (d,g,1), (e,f,7), (e,g,8), (e,h,2), (f,h,4), (g,h,4)}
   
   
   

2. (3 pts.) What is the length of the longest path from a to h? Show the path!
   
3. (2 pts.) Does the graph contain a cycle? Justify your answer!
   
4. (3 pts.) Give the adjacency matrix for the graph.
   
5. (4 pts.) Provide the order in which nodes would be visited in a depth-first traversal starting at a. State any assumptions you made in arriving at your answer.
   
6. (4 pts.) Provide the order in which nodes would be visited in a breadth-first traversal starting at a. State any assumptions you made in arriving at your answer.
   
7. (4 pts.) Perform Dijkstra's algorithm to obtain the shortest path from a to every other vertex in the graph. Show your work!

Answer 1

Given undirected graph

The length of the longest path from a to h is a - 6   b - 5   e - 9   d - 1   g - 4   h = 25(6+5+9+1+4)

The given graph contain a so many cycles a-b-e-g-d-a, b-c-f-h-e-b,a-b-c-f-h-e-g-d-a

Adjacency Matrix Representation of a graph

DFS: Step 1:                                        

Output: a b

Step 2:                                 

Output: a b c

Step 3:                            

Output: a b c f

Step 4:               

Output: a b c f h

Step 5:   

                                     

Output: a b c f h g

Step 6 :    

                             

Output: a b c f h g e

Step 7:                             

Output: a b c f h g e d

The DFS of a graph starting at vertex a is a b c f h g e d

DFS Tree as follows

         

BFS: Step 1:                                        

Output: a b

Step 2:                                 

Output: a b d

Step 3:                            

Output: a b d c

Step 4:               

Output: a b d c e

Step 5:                                        

Output: a b d c e g

Step 6 :                                 

Output: a b d c e g f

Step 7:                             

Output: a b d c e g f h

The BFS of a graph starting at vertex a is a b d c e g f h

BFS Tree as follows