Python Data Structures: Graph Algorithms

Graphs are extremely useful data structures for solving many important mathematical problems. For example, they can be used to analyze the topology of computer networks or the molecular structure of chemical compounds. They are also used in urban transportation, route planning, and even in human languages and their grammar. All of these applications share the challenge of traversing the graph using its edges and ensuring that all nodes are visited. There are two common and established methods for performing this traversal, which are described below.

Depth-First Traversal

This algorithm, also known as depth-first search (DFS), traverses the graph in a depth-first scan. When a dead end is reached during any iteration, a stack is used to remember the next vertex to start the search. We use collection data types to implement graph DFS in Python because they provide the necessary functionality to track visited and unvisited nodes.

Example

class graph:
   def __init__(self,gdict=None):
      if gdict is None:
         gdict = {}
      self.gdict = gdict
# Check for the visisted and unvisited nodes
def dfs(graph, start, visited = None):
   if visited is None:
      visited = set()
   visited.add(start)
   print(start)
   for next in graph[start] - visited:
      dfs(graph, next, visited)
   return visited

gdict = {
   "a" : set(["b","c"]),
   "b" : set(["a", "d"]),
   "c" : set(["a", "d"]),
   "d" : set(["e"]),
   "e" : set(["a"])
}
dfs(gdict, 'a')

Output

When the above code is executed, it produces the following output –

a
b
d
e
c

Breadth-First Traversal

Also known as breadth-first search (BFS), this algorithm traverses a graph in units of breadth. When a dead end is reached during any iteration, a queue is used to remember the next vertex to start the search. Please visit this link on our website for details on the steps of graph BFS.

We use the queue data structure discussed earlier to implement graph BFS in Python. As we continue to visit adjacent unvisited nodes, we continue to add them to the queue. We then begin to queue only nodes that have no unvisited nodes. When there are no next adjacent nodes to visit, we stop the program.

Example

import collections
class graph:
   def __init__(self,gdict=None):
      if gdict is None:
         gdict = {}
      self.gdict = gdict
def bfs(graph, startnode):
# Track the visited and unvisited nodes using queue
   seen, queue = set([startnode]), collections.deque([startnode])
   while queue:
      vertex = queue.popleft()
      marked(vertex)
      for node in graph[vertex]:
         if node not in seen:
            seen.add(node)
            queue.append(node)

def marked(n):
   print(n)

# The graph dictionary
gdict = {
   "a" : set(["b","c"]),
   "b" : set(["a", "d"]),
   "c" : set(["a", "d"]),
"d" : set(["e"]),
"e" : set(["a"])
}
bfs(gdict, "a")

Output

When the above code is executed, it produces the following output –

a
c
b
d
e