Skip to main content

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.

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

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

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.