Trees - A Non Linear Data Structure

Trees are undirected (without direction) graphs with exactly one path between any two nodes. They are also non-linear data structures that have node-relationships: parent nodes, siblings and children nodes.

Trees are helpful in implementing search algorithms like Breadth-First and Depth-First search. For a graph to be a tree, it should have no cycle, i.e. there shouldn't be more than one path between any two nodes. A graph G is a tree if it satisfies one of the following equivalent criteria:

• G is connected (a path to each node in the graph) and has no cycles.
• A cycle is formed if any two nodes are connected in G.
• G is connected (at least one path to each node), and it is not connected anymore if any edge is removed from G.

For a tree G with n number of nodes, it has n - 1 edges.

 An example of a graph (taken from here):

 I can spot 3 cycles, made of nodes:
- 2,3,4,5
-1,2,5
- 1,2,3,4,5

Now, an example of a tree (taken from here):

In this tree, n (number of nodes) = 7 and number of edges = n-1 = 7-1 = 6 edges

Read More

BFS and DFS - The Simplest of Search Algorithms

Every algorithms and artificial intelligence class starts with two simple search algorithms: Breadth First Search (BFS) and Depth First Search (DFS). They are used in data structures like trees, which is basically a network/graph of nodes that have values or states associated with them. What makes a tree a tree? Find out here. 

BFS and DFS are two kinds of search algorithms in which you follow a certain path to to go through each node until you find the goal node. They are uninformed searches, meaning you do not know whether one non-goal node is better than another non-goal node. This way you do not know whether the path that you are following is better than any other path that you could follow.

Now onto search strategies. Both strategies start with expanding a parent/start node s: i.e. recording its successor nodes.

Assume the following relationship: 
- s is the starting node
 - a and b are successor nodes of s
- x is a successor of a

In BFS, every direct successor of s will be checked for solution before moving onto its successors' successors. So a and b are checked for solution before checking x.  The path will look something like this:

In DFS, after expanding s, its first direct successor is checked for solution. If its not the goal node, we move on to the successor node of s's first direct successor node. So, a and x are checked for solution before b. The path for DFS looks like this:

Performance wise, one search strategy is not necessarily better than the other. Detailed comparisons here.
    

Read More