Implementing graph with python and how to traverse.

Implementing graph with python and how to traverse.
5 (100%) 6 votes

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.

Implementing graph with python

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.

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.

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.


Gaurav Yadav

Gaurav is cloud infrastructure engineer and a full stack web developer and blogger. Sportsperson by heart and loves football. Scale is something he loves to work for and always keen to learn new tech. Experienced with CI/CD, distributed cloud infrastructure, build systems and lot of SRE Stuff.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.