Bootcamp
Searchโฆ
A.5.7: Graphs

# Introduction

Graphs are a more generalised version of trees that can have "edges" that point in forward, backward, and both directions. All trees are graphs but not all graphs are trees.

## Representing a Graph

As described in the video above, there are many ways to represent a graph. We will be using an adjacency list to represent our graphs.
graph = {
'a' : ['b','c'],
'b' : ['d'],
'c' : ['e'],
'd' : ['f'],
'e' : [],
'f' : []
}

# Traversal Algorithms

For visiting every node in a graph. This code looks a little bit different from our tree DFS code.
graph = {
'a' : ['b','c'],
'b' : ['d'],
'c' : ['e'],
'd' : ['f'],
'e' : [],
'f' : []
}
โ
visited = {}
โ
def dfs(at):
if at in visited: return
โ
visited[at] = True
print(f'at: {at}')
โ
neighbors = graph[at]
โ
for next_node in neighbors:
dfs(next_node)
โ
dfs('a')
For visiting every node in a graph. This one visits each node in order of distance. This is equivalent to the level-order tree traversal algorithm we've seen.
graph = {
'a' : ['b','c'],
'b' : ['d'],
'c' : ['e'],
'd' : ['f'],
'e' : [],
'f' : []
}
visited = {} # Dict to track visited nodes
queue = []
โ
def bfs(visited, graph, node):
visited[node] = True
queue.append(node)
โ
while queue:
s = queue.pop(0)
print (s, end = " ")
โ
for neighbour in graph[s]:
if neighbour not in visited:
visited[neighbour] = True
queue.append(neighbour)
โ
bfs(visited, graph, 'a')

# Exercises

## Part 1

Implement a function that DFS searches a graph for a value and returns a boolean.
Implement a function that BFS searches a graph for a value and returns a boolean.

## Part 2

Implement path finding DFS that prints out a path in the graph from 'a' to 'e'.
graph = {
'a' : ['b','c'],
'b' : ['d'],
'c' : ['e'],
'd' : ['f'],
'e' : [],
'f' : []
}

## Part 3

Implement shortest path BFS that prints out or returns the shortest path in the graph from 'a' to 'e':
graph = {
'a' : ['b','c'],
'b' : ['d'],
'c' : ['e'],
'd' : ['f'],
'e' : [],
'f' : []
}

## Part 4

1. 3.
2. 4.
3. 5.
1. 1.
Hint: What additional data structures might be helpful for us to solve this problem?
2. 2.
Rocket solution code: https://pastebin.com/3N4NUz8Gโ
3. 3.
Rocket solution video: https://youtu.be/1xDBSlnUiUE?t=1308โ

## Part 5

1. 3.
1. 1.
2. 2.
Rocket solution code: https://pastebin.com/AtwkRjBfโ
3. 3.

1. 3.
โIntro to Graphsโ
2. 4.
โGraph Representationโ
3. 6.
โDFSโ
4. 7.
BFS vs DFS
1. 2.