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: TreesGraph: 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/nodeA 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 SearchDepth-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 SearchBFS 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 _ _ _ _ _ # # # _ _ _ _ # _ _ # _ # _ _ _ # # ELets 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 # # 8Even 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.```