# Graphs Flashcards

Legal Graph Coloring

No adjacent nodes can have the same color

Adjacency List

A 2D array where the first index represents the node and the second index is a list of that node’s neighbors. (Can use a hashmap if the node is an object rather than an int.)

Adjacency Matrix

A matrix of 1’s and 0’s indicating if node x connects to node y.

How do you determine if an undirected graph be colored with two colors?

Run BFS assigning colors as you visit nodes. Abort if you ever try to assign a different color to the same node.

Does this undirected graph have a cycle?

Run BFS keeping track of the number of times we visit each node. If you ever visit a node twice, you’ve found a cycle.

Dijkstra’s Algorithm

Finds the shortest path from a node to all other nodes in a *weighted* graph.

Degree

Number of edges connected to the node

Binary Search

Find an item in a SORTED array in log n time.

invert a binary tree

flip each row

imagine flipping the tree around a center axis

O(n) because you visit each node once

The space complexity is O(height) because you call the function once for each level of the tree. That means the worst case space complexity is O(n). That would be a fully balanced tree or a tree with only one child node for each node.