94 lines
2.7 KiB
Markdown
94 lines
2.7 KiB
Markdown
## 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.
|
|
|
|
```python
|
|
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
|
|
)
|
|
]
|
|
```
|