graphs

Question 1

adjacency matrix facts

Answer 1

Given two vertices u and v: find out whether u and v are adjacent –> O(1)

Given a vertex u: enumerate all neighbors of u –> O(n)

For all vertices: enumerate all neighbors of each vertex O(n^2)

memory space is O(n^2)

Question 2

adjacency list facts

Answer 2

Given two vertices u and v: find out whether u and v are adjacent –> degree of node O(n)

Given a vertex u: enumerate all neighbors of u –> degree of node O(n)

For all vertices: enumerate all neighbors of each vertex summations of all node degree O(m)

memory space is O(m)

better for sparse graphs

Question 3

when is a graph sparse?

Answer 3

a graph is spare is the number of edges is less than the number of nodes squared

Question 4

dijkstra’s algorithm

Answer 4

finding shortest path from node to node, traversing

time complexity: O(n log n + m log n(

Question 5

bellman-ford

Answer 5

shortest path, the one with going through each node and seeing if there can be a new shortest path by relaxing

time complexity O(m * n)

Question 6

kruskal’s algorithm

Answer 6

minimum spanning tree found by the next shortest absolute node that doesn’t create a cycle

Question 7

prim’s algorithm

Answer 7

minimum spanning tree found by the next shortest traversal

O(n^2) for dense graph
O(m log n) for sparse graph