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.

Introduction to Graphs & Graph Problems

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')

Graph Problems

DFS Path Finding (maze)

BFS Shortest Path

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. 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

Further Reading