Graphs

Question 1

What is a ‘graph’?

Answer 1

A set of vertices and edges

Question 2

What does it mean for two vertices to be (adjacent)?

Answer 2

Two vertices are adjacent if there exists an edge connecting them.

Question 3

What is a ‘Weighted Graph’?

Answer 3

A graph in which a values is associates w/ each edge.

Question 4

What is a ‘Directed Graph’?

Answer 4

A graph in which every edge has a direction associated with it.

Question 5

What is a ‘Dependency Graph’?

Answer 5

A data structure formed by a directed graph that describes the dependency of an entity in the system on the other entities of the same system.

Question 6

What are the two ways in which graphs are represented?

Answer 6

1. Adjacency Matrix
2. Adjacency List

Question 7

What is the runtime for determining if there is an edge between two vertices?

Answer 7

1. Adjacency Matrix: Theta(1)
2. Adjacency List: O(d)/O(V)
   where d is the degree of the vertex.

Question 8

What is the runtime for determining all vertices adjacent to a given vertex?

Answer 8

1. Adjacency Matrix: Theta(V)
2. Adjacency List: O(d)/O(V)
   where d is the degree of the vertex.

Question 9

What are the space requirements for each representation of a graph?

Answer 9

1. Adjacency Matrix: Theta(V^2)
2. Adjacency List: Theta(V+E)

Question 10

When should you use an Adjacency Matrix?

Answer 10

1. Small Graphs
2. Dense Graphs

Question 11

When should you use an Adjacency List?

Answer 11

1. Large Graphs
2. Sparse Graphs

Question 12

What is BFS used for?

Answer 12

BFS is used for finding the shortest path on an unweighted graph.

Question 13

What type of data structure does a BFS algorithm use?

Answer 13

The BFS algorithm uses a queue.

Question 14

What if the count of an index in BFS is not 0?

Answer 14

This means that there is an unvisited layer.

Question 15

What is a DFS algorithm used for.

Answer 15

The most fundamental algorithm used to explore nodes & Edged of a graph.

Question 16

What to BFS and DFS runtimes depend on?

Answer 16

They both depend on how the graph is represented.

Question 17

What are the runtimes for BFS?

Answer 17

1. Adjacency Matrix: Theta (V^2)
2. Adjacency List: Theta (V^2)

Question 18

What are the runtimes for DFS

Answer 18

1. Adjacency Matrix: Theta (V+E)
2. Adjacency List: Theta (V+E)

Question 19

Explain ‘Topological Sort’?

Answer 19

Topological sort takes a ‘directed’ graph and returns an array of the nodes where each node appears before all the nodes that it points to.

Question 20

What type of data structure does the Topological Sort algorithm use?

Answer 20

A min heap priority queue.

Question 21

Explain ‘Prim’s Algorithm’ and its runtime?

Answer 21

Prim’s Algorithm is used to construct a ‘minimum spanning tree’, which is the set of edges of the minimal cost that connects all edges.

Runtime: O(|E|lg|V|)

Question 22

Explain Dijkstra’s Algorithm and its runtime?

Answer 22

Dijkstra’s algorithm finds a single source shortest path across the graph.

Runtime: O(|E|lg|V|)

Question 23

Explain ‘Kruskal’s Algorithm’ and its runtime.

Answer 23

Kruskal’s algorithm sorts edges by weight and if two edges have the same weight, it puts the lower edge first.

Question 24

What algorithm does Kruskal’s Algorithm depend on?

Answer 24

Union-find

Question 25

Explain the ‘Union-find’ algorithm and its operations.

Answer 25

The union-find algorithm is used to detect cycles.

1. makeSet(x): Creates single node trees
2. union(x,y): Attaches the root of y’s subtree to the root of x’s subtree.
3. find(x): Follows the pointer chain from x to the root