CMSC 351 (JWG) Homework 10

1. Given the adjacency matrix AM for a graph with n vertices and a list V of k vertices, write [25 pts] the pseudocode for a function istrail(AM,n,V,k) which would determine whether V specifies a trail, returning either TRUE or FALSE. What is the best- and worst-case Θ time complexity of your pseudocode?

Solution:

Given the adjacency list AL for a graph with n vertices and a list V of k vertices, write the [25 pts] pseudocode for a function iswalk(AL,n,V,k) which would determine whether V specifies a walk, returning either TRUE or FALSE. What is the best- and worst-case Θ time complexity of your pseudocde?

Solution:

Show the functioning of the shortest-path algorithm applied to the following graph with s = 1 [13 pts] and t = 3. Show the steps as we did in class (and in the notes) and show the queue at each step.

Solution:

In the shortest path algorithm suppose the graph were weighted instead of unweighted. If the [12 pts]

line

dist[y] = dist[x] + 1

were replaced by

dist[y] = dist[x] + edgeweight(x to y)

would this effectively find the shortest total weighted distance from s to t? If so, explain why.

If not, explain why not and give an example graph to support your argument.

Solution: