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

Depth First Search

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

Breadth First Search

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

- 3.
- 4.
- 5.
- 1.Hint: What additional data structures might be helpful for us to solve this problem?
- 2.
- 3.

Part 5

- 3.
- 1.Hint: Would recursion be helpful?
- 2.
- 3.

Further Reading

- 3.
- 4.
- 6.
- 7.BFS vs DFS
- 2.https://www.youtube.com/watch?v=TIbUeeksXcI

- 8.Free Code Camp - Graphs in JavaScript

Last modified 1mo ago