Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP9024 23T2

Week 5 Problem Set

Digraphs, Minimum Spanning Tree, Shortest Path

1.  (Graph representations)

a.  Consider the following graphs, where bi-directional edges are depicted as two-way arrows rather than having two separate edges going in opposite directions:

For each of the graphs show the concrete data structures if the graph was implemented via:

1.  adjacency matrix representation (assume full V×V matrix)

2.  adjacency list representation (if non-directional, include both (v,w) and (w,v))

b.  Consider the following map of streets in the Sydney CBD:

Represent this as a directed graph, where intersections are vertices and the connecting streets are edges. Ensure that the directions on the edges correctly reflect any one-way streets (this is a driving map,  not a walking map). You only need to make a graph which includes the intersections marked with red letters. Some things that don't show on the map: Castlereagh St is one-way heading south, Curtin Pl is a little laneway that you can't drive down and George St is closed for cars between "F" and "K".

For each of the following pairs of intersections, indicate whether there is a path from the first to the second. Show a simple path if there is one. If there is more than one simple path, show two different paths.

1.  from intersection "D" on Margaret St to insersection "L" on Pitt St

2.  from intersection "J" to the corner of Margaret St and York St (intersection "A")

3.  from intersection "P" on Castlereagh St to the corner of Margaret St and Wynyard Ln ("C")

4.  from the intersection of Castlereagh St and Hunter St ("M") to intersection "H" at Wynyard Park

2.  (Digraphs)

Write a program pageRank .c that:

1.  builds a directed graph from user input, where each node represents a webpage:

first, the program prompts for the number of webpages

then, the program repeatedly asks to input information about links on a webpage

until any non-numeric character(s) are entered

2.  ranks all the nodes according to the number of inbound links. If two nodes page1 and page2 have the same number of inbound links, then they are ranked according to the following scoring of their outbound links:

The score for the outbound links of a page i is

the number of outbound links on page i

plus the sum of the number of inbound links on all the pages that pagei links to.

Formally: If In(i) are all the webpages with a link to i , and Out(i) are all the links from i , then the score for i is: |Out(i)| + ∑ ∣In(j)∣ .

For example, suppose that p1 and p2 have the same number of inbound links. If p 1 links to two pages, both of which have 3 inbound links, and p2 links to only one page, which has 8 inbound links, then p2 is ranked higher because 1+8 > 2+3+3.

3.  outputs the nodes from highest to lowest ranked. Nodes that rank equally on both criteria (the number of inbound links and the score of their outbound links) should be displayed in their natural (increasing) order.

Your program should use the Weighted Graph ADT (WGraph.h, WGraph.c) from the lecture. Do not change the header file or the ADT implementation.

Hints:

You can assume that the input is correct (a positive integer n, followed by pairs of integers in the range 0…n- 1, followed by non-numeric input) .

You cannot use the standard Graph ADT since this assumes undirected edges .

You can use a modified version of the sorting algorithm (inssort.c) from Week 1 if you wish .

An example of the program executing is shown below. The input is the directed graph from Exercise 1a.

We have created a script that can automatically test your program. To run this test you can execute the dryrun program that corresponds to this exercise. It expects to find a file named pageRank .c in the current directory. You can use dryrun as follows:

3.  (Warshall's algorithm)

Apply Warshall's algorithm to compute the transitive closure of your graph from exercise 1b. Choose vertices in alphabetical order. Show the reachability matrix:

after the initialisation

after the 1st iteration (vertex 'A') of the outermost loop

after the 6th iteration (vertex 'F') of the outermost loop

at the end.

Interpret the values in each of these matrices: Which connections between vertices do the different matrices encode?

4.  (Kruskal's algorithm)

a.  Show how Kruskal's algorithm would construct a minimum spanning tree for the following graph:

How many edges do you have to consider?

b.  For a graph G=(V,E), what is the least number of edges that might need to be considered by Kruskal's algorithm, and what is the most number of edges? Add one vertex and edge to the above graph to force Kruskal's algorithm to the worst case.

5.  (Prim's algorithm)

a.  Trace the execution of Prim's algorithm to compute a minimum spanning tree (MST) on the following graph:

Choose a random vertex to start with. Draw the resulting minimum spanning tree.

b.  Download the implementation of a Set ADT (Set.h, Set.c). The ADT can store a collection of distinct integer elements. Here is the interface for the ADT:

Next, download and complete the incomplete implementation prim.c of Prim's algorithm that uses the Set ADT and the Weighted Graph ADT from the lecture (WGraph.h, WGraph.c). The program:

prompts the user for the number of nodes in a graph,

builds a weighted, undirected graph from user input,

uses the Set ADT to compute a minimum spanning tree of the graph, starting with node 0 (needs to be implemented),

calculates and outputs the sume of the edge weights of the computed minimum spanning tree.

Hints:

Unlike the algorithm from the lecture, your program should not use an edge set (or a priority queue) to find the next edge. Your program should naively rely on the adjacent() function provided by

In determining the minimum weight edge to add to the MST you may find the INT_MAX macro from the limits .h library helpful . This provides the maximum value an int may take on a particular

system .

An example of the program executing is shown below for the graph