Graphs, MSTs, Djjkstra's and Floyd-Warshall

Question 1

What is a graph?

Answer 1

A graph is a set of vertices (points), connected by edges (lines)

Question 2

What are directed and undirected graphs?

Answer 2

Undirected - you can follow any edge in any direction from the vertice
Directed - you HAVE to follow the direction of the edge

Question 3

What is a weighted and unweighted graph?

Answer 3

Unweighted - edges don’t have any value associated to them
Weighted - edges have a value associated to them

Question 4

What is adjacency in graphs?

Answer 4

Node B is adjacent to A if there is an edge from A to B

Question 5

What does paths and reachability mean in graphs?

Answer 5

A path from A to B is a sequence of vertices such that there is an edge from A to A1, from A1 to A2, etc… until you reach B
A vertex is reachable from A if there is a path from A to B

Question 6

What does cycle, acyclic and connected mean in graphs?

Answer 6

Cycle - path from a vertex to itself
Acyclic - does not have cycles
Connected - there is a path between every pair of vertices
For a directed graph:
Weakly connected - if the corresponding undirected graph is connected i.e. ignoring directions on edges, if it is connected, then it is considered to be ‘weakly’ connected
It is strongly connected if, for every ordered pair of vertices, there is a path that respects the directions of the edges, and that goes from v1 to v2.

Question 7

How can you implement a graph using an adjacency matrix?

Answer 7

Adjacency Matrix - store node in an array. Each node is associated with an integer. Represent information about the edges using a 2D array, where array [i] [j] == 1 if there is an edge from node with index i to the node with index j
For weighted graphs, place weights in the matrix

Question 8

What are the disadvantages of adjacency matrices?

Answer 8

Sparse graphs with few edges for number that possible result in many 0 entries.
If the number of nodes in the graph may change, matrix representation is too inflexible

Question 9

How can you implement a graph using an adjacency list?

Answer 9

For every vertex, keep a list of adjacent vertices
Keep a list of vertices, or keep them in a Map as keys and lists of adjacent vertices as values

Question 10

What is a spanning tree?

Answer 10

Input - connected, undirected graph
Output - a tree which connects all vertices in the graph using only the edges present in the graph

Question 11

What is a Minimum Spanning Tree?

Answer 11

Input - connected, undirected, weighted graph
Output - a spanning tree, which is minimum in the sense that the sum of weights of the edges is the smallest possible for any spanning tree

Question 12

What is Prim’s Algorithm and how does it work?

Answer 12

A method used to construct an MST
Start by picking any vertex (M)
Choose the shortest edge from M to any other vertex (N)
Add edge (M, N) to the MST
Loop:
Continue to add at every step a shortest edge from a vertex in the ‘MST so far’ to a vertex outside, until all vertices are in the MST

Question 13

How does Dijkstra’s Algorithm work?

Answer 13

Assume that weights are non-negative (though possibly zero)
Think of the weights, w(i, j), as distances, and the length of the path is the sum of the length of edges
Then, keep on taking the shortest path towards the objective goal. Once you have reached it, go back and explore every single possible option, from the very beginning. Keep doing this until every single node has been fully explored i.e. no options are left to be considered

Uses three sets of nodes: unseen, working and closed
Unseen - nodes we have not reached yet
Working - nodes on the Priority queue, and for which we have some path to them, but are still working on the best path to them, or where else we can reach from them
Closed - Nodes on teh closed list - these are ‘finished with’ as we have found the optimal path to reach them, and processed all the edges from them to other nodes

Question 14

What is the complexity of Dijkstra’s algorithm?

Answer 14

O((|V| + |E|) * log (|V|))

Question 15

What does d(i, j, k) mean in Floyd-Warshall?

Answer 15

Shortest distance between nodes i and j, but using only the nodes {1, …, k} as potential allowed intermediary points
e.g. d(2, 5, 3) = shortest distance from Node 2 to Node 5 using only {Node 1, Node 2, Node 3} as potential intermediate points

Question 16

How does the Floyd-Warshall algorithm work?

Answer 16

Start at the starting node. Then, using only direct edges, create a matrix which lists all direct connections between nodes that are in contact with each other. Any path that cannot be made as you would have to use another node, mark off for now. Proceed to then add another node, and update the matrix using the additional node to form more paths. Keep doing this, and updating as you go, until all nodes have been added. If there is a shorter path that has been discovered using the additional nodes, then update the number accordingly. Remember, you are only writing the minimum number at each update.
If there are directional edges, then follow that procedure accordingly.

Question 17

What is the complexity of Floyd-Warshall?

Answer 17

Have three nested loops, of ranges |V|, hence O(|V|^3)