At this point you have several options for what to work on:
Recall that BFS is an algorithm that calculates the distance from a single start vertex $s$ to every other vertex.
Write a function BFS($G$ , $s$ ) which performs a BFS in $G$ starting at $s$. Assume that the vertices of $G$ are 0, 1, 2, ... It should return a list whose $i$th element is the distance from $s$ to $i$. You can use -1 or None (the Python equivalent of null in Java) to signify vertices whose distances have not been set.
For example, for $K_3$ BFS starting at vertex 0 should return [0, 1, 1], since vertex 0 is distance 0 from itself and distance 1 from vertices 1 and 2.
Use the CompleteGraph, Path, and RandomGraph functions from last time for testing. If you didn't finish that part of the lab, or if you're afraid you didn't do it correctly, I added those functions to graphs.py so you can use them. You can download the latest version here.
from graphs import *
def BFS(G, s):
n = G.numVertices()
dists = [-1 for i in range(n)]
# distance from s to itself is 0
dists[s] = 0
toVisit = [s]
for d in range(n):
##### YOUR CODE HERE #####
# For each vertex at distance d
# Mark all unmarked neighbors as distance d + 1
# Hint: G.neighbors(v) gives you a list of v's neighbors
return dists
###### Testing ######
n = 10
G = CompleteGraph(n) # Try changing this to Path, Cycle, and RandomGraph
startVertex = 0
L = BFS(G, startVertex)
print("Graph:")
print(G)
print("Start vertex: " + str(startVertex))
print("Vertex distances: " + str(L))
You can skip this exercise if you are using my updated graphs.py.
Write a function weightedCoin( $p$ ) which returns True with probability $p$, False with probability $1 - p$.
Hint: use the function random.rand(), which returns a random decimal between 0 and 1. The probability that it is between 0 and $p$ is $p$...
import random
def weightedCoin(p):
# Your code here
return False
#### Testing ####
p = .2
n = 100
# Flip n coins; keep track of number of heads
print("Flipping " + str(n) + " coins...")
numHeads = 0
for i in range(n):
if weightedCoin(p):
numHeads += 1
print("Proportion that came up heads: " + str(numHeads / n) + " (should be approx. " + str(p) + ")" )
Now modify your RandomGraph function from last time to add edges with probability $p$ instead of $1/2$. Again, be careful not to flip coins for both $uv$ and $vu$!
from graphs import *
def RandomGraph(n, p):
# Your code here
###### Testing ######
print(RandomGraph(10))
Write a function connectedComponent( $G, v$ ) which returns a list of vertices in the same connected component as $v$.
Hint: use BFS from Exercise 1.
from graphs import *
def connectedComponent(G, v):
CC = [v] # v is always in its own connected component
# Your code here
return CC
###### Testing ######
n = 10
G = RandomGraph(n, .2)
startVertex = 0
L = connectedComponent(G, startVertex)
print("Graph:")
print(G)
print("Start vertex: " + str(startVertex))
print("Connected component: " + str(L))
Now write a function connectedComponents( $G$ ) which returns all connected components of $G$. It should return a list of lists, with each inner list being one of the connected components.
Hint: use Exercise 3 to find the connected components one by one!
from graphs import *
def connectedComponents(G):
CCs = []
# Your code here
return CCs
######## Testing ########
n = 10
G = RandomGraph(n, .2)
L = connectedComponents(G)
print("Graph:")
print(G)
print("Connected components: " + str(L))
You can use a 2D list A to represent a matrix $A$ in Python, with A[i][j] corresponding to $a_{ij}$. Write a function mult( $A, B$ ) which multiplies $A$ and $B$ (using matrix multiplication) and returns the resulting matrix. You can assume that $A$ and $B$ are both $n \times n$, if that makes life easier.
def mult(A, B):
n = len(A)
# Start with an n x n matrix of 0s
AB = [[0 for j in range(n)] for i in range(n)]
for i in range(n):
for j in range(n):
# Calculate the correct value of AB[i][j]
return AB
###### Testing ######
def printMatrix(A):
"""Pretty print a matrix A"""
for row in A:
print(row)
print("")
A = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
B = [[1, -1, 1], [-1, 1, 1], [1, -1, 1]]
print("A = ")
printMatrix(A)
print("B = ")
printMatrix(B)
print("AB = ")
printMatrix(mult(A, B))
print("BA = ")
printMatrix(mult(B, A))
Definition. Let $G$ be a graph on $n$ vertices. The adjacency matrix of $G$ is an $n \times n$ matrix $A$ such that $a_{ij}$ is the number of edges from vertex $i$ to vertex $j$
Draw the graph represented below and then write down its adjacency matrix.
print(RandomGraph(10, .25))
Now write a function that returns the adjacency matrix of a graph $G$. Since our Graph class does not allow multiple edges, all entries will be 0 or 1.
from graphs import *
def adjacencyMatrix(G):
n = G.numVertices()
A = [[0 for j in range(n)] for i in range(n)]
# Your code here
return A
###### Testing ######
G = CompleteGraph(10) # Try with Path, Cycle, RandomGraph, etc.
print("Graph:")
print(G)
print("Adjacency matrix:")
printMatrix(adjacencyMatrix(G))