A Comprehensive Guide to Graph Search in Python- Part 1

Introduction to graph data structure and depth first search (DFS)

What is a graph data structure:

A Graph is a data structure consisting of finite number of nodes (or vertices) and edges that connect them. Consider the picture below:

(Image Source)

The numbered circles are nodes with the lines connecting them being the edges. A pair (0,1) represents an edge that connects the nodes or vertices 0 and 1.

Graphs are used to represent and solve many real life problems. For example, they can represent any network which could be social media like Facebook, LinkedIn etc. or Google maps.

What is graph search:

In graph search, we traverse or search the graph data structure from node to node. The easiest to understand example would be that of navigation maps like Google Maps. Consider all the towns are representing by nodes with the edges being the roads. To find the best route from town A to town B, we have to take several routes from the town A to B and then find the best one, this is graph search. Graph search is widely implemented these days and a good example is Facebook’s social network for suggesting friends.

Depth-First Search:

Depth-first search goes in one direction, from one node to its neighboring node, until it has reached the end in that direction before trying any other direction. In other words, while looking for the target node, it will go in a certain direction node to node, if it finds the target node, search ends but if it reaches the end in that direction and does not find the target node, it will repeat the same process in another direction. Therefore, it will go as deep as possible in one direction and ignore all other directions.

Pros and cons:

DFS can be the fastest but at the same time can be very slow. If it lucks out and chooses a path which will end up in the target node or goal state, it will be the fastest however at the same time, if it is going in a path where the target node is the last one, it may take an exceptionally long time.

Similarly, if there are multiple solutions or multiple paths to the target node, it may pick the less optimum one and thus may fail to pick the best solution.

Coding DFS:

Consider the graph structure below:

(Image Source)

This can be represented in python as follow:

graph = {
‘A’ : [‘B’,’C’],
‘B’ : [‘D’, ‘E’],
‘C’ : [‘F’],
‘D’ : [],
‘E’ : [‘F’],
‘F’ : []
}

To keep track of all the nodes we have a set “visited”

visited = set()

Now we write a recursive function that implements DFS to search through the nodes. It takes the starting node, the visited set and the graph. Output could be whatever you may require but for demonstration, we want it to print the node being processed, thus printing the path it takes node by node.

def dfs(visited, graph, node):
    if node not in visited:
        visited.add(node)
        print(node)
        for neighbor in graph[node]:
            dfs(visited, graph, neighbor)

Let’s run this starting with the node ‘A’:

dfs(visited, graph, ‘A’)

Output:

A
B
D
E
F
C

So our function started with the node A, went to B and then from B to D, it then reached the end of that branch to it went to E, which lead it to F, reaching another end, the only node then left was C which was then next.

So as you can see, it searched through one branch all the way to the end before looking into the next branch.

In part 2, we will talk about breadth-first search.

References:

1. Graph Data Structure and Algorithms

2. Understanding the Depth-First Search and the Topological Sort with Python