Depth-first search

Depth-first search (DFS) is an algorithm for traversing through the graph. The algorithm starts at the root node and explores each neighboring node as far as possible. The moment it reaches a dead-end, it backtracks until it finds a new, undiscovered node, then traverses from that node to find more undiscovered nodes. In that way, the algorithm visits each node in the graph.

Graph

Let's say you have a graph in the graph.txt file:

go a
go b
go c
a d
a e
a b
b f
b c
c g
d h
d e
e f
f i
g f
h i

Python code

Then you can read the graph, calculate shortest paths with depth-first search algorithm and draw the results:

import networkx as nx
import matplotlib.pyplot as plt


with open("graph.txt") as f:
    lines = f.readlines()

edgeList = [line.strip().split() for line in lines]

g = nx.Graph()
g.add_edges_from(edgeList)

pos = nx.planar_layout(g)

nx.draw(g, pos, with_labels=True, node_color="#f86e00")

dfs = nx.dfs_tree(g, source="go")

nx.draw(dfs, pos, with_labels=True, node_color="#f86e00", edge_color="#dd2222")

plt.show()

Output

Where to next?

There are many graph algorithms libraries out there, with their own implementations of depth-first search algorithm. NetworkX's algorithms are written in Python, and there are many other libraries that offer faster C++ implementations, such as MAGE, a graph algorithms library developed by Memgraph team.

Memgraph for NetworkX developers