Implementing graph with python and how to traverse.

When we talk about algorithms, graphs are one of the most important parts to know about. In this session, we will talk about graphs and implementing graph in python.

What is a graph?

A graph is a data structure consists of nodes and edges. It is nonlinear and can form very complex structures. If you want to visualize it, think about electric wiring in your house. Each node is a socket and edges are the wires that run between them. The graph looks something like below.

Traversal of graph

In this, we will also talk about the traversal of the graph. There are mainly two types of graph traversal and those are

BFS: Breadth-First Search and DFS: Depth-first search. In BFS we first traverse the nearest nodes and then go deeper. In DFS we first go in-depth of each branch instead of going to each branch first. We will talk about DFS and BFS in the coming posts.

Breadth-first search in a graph with python

Implementing Graph with python

class Node:
        def __init__(self, data):
                self.data = data
                self.edge = []

        def add_edge(self,edge):
                self.edge.append(edge)

        def traverse(self):
                traversed = []
                queue = []
                for ed in self.edge:
                    queue.append(ed)
                while len(queue) != 0:
                        vertex = queue.pop()
                        if vertex not in traversed:
                            print(vertex.data)
                            traversed.append(vertex)
                            for ed in vertex.edge:
                                    queue.append(ed)



graphroot = Node(3)

# Lets add a new vertex

vert = Node(4)

# Lets connect the vertex.

vert.add_edge(graphroot)
graphroot.add_edge(vert)

# adding more vertices

vert2=Node(6)
vert2.add_edge(graphroot)

graphroot.add_edge(vert)

vert3= Node(5)
vert2.add_edge(vert)
vert.add_edge(vert2)

vert3.add_edge(vert2)
vert2.add_edge(vert3)

graphroot.traverse()

#output
#4
#6
#5
#3

Code walkthrough

For implementing graph in python, we have first created a class Node which has two attributes data that keeps node data and then edge which keeps the list of edges you can visit from this node.

Now it has a function to add_edge which can be used to associate this node with other nodes.

Level order traversal of a binary tree in python.

The next function is traverse, what this function is doing is taking the edges and putting in the queues, taking out the last element of the queue and then print its data after that it adds all the edges in this to the queue. There is a check for traversed nodes to avoid cycles. There are two data structures traversed and a queue that is being used. Note that this queue is last in First out so you can call it to stack.

You can read about binary tree in python here.

If you like the article please share and subscribe. Follow us on facebook and install our android application.

---