Graphs Data Structures
Graphs evolved from the field of mathematics. They are primarily used to describe a model that shows the route from one location to another location.
A graph consists of a set of nodes and a set of edges. An edge is a pair of nodes that are connected. A path is the term used to describe traveling between nodes that share an edge. The image below shows a graph with 3 nods and 3 edges.
Tree Data Structure
A tree data structure, like a graph, is a collection of nodes. There is a root node. The node can then have children nodes. The children nodes can have their own children nodes called grandchildren nodes.
This repeats until all data is represented in the tree data structure. The image below shows a tree data structure.
A tree is a graph that has no cycles (a cycle being a path in the graph that starts and ends at the same vertex). A child node can only have one parent. For this reason trees are not a recursive data structure.
Why Use Graphs and Trees as Data Structures?
In computer programming, trees are used all the time to define data structures. They are also used as the basis for algorithms to solve problems.
The most common implementations of a graph are finding a path between two nodes, finding the shortest path from one node to another and finding the shortest path that visits all nodes.
The traveling salesman problem is a great example of using a tree algorithm to solve a problem.
In my next post I will talk about the two methods to search a tree – breadth first search and depth first search.