Graphs

Front 1

What's the difference between a graph and a tree?

Back 1

trees are a special case of a graph with no cycles

Front 2

What's an undirected graph?

Back 2

Any connection goes both ways.

Front 3

What's a directed graph?

Back 3

Connections only go one way.

Front 4

What is an adjaceny list?

Back 4

Something like,

a, b

a, c

c, b to model a graph with connections between those pairs of objects.

Front 5

What is an adjacenty matrix

Back 5

Something like

- a b c

a 0 1 1

b 0 0 0

c 0 1 0

to model a graph with connections between those objects

Front 6

How do you represent a graph with objects and pointers

Back 6

You'd have object a with pointers to b and c, and object c with a pointer to b, to model a graph with connections between objects

Front 7

What's std::set?

Back 7

In c++, a container that holds many (unlimited) const objects. Useful for declaring std::set<Pointer_type*> to store all the pointers from an object in a graph, when you don't know ahead of time how many there will be. Also takes custom less than comparators

Front 8

Explain DFS in the context of graphs

Back 8

Favors exploring unvisited nodes with a greater distance from root first. Good for finding things that are likely to be far away from root. Must have a way to make nodes visited/unvisited. Push things onto the stack (LIFO) until you run out of choices; then pop until you find a choice again.

Front 9

Explain BFS In the context of graphs

Back 9

Favors exploring unvisited nodes at the same distance from root first. Examine item at front of queue. If not searched-for-thing, add it's unvisited neighbors to the end of the queue and mark them visited (to prevent re-adding same nodes).

Front 10

What are the complexity properties of an adjacency list?

Back 10

Storage: O(V / E)

Adding Vertex: O(1)

Adding Edge: O(1)

Removing Vertex O(V/E)

Removing Edge O(E)

Query O(V)

Front 11

What are the complexity properties of an adjacency matrix?

Back 11

Storage: O(V^2)

Adding Vertex: O(V^2)

Adding Edge: O(1)

Removing Vertex O(V^2)

Removing Edge O(1)

Query O(1)

Front 12

What's Dijkstra ?

Back 12

How you go about calculating the "best" path when edges have weight; for example a busy road might be shorter but less ideal for a directions finding app. Instead of maintaining the shortest number of nodes, you maintain the shortest total weights.