2.7 KiB
Outline
We'll continue to go over breadth-first search and depth-first search.
To start, please implement the breadth-first search algorithm from last week. Then, if time permits, I'd like you to work through these exercises.
Exercise 1
Consider a graph that is used to represent people connections.
Bob --------- Dave ---- Frank ------- Heidi
/ | |
/ | |
Alice -----+ +------- Eve ---+ |
\ / \ |
\ / \ |
+------ Carol Grace ------- Ivan
\ /
\ /
+-- Mallory ---+
We say that person A has an "Nth-degree connection" to another person B, if person B is reachable from person A by traversing at minimum N edges.
Write an algorithm to return that person's Nth-degree connections, in a list of lists sorted by N. 1st-degree connections should appear in the first inner list, with 2nd-degree connections in the second inner list, and so forth.
Your algorithm should take a starting person and a maximum N, such that your algorithm does not return connections past the maximum Nth connection.
Example: nth_degree_connections(Mallory, 2) would return the following lists
in a list:
[Carol, Grace]: 1st-degree connections[Eve, Ivan, Alice]: 2nd-degree connections
It would not return anything else because of the maximum N specified.
Consider the following:
- Which algorithm does this use?
- How do we know when to stop at the maximum N?
Exercise 2
In a weighted road network, return all possible paths that a car can take to reach point A to point B. For each path, also sum up the total weight that taking that path requires.
Your algorithm should take the starting and ending points, and return a list of tuples. Each tuple should contain the traversal from point A to point B, followed by the total weight.
In this fictitious graph, calling possible_paths("Santa Ana", "San Francisco")
should yield the return below.
graph = {
'Santa Ana': {
'Los Angeles': 5,
'Palm Springs': 50
},
'Los Angeles': {
'San Francisco': 25,
'Santa Ana': 5
},
'Palm Springs': {
'San Francisco': 30,
'Santa Ana': 50
},
'San Francisco': {
'Los Angeles': 25,
'Palm Springs': 30
}
}
[
(
["Santa Ana", "Los Angeles", "San Francisco"],
30
),
(
["Santa Ana", "Palm Springs", "San Francisco"],
80
)
]