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.
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
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.