Almost all theoretical concepts get their names from other closely related things in the world, trees and graphs are no different.
This is an extension to the linked list concepts we studied earlier, with an additional link to it. For example a binary search tree would look like
I hope it does resemble an inverted tree.
There is a difference between a binary search tree and a binary tree, in a binary search tree each node's left value is less than the node and the right one is greater than or equal to its parent. That rule does not apply for a binary tree.
Let us now start with a simple program to build a tree and traverse the same.
There are two ways to traverse :
i) Breath first search - also called level order traversal
Looks like this for the above tree
10 8 12 6 9 11 14 4 7 10 16
In the code example below, I am using a rand function to generate random number between 0 and 10, to insert in a binary search tree.
http://codepad.org/MLzcn1Qv
The only trick in this breadth first search is the usage of Queue data structure. As can be seen in the code above we print the current node data and enQueue the left and right nodes. This process continues till the queue is empty which happens when we are done traversing the tree.
ii) Depth first search.
Looks like this for the above tree
10 8 6 4 7 9 12 11 14 10 16
In the code example below, I am once again using a rand function to generate random numbers between 0 and 10 to insert in a binary tree.
http://codepad.org/V5qhHkY1
As seen in breadth first search the usage of Queue data structure is the trick but in depth first search using a Stack is the method to traverse. As can be seen in the code above we print the current node data and Push the left and right nodes. This process continues till the stack is empty which happens when we are done traversing the tree.
iii) In Order Traversal
The core concept of this traversal can be summarized into three simple steps
-> Visit the Left Node
-> Visit the Root Node
-> Visit the Right Node
iv) Pre Order Traversal
The core concept of this traversal can be summarized into three simple steps
-> Visit the Root Node
-> Visit the Left Node
-> Visit the Right Node
v) Post Order Traversal
The core concept of this traversal can be summarized into three simple steps
-> Visit the Left Node
-> Visit the Right Node
-> Visit the Root Node
Height of a tree :
The height of a tree node is the number of edges from the node to the trees leaf node. So the height of a leaf node is always 0.
Imagine a real tree, the distance from any segment of the tree to the leaf is the height of that segment.
Height of a node is the longest path from the node to the leaf, so to find that we recursively find the maximum height of its left and right nodes. When the node is NULL we return a 0 else we return max(leftHeight, rightHeight) + 1. In the tree shown above the height of the root node is 4.
Find the code for the same below.
http://codepad.org/KKNni5z4
Depth of a tree node is the number of edges between the root node and the node. So the depth of a root node is always 0.
Imagine a real tree, the distance from any segment of the tree to the root is its depth of that segment.
To find the depth of a node we do a binary search and return the number of edges visited + 1.
Code : http://codepad.org/HYOByZsx
Graphs :
Graphs are generally used to represent a network of roads, a communication network or the connections of a person in social networking sites. Its a digital representation of an actual relationship between two entities. In a way that the computer can understand and perform computation such as searching.
An edge represents the relation between two vertices. A vertex can represent a person in a social network or location in a road network or server in a communication network.
Now lets see how to represent a graph. There are three types of graphs a directed graph, undirected graph and weighted graphs.
Undirected Graph :
Directed Graph :
Unlike undirected graphs directed graphs have a direction in their relation between edges. That is we can go from edge 1 to edge 2 but not otherwise.
Weighted Graphs :
The above figure shows a weighted graph which has information in each of its edges, i.e for example in case of a road network it can represent the distance between two locations(vertices).
We now need to represent the graph to be able to use it n our code, there are two ways to do so.
i) Adjacency matrix
We represent all the nodes as rows and columns, the data in the matrix represents the connections
between the nodes
ii) Adjacency lists An array of linked lists is used to represent the graph, let the array be called listArray. listArray[i]
will represent the linked list of vertices adjacent to ith vertex.
Let us now move on to write a code to find the shortest distance between two vertices of a graph.
Dijkstra's Shortest Path Algorithm :
This is one among many algorithms being used to find the shortest path between two vertices in a graph. Its goes like this
1) Assign a distance value to every node in the graph. For example consider the graph below
Define an array of 6 elements called vertexDistanceArray which will be used to store the distance of each vertex from the source vertex in this case source vertex is A. Initialize this array with all elements set to infinity except to the source node which should be set to 0.
Define another array of 6 elements called visitedVertexArray which will keep track of which vertices have been visited and which have not yet been.
Another variable called currentDistance to keep track of the distance from the origin vertex to the current vertex. To begin with it is set to zero since the distance from A to A should be zero.
currentVertex will keep track of the current vertex in process.
2) Set the initial vertex as current vertex. In this case A
3) For the current node consider all the unvisited(from visitedVertexArray) vertices which are connected to A, i.e B and C in this case, you can get the information of the connections from the Adjacency matrix shown above.
The distance from A to B is 9 + currentDistance and A to C is 2 + currentDistance. Since the currentDistance when the currentVertex is A is 0 as discussed above, A - B distance : 9 A- C distance : 2.
4) After visiting all the vertices connected to the currentVertex, make the current vertex as visited.
5) If the destination node has been marked visited or if the current vertex is not connected to any vertex, the algorithm is completed.
6) Now select the unvisited node that is marked unvisited with smallest distance from the source vertex and continue from step three.
Example code :
http://codepad.org/QBkkmFMB
No comments:
Post a Comment