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 ={}
โ
defdfs(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 =[]
โ
defbfs(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 notin 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':