Depth First Search In Python to print nodes of Graph

Untitled document (1)
Graph

Graph

Shown above is a simple graph. Let’s define the characteristic of the graph:

  • This is a connected graph. Meaning, you can travel from anywhere to anywhere in this graph.  Read further here
  • This is an undirected graph. That simply means we don’t have any direction sense to the arrow connecting two nodes
  • This is an unweighted graph which is a different way of saying all the edges carry equal weight

Adjacency List

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph. Read the wiki page here.

Our graph is now being represented in python dictionary using set

Print Nodes of Graph

We will now transverse the graph in depth-first fashion and try to print all the elements of the graph. Let’s say we start from A, we explore all the immediate neighbors before backtracking and then turn back when there is no further nodes.

 


Further Reading

MIT Video Lecture

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog at WordPress.com.

Up ↑

%d bloggers like this: