Introduction
Depth-First Search (DFS) and Breadth-First Search (BFS) are very well know algorithms if you studied computer science, but for some self-taught people this algorithms are not so well known.
Graph theory helps you to solve several problems and having this two algorithms in mind could save your interview. Actually some big companies will ask you to solve problems that use this DFS or BFS.
We are going to show you how to remember DFS and BFS algorithms very easily. All examples will be made with Python.
To understand what this algorithms does, you need to know what a graph is.
Graph representation
Graph can be represented with a matrix or with a dictionary with list. When using matrix representation the position i,j of the matrix contains information of adjacency. if graph[i, j] is equal to one it means that vertex i is connected with vertex j. With adjacency list you will have a dictionary with a list of connections for each vertex. If you access to graph[i] it will return a list of the connected vertex.
The algorithms
DFS algorithm will be iterate the vertices with a Frst in first out (FIFO) queue, in that way it will go as deep as possible. On the other side BFS will consume vertices Last on first out (LIFO) To avoid revisit vertices of the graph we will use a visited set.
def dfs(graph, start):
visited = set()
to_visit = [start]
while to_visit:
vertex = to_visit.pop() # here we are usinf FIFO
if vertex not in visited:
visited.add(vertex)
stack.extend(graph[verted] - visited)
A BFS code is almost equal, it only change the line were we pop elements from to_visit.
def dfs(graph, start):
visited = set()
to_visit = [start]
while to_visit:
vertex = to_visit.pop(0) # here we are usinf LIFO
if vertex not in visited:
visited.add(vertex)
stack.extend(graph[verted] - visited)
To test your self, write functions usinf BFS or DFS that solved the following problems:
- The connected component of a vertex
- All possible paths that start from a vertex
- Shortest path from vertex A to B
