# Computer Science 220S2C Python Programming

```Computer Science 220S2C (2018)
Assignment 3 (Graph Algorithms)
```

## Task 1: Minimum Spanning Trees

For this warm-up task you are to implement any eļ¬cient minimum spanning tree algorithm that takes a sequence of edge-weighted graphs and outputs the minimum cost weight of a spanning tree of each.

### Input Format

For this assignment we use adjacency matrices with positive integer weights. Here a zero entry at row i and column j indicates that no edge ij exists in the graph. The ļ¬rst line consists of an integer n ≤ 1000 denoting the order of the graph. This is then followed by n lines of n white-space separated integers denoting edge weights. The sequence of graphs is terminated by a value n = 0, which is not processed.

```
3
0 1 3
1 0 2
3 2 0
4
0 2 7 0
2 0 5 1
7 5 0 3
0 1 3 0
6
0 1 0 4 0 0
1 0 3 0 3 0
0 3 0 0 0 2
4 0 0 0 2 0
0 3 0 2 0 1
0 0 2 0 1 0
0```

### Output Format

Output should be one line for each input graph indicating the minimum cost weighted tree. The sample output for the previous input cases is as follows.

3
6
9

## Task 2: A Paths Optimization Problem for Weighted Trees

### Input Format

Input for this problem consists of a sequence of one or more scenarios, taken from the keyboard/stdin. Each scenario contains two or more lines. • The ļ¬rst line contains an integer n, 1 ≤ n ≤ 500000, indicating the number of intersections, including the entrance intersection, implicitly labelled 0. • This is then followed by one or more lines, containing n−1 pairs of integers. All integers are separated by single spaces or newlines. The y-th intersection is deļ¬ned by the y-th pair of integers ‘x p’, where 1 ≤ y < n, 0 ≤ x < y, −1000 ≤ p ≤ 1000. This pair indicates that a road is added between y and a previously deļ¬ned intersection, x, with a green book proļ¬t value given by p.

The input will be terminated by a line consisting of one zero (0). This line should not be processed. Some sample input scenarios follows.

```5
0 -1 1 3 0 2 1 2
5
0 1 1 -3 0 -2 1 -2
5
0 -1 1 -3 0 -2 1 -2
10
0 -1 0 -1 0 0 1 3 1 4 2 4 2 2 3
3 3 3
0
```

### Output Format

Output will be a sequence of lines, one for each input scenario. Each line will contain an integer, indicating the maximum non-negative proļ¬t sum, over all possible simple road chains connecting two intersections of the subdivision. Write zero (0) if no proļ¬t can be obtained. The output for the previous sample input follows.

5
1
0
7

## Task 3: Snakes in a Graph

For a graph G = (V,E), a snake (also called an induced path) is a path v1,v2,...,vk such that for all j−i > 1 (vi,vj) 6∈ E. That is, it is a sequence of vertices in G such that each two adjacent vertices in the sequence are connected by an edge in G, and each two nonadjacent vertices in the sequence are not connected by any edge in G.

For this task, our goal is to determine the largest snake of a graph.

### Input Format

Input for this problem consist of a sequence of one or more (undirected) graphs taken from the keyboard. Each graph is represented by an adjacency list. The ļ¬rst line is an integer n indicating the order of the graph. This is followed by n white space separated lists of adjacencies for nodes labeled 0 to n − 1. The input will be terminated by a line consisting of one zero (0). This line should not be processed. Two sample input graphs are listed below. The easy (harder) test cases are graphs of order at most 10 (50).

```4
1
0 3

1
5
1 4
0 2
1 3 4
2 4
0 2 3
0
```

### Output Format

Output will be just one integer per line sent to the console (e.g. System.out). For the above, input we would output the following two integers denoting the longest snake of the two graphs. Recall that the length of a path is the number of edges.

2
3

Assignment Help Features
Assignment Help Services
• Assignment Help
• Homework Help
• Writing Help