What is the postorder tree traversal algorithm?

Postorder traversal algorithm is a depth first traversal algorithm. Here, we start from a root node and traverse a branch of the tree until we reach the end of the branch. After that, we move to the next branch. This process continues until all the nodes in the tree are printed. 

The postorder tree traversal algorithm gets its name from the order in which the nodes of a tree are printed. In this algorithm, we first print the left sub-tree of the node, then we print the right sub-tree of the current node. At last, we print the current node. This process is recursive in nature. Here, the node is only printed when all the nodes in the left sub-tree and the right sub-tree of the current node have already been printed.  

Let us understand the process using the binary tree given in the following image.

Let us print all of the nodes in the above binary tree using the postorder traversal algorithm.

• We will start from the node 50. Before printing 50, we have to print its left sub-tree and right sub-tree. So, we will move to 20.
• Before printing 20, we have to print its left sub-tree and right sub-tree. So, we will move to 11.
• As 11 has no children, we will print 11. After that we will move to the previous node i.e. 20.
• As the left child of 20 has already been printed, we will move to the right sub-tree of 20 i.e. 22.
• As 22 has no children, we will print 22. After that we will move to the previous node i.e. 20.
• As both the left sub-tree and the right sub-tree of 20 have already been printed. We will print 20 and will move to its parent node i.e. 50.
• At this point, Left sub-tree of 50 has already been printed.So, will print its right sub-tree. We will move to 53.
• Before printing 53, we have to print its left sub-tree and right sub-tree. So, we will move to 52.
• As 52 has no children, we will print 52. After that we will move to the previous node i.e. 53.
• As the left child of 53 has already been printed, we will move to the right sub-tree of 53 i.e. 78.
• As 78 has no children, we will print 78. After that we will move to the previous node i.e. 53.
• As both the left sub-tree and the right sub-tree of 53 have already been printed, We will print 53 and will move to its parent node i.e. 50.
• At this point,  both the left sub-tree and the right sub-tree of 50 have already been printed, So, we will print 50.
• As all the nodes in the tree have already been printed, we will terminate this algorithm.

You can observe that we have printed the values in the order 11, 22, 20,52, 78, 53, 50. Let us now formulate an algorithm for the postorder tree traversal algorithm.

Algorithm for postorder tree traversal

As you have an overview of the entire process, we can formulate the algorithm for postorder tree traversal as follows.

1. Start from the root node.
2. If the root is empty, return.
3. Traverse the left sub-tree recursively.
4. Traverse the right sub-tree recursively.
5. Print the root node.
6. Stop.

Implementation of postorder tree traversal in Python

 As we have understood the algorithm for postorder tree traversal and its working, Let us implement the algorithm and execute it for the binary tree given in the above image.

class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None


def postorder(root):
    # if root is None,return
    if root is None:
        return
    # traverse left subtree
    postorder(root.leftChild)

    # traverse right subtree
    postorder(root.rightChild)
    # print the current node
    print(root.data, end=" ,")


def insert(root, newValue):
    # if binary search tree is empty, create a new node and declare it as root
    if root is None:
        root = BinaryTreeNode(newValue)
        return root
    # if newValue is less than value of data in root, add it to left subtree and proceed recursively
    if newValue < root.data:
        root.leftChild = insert(root.leftChild, newValue)
    else:
        # if newValue is greater than value of data in root, add it to right subtree and proceed recursively
        root.rightChild = insert(root.rightChild, newValue)
    return root


root = insert(None, 50)
insert(root, 20)
insert(root, 53)
insert(root, 11)
insert(root, 22)
insert(root, 52)
insert(root, 78)
print("Postorder traversal of the binary tree is:")
postorder(root)

Output:

Postorder traversal of the binary tree is:
11 ,22 ,20 ,52 ,78 ,53 ,50 ,

Conclusion

In this article, we have discussed and implemented the postorder tree traversal algorithm. To learn more about other tree traversal algorithms, you can read this article on Inorder tree traversal algorithm or level order tree traversal algorithm in python.

The post Postorder Tree Traversal Algorithm in Python appeared first on PythonForBeginners.com.

What is the Preorder tree traversal ?

Preorder tree traversal is a depth first traversal algorithm. Here, we start from a root node and traverse a branch of the tree until we reach the end of the branch. After that, we move to the next branch. This process continues until all the nodes in the tree are printed. 

The preorder tree traversal algorithm gets its name from the order in which the nodes of a tree are printed. In this algorithm, we first print a node. After that, we print the left child of the node. And, at last, we print the right child of the node. This process is recursive in nature. Here, the right child of a node is only printed when all the nodes in the left subtree of the current node and the current node itself have already been printed.  

Let us understand the process using the binary tree given in the following image.

Let us print all of the nodes in the above binary tree using the preorder traversal.

• First, we will start from the root node and print its value i.e. 50.
• After that we have to print the left child of 50. So, we will print 20. 
• After printing 20, we have to print the left child of 20. So, we will print 11.
• 11 has no children. So, we will move to node 20 and print its right child i.e. we will print 22.
• 22 has no children so, we will move to 20. Again all of the children of 20 have been printed. So, we will move to 50. At 50, we will print its right child as all the nodes in its left subtree have already been printed. Hence, we will print 53.
• After printing 53, we have to print the left child of 53. So, we will print 52.
• 52 has no children. So, we will move to node 53 and print its right child i.e. we will print 78.
• At this point, we have printed all of the nodes in the binary tree. So, we will terminate the process.

You can observe that we have printed the values in the order 50, 20, 11,22, 53, 52, 78. Let us now formulate an algorithm for the preorder tree traversal .

Algorithm for preorder tree traversal

As you have an overview of the entire process, we can formulate the algorithm for preorder tree traversal as follows.

1. Start from the root node.
2. If the root is empty, goto 6.
3. Print the root node.
4. Traverse the left subtree recursively.
5. Traverse the right subtree recursively.
6. Stop.

Implementation of preorder tree traversal in Python

 As we have discussed the algorithm for preorder tree traversal and its working, Let us implement the algorithm and execute it for the binary tree given in the above image.

class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None


def preorder(root):
    # if root is None,return
    if root is None:
        return
    # print the current node
    print(root.data, end=" ,")
    # traverse left subtree
    preorder(root.leftChild)

    # traverse right subtree
    preorder(root.rightChild)


def insert(root, newValue):
    # if binary search tree is empty, create a new node and declare it as root
    if root is None:
        root = BinaryTreeNode(newValue)
        return root
    # if newValue is less than value of data in root, add it to left subtree and proceed recursively
    if newValue < root.data:
        root.leftChild = insert(root.leftChild, newValue)
    else:
        # if newValue is greater than value of data in root, add it to right subtree and proceed recursively
        root.rightChild = insert(root.rightChild, newValue)
    return root


root = insert(None, 50)
insert(root, 20)
insert(root, 53)
insert(root, 11)
insert(root, 22)
insert(root, 52)
insert(root, 78)
print("Preorder traversal of the binary tree is:")
preorder(root)

Output:

Preorder traversal of the binary tree is:
50 ,20 ,11 ,22 ,53 ,52 ,78 ,

You can observe that the code gives the same output that we have derived while discussing this algorithm.

Conclusion

In this article, we have discussed and implemented the preorder tree traversal algorithm in Python. To learn more about other tree traversal algorithms, you can read this article on In order tree traversal in Python and Level order tree traversal in python.

The post Preorder Tree Traversal Algorithm in Python appeared first on PythonForBeginners.com.

How to calculate the Shortest Path Length from a Vertex to other vertices?

In an unweighted graph, all the edges have equal weight. It means that we just have to count the number of edges between each vertex to calculate the shortest path length between them. 

For example, consider the following graph.

Let us calculate the shortest distance between each vertex in the above graph.

There is only one edge E₂ between vertex A and vertex B. So, the shortest path length between them is 1. 

We can reach C from A in two ways. The first one is using the edges E₄-> E₅->E₆ and the second path is using the edges E₂-> E₆. Here, we will choose the shortest path, i.e. E₂-> E₆. Hence the shortest path length between vertex A and vertex C is 2.

There is only one edge E₁ between vertex A and vertex D. So, the shortest path length between them is 1. 

There is only one edge E₃ between vertex A and vertex E. So, the shortest path length between them is 1. 

We can reach F from A in two ways. The first one is using the edges E₂-> E₅ and the second path is using the edges E₄. Here, we will choose the shortest path, i.e. E₄. Hence the shortest path length between vertex A and vertex F is 1.

Algorithm to calculate the Shortest Path Length from a Vertex to other vertices

By now, you must have understood that we have to count the number of edges between the vertices to calculate the distance between the vertices. For this, we will modify the  breadth first search algorithm as follows.

• We will declare a python dictionary that will contain the vertices as their keys and distance from the source vertex as the associated values. 
• Initially, we will assign the distance of each vertex from the source as infinite , denoted by a large number. Whenever we will find a vertex during traversal, we will calculate the current distance of the vertex from the source. If the current distance appears to be less than the distance mentioned in the dictionary containing the distance between source and other vertices, we will update the distance in the dictionary. 
• After full breadth first traversal, we will have the dictionary containing the least distance from the source to each vertex. 

We can formulate the algorithm for calculating the shortest path length between vertices of an unweighted graph as follows.

1. Create an empty Queue Q. 
2. Create a list visited_vertices to keep track of visited vertices.
3. Create a dictionary distance_dict to keep track of distance of vertices from the source vertex. Initialize the distances to 99999999. 
4. Insert source vertex into Q and visited_vertices.
5. If Q is empty, return. Else goto 6.
6. Take out a vertex v from Q.
7. Update the distances of unvisited neighbors of v in distance_dict. 
8. Insert the unvisited neighbors to  Q and visited_vertices.
9. Go to 5.

Implementation

As we have discussed the example and formulated an algorithm to find the shortest path length between source vertex and other vertices in a graph, let us implement the algorithm in python.

from queue import Queue

graph = {'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
print("Given Graph is:")
print(graph)


def calculate_distance(input_graph, source):
    Q = Queue()
    distance_dict = {k: 999999999 for k in input_graph.keys()}
    visited_vertices = list()
    Q.put(source)
    visited_vertices.append(source)
    while not Q.empty():
        vertex = Q.get()
        if vertex == source:
            distance_dict[vertex] = 0
        for u in input_graph[vertex]:
            if u not in visited_vertices:
                # update the distance
                if distance_dict[u] > distance_dict[vertex] + 1:
                    distance_dict[u] = distance_dict[vertex] + 1
                Q.put(u)
                visited_vertices.append(u)
    return distance_dict


distances = calculate_distance(graph, "A")
for vertex in distances:
    print("Shortest Path Length to {} from {} is {}.".format(vertex, "A", distances[vertex]))

Output:

Given Graph is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
Shortest Path Length to A from A is 0.
Shortest Path Length to D from A is 1.
Shortest Path Length to B from A is 1.
Shortest Path Length to C from A is 2.
Shortest Path Length to E from A is 1.

Conclusion

In this article, we have discussed and implemented the algorithm to calculate the shortest path length between vertices in an unweighted graph. Here we have used the breadth first graph traversal algorithm. To read about binary tree traversal algorithms, you can read  Inorder tree traversal algorithm or level order tree traversal algorithm.

The post Shortest Path Length from a Vertex to other Vertices in a Graph appeared first on PythonForBeginners.com.

What is breadth first traversal?

Breadth first traversal is a graph traversal algorithm to print all the vertices in a graph. In this algorithm, we start with a vertex and print its value. Then we print all the neighbors of the current vertex. After that, we select every neighbor of the current vertex and print all of its neighbors. This process continues until all of the vertices in the graph are printed.

Let us understand this process by performing a breadth first traversal on the following graph.

Suppose that we start from vertex A.

After printing vertex A, we will print all of its neighbor vertices i.e. B, D, E, and F.

After printing B,D, E, and F, we will select one of these vertices. Let us select D.

As D has no neighbor that needs to be printed, we will move back to A and choose another neighbor of A. Let us select E.

As E has no neighbor that needs to be printed, we will move back to A and choose another neighbor of A. Let us select F.

As F has no neighbor that needs to be printed, we will move back to A and choose another neighbor of A. Let us select B.

Now, we will print all the neighbors of B that have not been printed yet. Hence, we will print C. 

At this point, you can observe that all of the vertices in the graph have been printed in the order A, B, D, E, F, C . So, we will terminate the algorithm. 

Algorithm for breadth first traversal 

The algorithm for depth first traversal of a graph is implemented using a queue data structure. Here, we will assume that we have a connected graph. In other words, we can reach each vertex of the graph from the starting vertex.

We will maintain a queue to store the vertices that have not been printed and a list to store the visited vertices. After that we will process the graph using the following algorithm.

1. Create an empty queue Q to store the vertices that have not been printed.
2. Create an empty list L to store the visited vertices.
3. Insert source vertex into the Q and L.
4. If Q is empty, Go to 9. Else go to 5.
5. Take out a vertex v from Q.
6. Print the vertex v.
7. Insert all the neighbors of v that are not in L into Q as well as L.
8. Go to 4.
9. Stop.

This Algorithm can be demonstrated using the following source code for the graph given in the figure above.

from queue import Queue

graph = {'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
print("Given Graph is:")
print(graph)


def BFS_Algorithm(input_graph, source):
    Q = Queue()
    visited_vertices = list()
    Q.put(source)
    visited_vertices.append(source)
    while not Q.empty():
        vertex = Q.get()
        print("At:",vertex)
        print("Printing vertex:",vertex)
        for u in input_graph[vertex]:
            if u not in visited_vertices:
                print("At vertex, adding {} to Q and visited_vertices".format(vertex, u))
                Q.put(u)
                visited_vertices.append(u)
        print("visited vertices are: ", visited_vertices)


print("BFS traversal of graph with source A is:")
BFS_Algorithm(graph, "A")

Output:

Given Graph is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
BFS traversal of graph with source A is:
At: A
Printing vertex: A
At vertex, adding A to Q and visited_vertices
At vertex, adding A to Q and visited_vertices
At vertex, adding A to Q and visited_vertices
At vertex, adding A to Q and visited_vertices
visited vertices are:  ['A', 'B', 'D', 'E', 'F']
At: B
Printing vertex: B
At vertex, adding B to Q and visited_vertices
visited vertices are:  ['A', 'B', 'D', 'E', 'F', 'C']
At: D
Printing vertex: D
visited vertices are:  ['A', 'B', 'D', 'E', 'F', 'C']
At: E
Printing vertex: E
visited vertices are:  ['A', 'B', 'D', 'E', 'F', 'C']
At: F
Printing vertex: F
visited vertices are:  ['A', 'B', 'D', 'E', 'F', 'C']
At: C
Printing vertex: C
visited vertices are:  ['A', 'B', 'D', 'E', 'F', 'C']

In the output, you can observe that the vertices have been printed in the order A, B, D, E, F, and C.

Implementation of Breadth first traversal in Python

As we have discussed the general idea for breadth first traversal of a graph and observed how the algorithm works using the python program, we can implement the breadth first traversal algorithm as follows.

from queue import Queue

graph = {'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
print("Given Graph is:")
print(graph)


def BFS(input_graph, source):
    Q = Queue()
    visited_vertices = list()
    Q.put(source)
    visited_vertices.append(source)
    while not Q.empty():
        vertex = Q.get()
        print(vertex, end= " ")
        for u in input_graph[vertex]:
            if u not in visited_vertices:
                Q.put(u)
                visited_vertices.append(u)


print("BFS traversal of graph with source A is:")
BFS(graph, "A")

Output:

Given Graph is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
BFS traversal of graph with source A is:
A B D E F C 

Conclusion

In this article, we have discussed the breadth first traversal algorithm for a fully connected graph in python. To read more about other algorithms, you can read this article on In-order tree traversal in Python.

The post Breadth First Traversal in Python appeared first on PythonForBeginners.com.

What is depth first traversal?

Depth first traversal is a graph traversal algorithm in which we start from a vertex of a graph and print its value. Then we move to one of the neighbors of the present vertex and print its values. If there are no neighbors of the current vertex that have to be printed, we move to the previous vertex to see if all of their neighbors are printed. If not, we select one of the neighbors and print its value. We repeat this process until all the vertices of the graph are printed.  It should be noted that we have to print each vertex only once. 

Let us try this process on the following graph.

Here, Let us start from the vertex A. First, we will print A. After that we will select one of the vertices from B, D,E and F as all are neighbors of A. 

Let us select B. After printing B, we will select one of the vertices from A, C and F as these are neighbors of B. Here, A is already printed so it won’t be selected.

Let us select C. After printing C, we have no neighbors of C to print. So, we will move to the previous vertex of C i.e. vertex B to check if all the neighbors of B are already printed. Here, F has not been printed yet. So, we will select F.

After printing F, we have to select one of the vertices from A and B as these are neighbors of F. But, both these vertices are already printed. So, we will move to previous vertex of F i.e. B. 

At B, we can see that all the neighbors of B have already been printed. So, we will move to previous vertex of B i.e. A. 

At A, neighbors D and E have not been printed yet, So we will select one of the vertices.

Let us select D. After printing D, we can see that D does not have any neighbors to print. So, we will move to its previous vertex i.e A. 

Now, only one neighbor of A has not been printed i.e. E. So, we will print E.

At this point, all of the vertices of the graph have been printed in the order A, B, C, F, D, E. Hence, we will stop this process.

You can observe that there may be many depth first traversal of a single graph based on the neighbor that we choose. 

Algorithm for depth first traversal

The algorithm for depth first traversal of a graph is implemented using a stack data structure. Here, we will assume that we have a connected graph. In other words, we can reach each vertex of the graph from the starting vertex.

We will maintain a stack to store the vertices that have not been printed and a list to store the visited vertices. After that we will process the graph using the following algorithm.

1. Create an empty stack S to store the vertices that have not been printed.
2. Create an empty list L to store the visited vertices.
3. Insert the source vertex into S. Also, insert the source vertex to L.
4. If  the stack S is empty, Go to 9 else go to 5.
5. Take out a vertex v from S.
6. Print the value in v. 
7. Insert all the unvisited neighbors of v into the stack S and list L.
8. Go to 4.
9. Stop.

This Algorithm can be demonstrated using the following source code for the graph given in the figure above.

graph = {'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
print("Given Graph is:")
print(graph)


def DFS_Algorithm(input_graph, source):
    stack = list()
    visited_list = list()
    print("At {}, adding vertex {} to stack and visited list".format(source, source))
    stack.append(source)
    visited_list.append(source)
    while stack:
        vertex = stack.pop()
        print("At vertex :", vertex)
        print("Printing vertex:", vertex)
        for u in input_graph[vertex]:
            if u not in visited_list:
                print("At {}, adding vertex {} to stack and visited list".format(vertex, u))
                stack.append(u)
                visited_list.append(u)
        print("Vertices in visited list are:", visited_list)
        print("Vertices in stack are:", stack)


print("Explanation of DFS traversal of graph with source A is:")
DFS_Algorithm(graph, "A")

Output:

Given Graph is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
Explanation of DFS traversal of graph with source A is:
At A, adding vertex A to stack and visited list
At vertex : A
Printing vertex: A
At A, adding vertex B to stack and visited list
At A, adding vertex D to stack and visited list
At A, adding vertex E to stack and visited list
At A, adding vertex F to stack and visited list
Vertices in visited list are: ['A', 'B', 'D', 'E', 'F']
Vertices in stack are: ['B', 'D', 'E', 'F']
At vertex : F
Printing vertex: F
Vertices in visited list are: ['A', 'B', 'D', 'E', 'F']
Vertices in stack are: ['B', 'D', 'E']
At vertex : E
Printing vertex: E
Vertices in visited list are: ['A', 'B', 'D', 'E', 'F']
Vertices in stack are: ['B', 'D']
At vertex : D
Printing vertex: D
Vertices in visited list are: ['A', 'B', 'D', 'E', 'F']
Vertices in stack are: ['B']
At vertex : B
Printing vertex: B
At B, adding vertex C to stack and visited list
Vertices in visited list are: ['A', 'B', 'D', 'E', 'F', 'C']
Vertices in stack are: ['C']
At vertex : C
Printing vertex: C
Vertices in visited list are: ['A', 'B', 'D', 'E', 'F', 'C']
Vertices in stack are: []

In the output, you can observe that all the vertices are finally present in the visited list and they are printed in the order A, F, E, D, B,C. You can see that the order of vertices is not similar to what we have discussed in the previous section. This is due to the fact that we have many options to choose when we are selecting neighbors of a vertex and the order will depend on the vertex we select.

Implementation of Depth first traversal in Python

As we have discussed the general idea for depth first traversal of a graph and observed how the algorithm works using the python program, we can implement the depth first traversal algorithm as follows.

graph = {'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
print("Given Graph is:")
print(graph)


def dfs_traversal(input_graph, source):
    stack = list()
    visited_list = list()
    stack.append(source)
    visited_list.append(source)
    while stack:
        vertex = stack.pop()
        print(vertex, end=" ")
        for u in input_graph[vertex]:
            if u not in visited_list:
                stack.append(u)
                visited_list.append(u)


print("DFS traversal of graph with source A is:")
dfs_traversal(graph, "A")

Output:

Given Graph is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
DFS traversal of graph with source A is:
A F E D B C 

Conclusion

In this article, we have discussed the depth first traversal algorithm for a fully connected graph and we have also implemented it in Python. We have used a list as a stack in our implementation but stacks can also be implemented using a linked list in Python. TO read more about other algorithms, you can read this article on In-order tree traversal in Python.

The post Depth First Traversal in Python appeared first on PythonForBeginners.com.

What are different graph operations?

A graph is generally provided in the form of an adjacency list. If we talk about operations on the, there may be the following graph operations. 

• Print all the vertices of the graph
• Print all the edges of the graph
• Insert a vertex into the graph
• Insert an edge into the graph

We will perform all these graph operations in python. For this, we will use the graph given in the following image.

Before performing the graph operations, we will construct an adjacency list representation of the above graph as follows.

graph = {'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
print("Graph representation in python is:")
print(graph)

Output:

Graph representation in python is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}

How to print all the vertices of a graph

From the previous post on graphs in python, we know that the vertices of the graph are represented using the keys of the adjacency matrix (which is a python dictionary). Hence, we can print all the vertices of the graph by simply printing the keys of the adjacency matrix. For this, we will use the keys() method of a python dictionary as follows.

graph = {'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
print("Graph representation in python is:")
print(graph)
vertices= list(graph.keys())
print("Vertices in the graph are:",vertices)

Output:

Graph representation in python is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
Vertices in the graph are: ['A', 'D', 'B', 'F', 'C', 'E']

How to print all the edges of the graph

We know that edges are represented in the graph by using a list associated with each vertex. Every vertex stores a list of vertices with which it is connected.  We will traverse through each vertex v1 and create an edge (v1,v2 ) for each vertex present in the list associated with v1. 

Remember that while printing the edges, there will be repetitions because whenever a vertex v2 is present in the list associated with v1, v1 will also be present in the list associated with v2. Hence, while printing the edges, both (v1,v2) and (v2,v1) will be printed which introduces redundancy as (v1,v2) and (v2,v1) both represent the same edge.

To overcome this problem, we will store any edge (v1, v2) as an unordered set. In this way, (v1, v2) will be the same as (v2,v1). After that, we will create a list of edges. Before inserting any new edge to the list, we will first check if the edge is present in the list or not. If any edge is already present in the list, we will not insert any duplicate edge. 

The above process can be implemented in python as follows.

graph = {'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
print("Graph representation in python is:")
print(graph)
edges = []
for vertex in graph:
    for adjacent_vertex in graph[vertex]:
        edge = {vertex, adjacent_vertex}
        if edge not in edges:
            edges.append(edge)

print("Edges in the graph are:", edges)

Output:

Graph representation in python is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
Edges in the graph are: [{'B', 'A'}, {'A', 'D'}, {'A', 'E'}, {'A', 'F'}, {'B', 'F'}, {'B', 'C'}]

 How to insert a vertex into the graph

We know that a vertex is represented using keys of the adjacency list. To insert a vertex into the graph, we will insert the vertex as a key into the graph with an empty list  as its associated value. The empty list represents that the current vertex is not connected to any other vertex. We can implement it as follows.

graph = {'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
print("Original Graph representation is:")
print(graph)
# insert vertex G
graph["G"] = []
print("The new graph after inserting vertex G is:")
print(graph)

Output:

Original Graph representation is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
The new graph after inserting vertex G is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A'], 'G': []}

How to insert an edge into the graph

Inserting an edge into the graph is much simpler than printing the edges. We know that each vertex contains a list of vertices to which it is connected. So, to insert an edge (v1,v2), we will simply insert the vertex v1 to the list of vertices associated with v2 and v2 to the list of vertices associated with the vertex v1. 

In this way, It will be established that v1 is connected to v2 and v2 is connected to v1. Hence, the vertex (v1,v2) will be added in the graph. We can implement it as follows.

graph ={'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A'], 'G': []}
print("Original Graph representation is:")
print(graph)
# insert vertex (D,G)
graph["D"].append("G")
graph["G"].append("D")
print("The new graph after inserting edge (D,G) is:")
print(graph)

Output:

Original Graph representation is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A'], 'G': []}
The new graph after inserting edge (D,G) is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A', 'G'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A'], 'G': ['D']}

Conclusion

In this article, we have implemented different graph operations in python. To know more about other data structures, you can read this article on Linked list in python.

The post Graph Operations in Python appeared first on PythonForBeginners.com.

What is a graph?

In mathematics, A graph is defined as a set of vertices and edges where vertices are particular objects and edges represent the connections between the vertices. The vertices and edges are represented by using sets. 

Mathematically, a graph G can be represented as G= (V , E), where V is the set of vertices and E is the set of edges.

If an edge E_i connects vertices v1 and v2, we can represent the edge as E_i= (v1, v2).

How to represent a graph?

We will use the graph given in the following figure to learn how to represent a graph.

To represent a graph, we will have to find the set of vertices and edges in the graph. 

First, we will find the set of vertices. For this, we can create a set using the vertices given in the above figure. In the figure, the vertices have been named A,B,C,D,E, and F. So the set of vertices can be created as V={A, B, C, D, E, F}. 

To find the set of edges, first we will find all the edges in the graph. You can observe that there are 6 edges in the graph numbered from E₁ to E₆. An edge E_i can be created as a tuple (v1, v2) where v1 and v2 are the vertices being connected by E_i. For the above graph, We can represent the edges as follows.

• E₁=(A, D) 
• E₂ = (A,B)
• E₃= (A,E)
• E₄=(A, F)
• E₅=(B,F)
• E₆= (B,C)

The set of edges E can be represented as E= {E₁, E₂ , E₃, E₄, E₅, E₆}.

Finally, the graph G can be represented as G= (V,E) where V and E are sets of vertices and edges.

Till now, we have discussed how to represent a graph mathematically. Can you think of a way to represent a graph in a python program? Let us look into it.

How to represent a graph in Python?

We can represent a graph using an adjacency list. An adjacency list can be thought of as a list in which each vertex stores a list of all the vertices connected to it. 

We will implement the adjacency list representation of the graph in python using a dictionary and lists. 

First, we will create a python dictionary with all the vertex names as keys and an empty list (adjacency list) as their associated values using the given set of vertices.

After that, we will use the given set of edges to complete the adjacency list of each vertex that has been represented using the keys of the dictionary. For every edge (v1,v2), we will add v1 to the adjacency list of v2 and v2 to the adjacency list of v1. 

In this way, every key (vertex) in the dictionary will have an associated value (a list of vertices) and the dictionary will represent the whole graph in python. 

Given the set of vertices and edges, we can implement a graph in python as follows.

vertices = {"A", "B", "C", "D", "E", "F"}
edges = {("A", "D"), ("A", "B"), ("A", "E"), ("A", "F"), ("B", "F"), ("B", "C")}
graph = dict()
for vertex in vertices:
    graph[vertex] = []
for edge in edges:
    v1 = edge[0]
    v2 = edge[1]
    graph[v1].append(v2)
    graph[v2].append(v1)
print("The given set of vertices is:", vertices)
print("The given set of edges is:", edges)
print("Graph representation in python is:")
print(graph)

Output:

The given set of vertices is: {'F', 'D', 'B', 'E', 'A', 'C'}
The given set of edges is: {('A', 'F'), ('A', 'B'), ('B', 'C'), ('A', 'D'), ('A', 'E'), ('B', 'F')}
Graph representation in python is:
{'F': ['A', 'B'], 'D': ['A'], 'B': ['A', 'C', 'F'], 'E': ['A'], 'A': ['F', 'B', 'D', 'E'], 'C': ['B']}

In the above output, you can verify that each key of the graph has a list of vertices that are connected to it as its value.

Conclusion

In this article, we have discussed graph data structure. We also discussed the mathematical representation of a graph and how we can implement it in python. To learn more about data structures in Python, you can read this article on Linked list in python.

The post Graph in Python appeared first on PythonForBeginners.com.

What is the mirror image of a binary tree?

Mirror image of a binary tree is another binary tree which can be created by swapping left child and right child at each node of a tree. So, to find the mirror image of a binary tree, we just have to swap the left child and right child of each node in the binary tree. Let us try to find the mirror image of the following tree.

To find the mirror image of the above tree, we will start from the root and swap children of each node.

At root , we will swap the left and right children of the binary tree. In this way, 20,11, and 22 will come into the right subtree of the binary tree and 53,52, and 78 will come to the left of the binary tree as follows.

Then we will move to the next level and swap the children of 53. Here, 78 will become the left child of 53 while 52 will become the right child of 53. Similarly we will swap the left child and right child of 20. In this way, 22 will become the left child of 20 while 11 will become the right child of 20. The output binary tree after swapping nodes at this level will be as follows.

Now we will move to the next level. At this level, all the nodes are leaf nodes and have no children. Due to this there will be no swapping at this level and the above image is the final output.

Algorithm to find mirror image of a binary tree

As we have seen above, We can find the mirror image of a binary tree by swapping the left child and right child of each node. Let us try to formulate the algorithm in a systematic way. 

In the last example, At the second level, each node has only leaf nodes as their children. To find the mirror image at a node at this level, we have just swapped the left and right child at each node at this level. At the root node, we have swapped its both subtrees. As we are swapping each subtree (leaf nodes are also subtree), we can implement this algorithm using recursion.

The algorithm for finding a mirror image of a binary tree can be formulated as follows.

1. Start from the root node.
2. Recursively find the mirror image of the left subtree.
3. Recursively find the mirror image of the right subtree.
4. Swap the left and right subtree.

Implementation of Algorithm in Python

Now we will implement the algorithm to find the mirror image of a binary tree in Python.

from queue import Queue


class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None


def mirror(node):
    if node is None:
        return None
    mirror(node.leftChild)
    mirror(node.rightChild)
    temp = node.leftChild
    node.leftChild = node.rightChild
    node.rightChild = temp


def insert(root, newValue):
    # if binary search tree is empty, create a new node and declare it as root
    if root is None:
        root = BinaryTreeNode(newValue)
        return root
    # if newValue is less than value of data in root, add it to left subtree and proceed recursively
    if newValue < root.data:
        root.leftChild = insert(root.leftChild, newValue)
    else:
        # if newValue is greater than value of data in root, add it to right subtree and proceed recursively
        root.rightChild = insert(root.rightChild, newValue)
    return root


def inorder(root):
    if root:
        inorder(root.leftChild)
        print(root.data, end=" ")
        inorder(root.rightChild)


root = insert(None, 50)
insert(root, 20)
insert(root, 53)
insert(root, 11)
insert(root, 22)
insert(root, 52)
insert(root, 78)
print("Inorder Traversal of tree before mirroring:")
inorder(root)
mirror(root)
print("\nInorder Traversal of tree after mirroring:")
inorder(root)

Output:

Inorder Traversal of tree before mirroring:
11 20 22 50 52 53 78 
Inorder Traversal of tree after mirroring:
78 53 52 50 22 20 11 

Here, we have created a binary tree node. After that, we defined functions to insert elements to the binary tree. We have also used the in-order tree traversal algorithm to print the elements of the tree before and after finding the mirror image.

Conclusion

In this article, we have implemented an algorithm to find the mirror image of a binary tree. To learn more about other data structures, you can read this article on Linked List in Python. Stay tuned for more articles on implementation of different algorithms in Python.

The post Find the mirror image of a binary tree appeared first on PythonForBeginners.com.

What is the height of a binary tree?

Height of a binary tree is defined as the maximum distance from the root node at which a node is present in the binary tree. The height of a binary tree depends on the number of nodes and their position in the tree. If a tree has an ‘n’ number of nodes, it can have a height anywhere between log(n) + 1 to n.  The binary tree will have a height n if the tree is entirely skewed to either left or right. It will have a height of log(n)+1 if the nodes in the tree are properly distributed and the tree is a complete binary tree.

For example, the following binary tree has 7 elements.A binary tree with 7 elements can have any height between log(7)+ 1 that is 3 and 7. In our example, the nodes of the tree are properly distributed and the tree is completely balanced. Therefore, the height of the tree is 3.

How to calculate the height of a binary tree?

To calculate the height of a binary tree, we can calculate the heights of left and right subtrees. The maximum of the height of the subtrees can be used to find the height of the tree by adding one to it. For an empty root, we can say that the height of the tree  is zero. Similarly, height of a single node will be considered as 1. 

Algorithm to find the height of a binary tree

Now that we have found a way to find the height of the binary tree, we will formulate the algorithm for finding the height as follows.

1. If we find an empty root node, we will say that the height of the tree is 0.
2. Otherwise, we will find the height of the left subtree and right subtree recursively.
3. After finding the height of the left subtree and right subtree, we will calculate their maximum height.
4. We will add 1 to the maximum height. That will be the height of the binary tree.

Implementation of the algorithm in Python

Now that we have understood and formulated the algorithm, we will implement it in Python.

from queue import Queue


class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None


def height(root):
    if root is None:
        return 0
    leftHeight=height(root.leftChild)
    rightHeight=height(root.rightChild)
    max_height= leftHeight
    if rightHeight>max_height:
        max_height = rightHeight
    return max_height+1


def insert(root, newValue):
    # if binary search tree is empty, create a new node and declare it as root
    if root is None:
        root = BinaryTreeNode(newValue)
        return root
    # if newValue is less than value of data in root, add it to left subtree and proceed recursively
    if newValue < root.data:
        root.leftChild = insert(root.leftChild, newValue)
    else:
        # if newValue is greater than value of data in root, add it to right subtree and proceed recursively
        root.rightChild = insert(root.rightChild, newValue)
    return root


root = insert(None, 50)
insert(root, 20)
insert(root, 53)
insert(root, 11)
insert(root, 22)
insert(root, 52)
insert(root, 78)
print("Height of the binary tree is:")
print(height(root))

Output:

Height of the binary tree is:
3

Here, we have created a binary tree node. Then, we defined functions to insert elements to the binary tree. Finally, we implemented the algorithm to find the height of a binary tree in Python.

Conclusion

In this article, we have implemented an algorithm to find the height of a binary tree. To learn more about  other data structures, you can read this article on Linked List in Python. Stay tuned for more articles on implementation of different algorithms in Python.

The post Find the Height of a Binary Tree appeared first on PythonForBeginners.com.

What is Level Order Tree Traversal?

Level order tree traversal algorithm is a breadth-first tree traversal algorithm. It means that while traversing a tree, we first traverse all the elements at the current level before moving to the next level. To understand this concept, Let us consider the following binary search tree.

The level order traversal of the above tree will be as follows.

We will start from the root and print 50. After that we move to next level and print 20 and 53. After this level, we move to another level and print 11, 22, 52, and 78. So, the level order traversal of above tree is 50, 20, 53, 11, 22, 52, 78.

Algorithm for Level Order Tree Traversal

As we have seen that we have to process elements at each level one by one in the level order tree traversal, we can use the following approach. We will start from the root node and will print its value. After that, we will move both children of the root node to a queue. The queue will be used to contain elements that have to be processed next. Each time we process an element, we will put the children of that element into the queue. In this way all the elements at the same level will be pushed into the queue in continuous order and will be processed in the same order. 

The algorithm for level order tree traversal can be formulated as follows.

1. Define a Queue Q to contain the elements.
2. Insert the root into Q.
3. Take out a node from Q.
4. If  the node is empty i.e. None, goto 8.
5. Print the element in the node. 
6. Insert the left child of the current node into Q.
7. Insert the right child of the current node into Q.
8. Check if Q is Empty. If Yes, Stop. else, goto 3.

Implementation of Level Order Tree Traversal Algorithm in Python

Now we will implement the above algorithm in python. After that, we will process the binary search tree used in the above example using the same algorithm.

from queue import Queue


class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None


def levelorder(root):
    Q = Queue()
    Q.put(root)
    while (not Q.empty()):
        node = Q.get()
        if node == None:
            continue
        print(node.data)
        Q.put(node.leftChild)
        Q.put(node.rightChild)


def insert(root, newValue):
    # if binary search tree is empty, create a new node and declare it as root
    if root is None:
        root = BinaryTreeNode(newValue)
        return root
    # if newValue is less than value of data in root, add it to left subtree and proceed recursively
    if newValue < root.data:
        root.leftChild = insert(root.leftChild, newValue)
    else:
        # if newValue is greater than value of data in root, add it to right subtree and proceed recursively
        root.rightChild = insert(root.rightChild, newValue)
    return root


root = insert(None, 50)
insert(root, 20)
insert(root, 53)
insert(root, 11)
insert(root, 22)
insert(root, 52)
insert(root, 78)
print("Level Order traversal of the binary tree is:")
levelorder(root)

Output:

Level Order traversal of the binary tree is:
50
20
53
11
22
52
78

In the above program, we have first implemented the binary search tree given in the figure. Then We have used the algorithm for level order tree traversal to traverse the binary search tree in Python. As you can observe, The program used a queue to store the data for processing. Also, the elements of the binary search tree have been printed from left to right in the order of their depth in the tree. The root is printed first while the leaf nodes are printed at last.

Conclusion

In this article, we have discussed the level order tree traversal algorithm in Python. Level order tree traversal can be used to find the width of a binary tree in Python. Also, This algorithm has been used to implement various other algorithms that we will discuss later in this series. In next articles, we will implement other tree traversal algorithms such as In-order tree traversal, pre-order tree traversal, and post-order tree traversal algorithm. To learn more about other data structures, you can read this article on Linked List in Python. Stay tuned for more articles on implementation of different algorithms in Python.

The post Level Order Tree Traversal in Python appeared first on PythonForBeginners.com.