# Graphs Flashcards

1
Q

Legal Graph Coloring

A

No adjacent nodes can have the same color

2
Q

A

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.)

3
Q

A

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

4
Q

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

A

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

5
Q

Does this undirected graph have a cycle?

A

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.

6
Q

Dijkstra’s Algorithm

A

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

7
Q

Degree

A

Number of edges connected to the node

8
Q

Binary Search

A

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

9
Q

invert a binary tree

A

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.