ES242. Data Structures and Algorithms I. Week 06 Lab

ES242. Data Structures and Algorithms I.

Lab 06

Breadth First Search

Problem 1. Implement BFS

In this exercise your goal is to output a BFS traversal of a given graph G starting from a given source s.

Input Format

The first line of input is three space-separated integers n, m and s, denoting the number of vertices and edges of G, and the id of the source vertex, respectively. Vertices are indexed from 0 to n-1.

The next m lines of code are two space separated integers u and v in the range 0 and n-1, indicating an (undirected) edge between vertices u and v.

The last line is a pair of space-separated integers x and y.

Output Format

The output is formatted as follows: if the BFS lasts for t rounds, there are t lines of output. The i-th line consists of a space-separated list of the vertices visited by BFS in the i-th round of the traversal in increasing order of labels.

Sample I/O

Sample Input

Sample Output

0
1 2 3 4
5

Note. This was a worked out example and the code is here. Please note that there some very minor changes from the version discussed in class to account for proper printing of whitespace in the output.

Problem 2. Unique Servers

Networking company Dagm is reponsible for extending internet services to town Xelo with n devices. To deploy such services, and guarantee their connection to the internet, Dagm has set up x services in its head office.

You are given a matrix same_server[n][n] which denotes if two devices are always connected to the same server. It implies, same_serve[i][j]=1 if device i and j are facilitated by the same server. Else, it is 0.

Your task is compute the number x. That is, the number of unique servers set up by Dagm.

You are asked to complete the count_unique_servers() function in line 8

Consider the illustration below:

Here, number of unique servers is 2 (S1 and S2).

Input Format

The first line contains an integer n, the number of devices in the city. The next n input line contains n space separated integers (0 or 1).

Output Format

Output a single number representing the answer.

Sample Input 1

7
1 1 1 0 1 0 0
1 1 1 0 1 0 0
1 1 1 0 1 0 0
0 0 0 1 0 1 1
1 1 1 0 1 0 0
0 0 0 1 0 1 1
0 0 0 1 0 1 1

Sample Output 1

Sample Input 2

10 
1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1

Sample Output 2

List of Practice Problems

Wonderland Chase This Google Code Jam Finals problem from 2022 has a small test case that can be solved by brute force but you’d need to apply BFS to solve the advanced test set.
Blizzard Basin This Day 24 AoC question from 2022 involves a constantly changing graph. Can you make your way out? Give it a shot!