Homework 12 Fundamental Algorithms

Due May 3-d A.Paz

  1. A UG is described below where A-5-B denotes "vertex A is connected to vertex B with weight 5". A-5-B-2-C-1-D-6-E-7-F-3-A; F-3-G-1-H-4-C; A-2-G-3-E; B-3-H-2-D. For the above UG do the following

    (i) Ignore weights and apply the DFS algorithm. Show the order in which the vertices of the graph are visited.

    (ii) Same as (i) but with BFS.

    (iii) With weights, find the single source shortest paths from A .

    (iv) With weights , find all distances shortests paths.

    (v) Find a minimum weight spanning tree for the graph.

  2. Write an algorithm whose input is a connected UG and whose output is an EDGE traversal of the graph in which each edge appears exactly twice. (The algorithm should output the edges in the order that they are traversed). Apply your algorithm to the graph in exercise 1.

  3. Exercise 4.10 (p 406) in the book

  4. Exercise 4.31 (p.410) in the book