graphs and trees Flashcards
graphs consist of…
nodes connected ny edges
path
a route from a starting node to a destination node
graph theory
a field of math that studies graphs, their properties, and their application
connected graphs
for any pair of nodes u and v, there is a path from u to v
connected graphs <->
disconnected
directed graphs
directed edges
weakly connected
there is a path between every pair of vertices in the undirected version of the graph
strongly connected
for every pair of vertices u and v, there is a directed path from u to v and a directed path from v to u.
cyclic
contains one or more cycles
acyclic
contains no cycles
weighted
edges have numerical values, called weight
DAG
directed acyclic graph
edges in non-weighted graphs carry binary information:
they do exist or they don’t
tree
and undirected graph in which any two nodes are connected by exactly one path, or equivalently a connected acyclic undirected graph
directed tree
DAG whose underlying undirected graph is a tree
binary trees
a tree data structure in which each node has at most 2 children
root
node that has no parent nodes
leaf
node that has no children
perfect binary tree
all nodes have either 0 or 2 children and all leaf nodes are at the same distance from the root
degenerate tree
opposite of balanced, each parent node has only one associated child node
worst case complexity for searching a tree
O(N)
binary search tree
a binary tree whose internal nodes each store a key greater than all the keys in the node’s left subtree and less than those in its right subtree
quadtrees
each node can have up to four child nodes, allowing both dimensions to be split in half
