Data Structures Final Review - GRAPHS ONLY

A set of vertices and edges that connect said vertices

1) Every node has a color either red or black.

2) Root of tree is always black.

3) There are no two adjacent red nodes (A red node cannot have a red parent or red child).

4) Every path from a node (including root) to any of its descendant NULL node has the same number of black nodes.

Insert: O(log N), Find: O(log N), Delete: O(log N)

If any bottom nodes are a 4 node (has three elements), preemptively split it upwards.
Search for the location to place the node and then insert it.

A bottom-up search tree whose nodes can have 1, 2, or 3 elements, and can have n elements + 1 children.

If a node has 3 elements, upon insertion, the node must be split upwards. The middle node becomes the parent of a left 2-node and a right 2-node, both holding a single element. If there are no parents, a new parent is formed, otherwise it joins the already existing parent. Splits may cascade upwards, upon which this is repeated.

Start at the root, searching for the node to delete. Along the way own, turn 2-nodes into three nodes (except for the root).
If an adjacent sibling is a 3 or 4 nodes, redistribute items from the sibling and adopt the child.
If the adjacent sibling is a 2-node, redistribute items from the parent (which will always have at least 2 items, unless it's the root), then merge the nodes.
Once the node is found, move it downward to a leaf node, shifting nodes along the way, then delete it.

A graph in which the edges have no direction.

A graph in which the edges have a direction.

An edge that originates and ends at the same node

A path that originates and ends at the same node.

A sequence of edges that start at one node and ends at another node, connected via intermediary edges between nodes.

A graph such that there is a path going from any node to any other node

A graph that is not connected (there exist nodes with no paths between them)

A graph with no cycles.

A |V| X |V| matrix M, where if M[u][v] is true, then there is an edge from u to v.

A linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

A directed graph with no cycles.

A search in which children of a node are considered before siblings are considered.

A search in which siblings of a node are considered before children are considered.

An algorithm for finding the shortest paths from an origin node to every other node.
1. Pick the closest unknown vertex v
2. Add it to the known vertices
3. Update distances for nodes with edges from v

1. Label each vertex with its in-degree
2. Enqueue each vertex with a degree of 0
3. Dequeue the first vertex, add it to the ordering, and then decrease the in-degree of all the vertices they point to.
4. Repeat Steps 2-4 until all vertices are ordered.

An algorithm that makes the best choice at each step.

A subgraph of a graph that includes all the vertices of the graph while retaining the minimum amount of edges (or minimum cost in the case of a weighted graph).

A graph where each edge has an associated cost.

1. Pick a node and mark it known
2. Select the lowest edge that is connected to our already known nodes, and is connected to an unknown node.
3. Add the edge to our spanning tree, and mark both it and the vertex its connected to as known.
4. Repeat 2-4 until all vertices are known.

1. Pick the lowest cost edge that does not cause a cycle
2. Repeat until all vertices are connected.

A table describing the shortest path from any vertex to any other vertex.

k = iteration number
D_k = |V| x |V| Distance table in kth iteration
S_k = |V| x |V| Sequence table in kth iteration
d_ij = Distance between vertex i and j

1. Remove self loops and resolve multiedges by picking the lowest node.
2. Fill the S_0 table by filling each column with the column number
3. Fill the D_0 table by filling dij with the cost of the edge between i and j if it exists, and infinity if it doesn't exist. If i == j, mark it as nil.
4. For each cell C_ij in D_k, if in D_k-1 d_ij > d_ik + d_kj, then C_ij = d_ik + d_kj and S_ij = k. Otherwise, C_ij = d_ij and S_ij copies the value from the previous table.
5. Increment k by 1. Loop 4-5 until k > |V|

Look up D[a][b].

Seq = []
"Seq top" is the topmost value of the sequence stack
1. Push vertex a onto Seq
2. Push S[Seq top][b] onto Seq
3. Repeat 2 until S[Seq top][b] == b

Two arrays describing the distances and sequences from a single source node to every other node.

D = Distance array
P = Predecessor Array
k = Iteration count
1. Fill the distance array with 0 at the source node, and infinity at every other node
2. Fill the predecessor array with nil
3. For each edge u -> v, determine if v.d > u.d + w(u, v). If so, set v.d = u.d + w(u, v), and set v.p = u.
4. Increment k, and repeat until k = |V|

A collection of sets with the operations union and find.

Start with a forest. Each forest has a weight corresponding to the amount of nodes in their uptree.
This can be represented using a parent array and a weight array.
Union(a, b): Find the roots of a and b. If a.w < b.w, have a point to b. Otherwise, have b point to a. Update the weight of b to be |a| + |b|.
Find(a): Find the root of a. If path compression is on, shift a upwards to directly point to the root to be accessed earlier.

O(|V| + |E|)

O(|V|^2)

O(|E|)

O(|V|^2)

O(|V| + |E|)

O(|V|)

O(|E|)

O(|V| + |E|)

O((|V| + |E|) log |V|)

O(|V|)

O(|V||E|)

O(|E|)

O(|V||E|)

O(|V|^3)

O(|E| log |V|)

O(|E| log |V|)

O(|E| + log |V|)

O(log |N|)

O(|V|^3)