Part 1 (Graph)

(Only Part 1 is mandatory and graded.)

Q 1. Consider a social network of n people.  Each person is given a distinct id ranging from 0 to n − 1. Among these people, k  (k  ≥ 1) of them are infected with a mysterious virus.  If two persons have close contact with each other, the virus can be transmitted from one person to the other. The virus will spread through the network until there are no more people left to infect.

In this network, a“graph”, implemented using adjacency matrix, is used to represent the connection between people. Specifically, graph[i][j] = 1 if and only if persons i and j have close contact with each other; Otherwise, graph[i][j] = 0. The network is an undirected graph which means graph[i][j] = graph[j][i].

Write programs to solve the following problems:

(a)  [30%] Write a program that, given a graph and a list initial, returns the total number of infected people

including the people in the initial list.  The list initial stores the id’s of the people who were initially infected. Here are some examples:

• Example 1:

The index of upper-left cell is cell (0, 0) and the index of bottom-right cell is cell (n − 1,n − 1)

Input: graph=[[0,0,0,0,0],[0,0,0,0,0],[0,0,0,1,0],[0,0,1,0,1],[0,0,0,1,0]]

initial=[0,1]

Output: 2

• Example 2:

The index of the upper-left cell is cell (0, 0) and the index of the bottom-right cell is cell (n−1,n−1)

Input: graph=[[0,1,1,0,0],[1,0,1,1,0],[1,1,0,0,0],[0,1,0,0,1],[0,0,0,1,0]]

initial=[0,1]

Output: 5

• Example 3:

The index of upper-left cell is cell (0, 0) and the index of bottom-right cell is cell (n − 1,n − 1)

Input: graph=[[0,0,1,0,0],[0,0,0,1,0],[1,0,0,1,0],[0,1,1,0,0],[0,0,0,0,0]]

initial=[0,1]

Output: 4

• Example 4:

The index of upper-left cell is cell (0, 0) and the index of bottom-right cell is cell (n − 1,n − 1)

Input: graph=[[0,0,1,0,0],[0,0,0,1,1],[1,0,0,1,0],[0,1,1,0,1],[0,1,0,1,0]]

initial=[0,1]

Output: 5

(b)  [70%] If we select one person in the list initial and put him/her in quarantine, that person will not

spread the virus.  Which person should be quarantined to minimize the number of final infections? Write a program that, given a graph and an initial list, returns the id of the person that should be selected for quarantine. If more than one person satisfies the condition, return the one with the smallest id. Some examples:

• Example 1:

The index of upper-left cell is cell (0, 0) and the index of bottom-right cell is cell (n − 1,n − 1)

Input: graph=[[0,0,0,0,0],[0,0,0,0,0],[0,0,0,1,0],[0,0,1,0,1],[0,0,0,1,0]]

initial=[0,1]

Output: 0

Example 2:

The index of upper-left cell is cell (0, 0) and the index of bottom-right cell is cell (n − 1,n − 1)

Input: graph=[[0,1,1,0,0],[1,0,1,1,0],[1,1,0,0,0],[0,1,0,0,1],[0,0,0,1,0]]

initial=[0,1]

Output: 1

Example 3:

The index of upper-left cell is cell (0, 0) and the index of bottom-right cell is cell (n − 1,n − 1)

Input: graph=[[0,0,1,0,0],[0,0,0,1,0],[1,0,0,1,0],[0,1,1,0,0],[0,0,0,0,0]]

initial=[0,1]

Output: 0

• Example 4:

The index of upper-left cell is cell (0, 0) and the index of bottom-right cell is cell (n − 1,n − 1)