Graphs

Question 1

Tree compared to graph

Answer 1

1. tree can only flow in one direction (root node to lead/child nodes)
2. Trees only have one-way connections. Child node can only have 1 parent. ( no loops)

Question 2

Graph - Depth First Search/Traversal

Answer 2

1. Use a stack and a “Results” set.
2. Move along adjacent vertices in order as much as possible.
3. Add the visited vertex to the stack.
4. Mark each vertex as visited and place it in the set.
5. When no more non-visited adjacent vertices, we remove the current vertex from the stack and go back to the next one there.
6. Repeat

Question 3

Graph - Breadth-First Search/Traversal

Answer 3

1. Use a queue and a set.
2. Start with first vertex, as you look at adjacent vertices in order, add each vertex to the set if you’ve visited and add to the queue.
3. Once you’ve done all the adjacent vertices, de-queue the first vertex and now that is your “current” vertex.
4. Repeat

Question 4

Define a Graph

Answer 4

A graph “G” is an ordered piar of a set “V” of vertices and a set of “E” edges.
G = (V, E)

Question 5

Edges

Answer 5

Can be directed or undirected (directional).

Question 6

Vertices

Answer 6

Can be weighted or unweighted.

Question 7

Multi-Edge graph

Answer 7

two vertices that have two edges to each other (both directed or undirected).

Example is if there are multiple flights between two different cities. Each edge can have it’s cost.

Question 8

Given a simple graph ( no multi-edges or self-loops), how many max edges can you have if you have N vertices?

Answer 8

<= N(N - 1) if directed. 
<= (N(N - 1))   / 2 if undirected

I.e if V = 4
max E <= 12

Question 9

Define a Dense or Sparse graph and how would we define the storage structure depending on each?

Answer 9

Adjacency Matrix = Dense
Adjacency List = Sparse

Dense is close to the max number of edges.

Question 10

What are the 3 ways graphs can be represented?

Answer 10

1. Edge List
   - typically an array [1, 2]
   - node to node
   - lookup O(E), O(E) space
2. Adjacency Matrix
   - nested arrays to have row and columns
   - shows which nodes in the graph contain edges between them
   - 1 represents and edge, 0 is none. If there is weight, you would put the weight instead of 1 if the edge exists

Question 11

What are the 3 ways graphs can be represented?

Answer 11

1. Edge List
   - typically an array [1, 2]
   - node to node
   - lookup O(E), O(E) space
2. Adjacency Matrix
   - nested arrays to have row and columns
   - shows which nodes in the graph contain edges between them
   - 1 represents and edge, 0 is none. If there is weight, you would put the weight instead of 1 if the edge exists
   - If undirected, both sides of the main diagonal will be symmetric
   - always O(V^2) space
   - lookup, insert, remove O(1) time
   - if sparse, it’ll mostly be filled with O’s
3. Adjacency List
   - An array of linked lists (or arrays). Each vertex is given an index in a list and has it’s neighboring vertices stored as an array/linked list, adjacent to it.
   - lookup node neighbors O(1) time
   - lookup edges existence O(d) t
   - max possible degrees (d) of any vertex is (|V| - 1), minimum value for D is 0
   - if undirected, each edge will be represented twice 2(| E |)