Courses‎ > ‎AP Computer Science 2‎ > ‎konstantinovich‎ > ‎

2018-04-20

posted Apr 20, 2018, 10:18 AM by Konstantinovich Samuel   [ updated Apr 23, 2018, 5:44 AM ]
Goal: Trees

Graph: a relational data structure that stores points of interest and the relationships between them (nodes and edges)
The edges are pairs of nodes. A graph models the pairwise relationship between objects.

-The edges can be one way (directed graph) or bi-directional
-In some graphs the edges have an additional value or weight (weighted graph)
-Directed graphs can have different weights in each direction.

A linked list is a graph 
    Edges: next/prev 
    Nodes:  the data/node
A maze can be represented by a graph. 
    Edges: where you can go from the current location
    Nodes: a single space on the maze
    Adjacent spaces have an edge between them.



Tree: an acyclic graph.



Breadth First Search vs. Depth First Search

Depth-First Search

-Tests all possibilities in one path until it needs to backtrack. This is the recursively backtrack you have written for your previous assignments (until now!)

-Does not guarantee shortest path / closest value.

(Visually DFS goes to bottom of a tree, then backtracks, etc.)


Breadth-First Search

BFS checks the first node, then its direct children, then the children of those. Tests all possibilities in order from the closest possibility to the furthest.

This will find the closest matching value or shortest path to a goal.

(Visually BFS will check the next level of the tree, then the next level... etc)



Maze example:


S _ _ _ _

_ # # # _

_ _ _ # _

_ # _ # _

_ _ # # E

Lets label the spaces we want to go to make our lives easier!

or:

0 1 2 3 4

1 # # # 5

2 3 4 # 6

3 # 5 # 7

4 5 # # 8

Even though some maze's graphs are not trees, they COULD be. We just don't link up the nodes if there is already a node linked to something (prevent cycles)



This expression tree is a binary tree that represents
an arithmetic expression. The results are always doubles,
no int operations nor booleans/strings etc.
-Example:
  +
 / \
3   *
  /  \
 2   10
- Any node with children is treated like an operator.
- Any node without children is treated like a value.


Comments