Last Minute Flashcards
1
Q
topological sort
A
O(N+M) = O(V+E)
2
Q
DFS/BFS
A
O(M) = O(E) with adj. list.
O(V^2) for adj. matrix
3
Q
non weighted shortest path
A
O(N + M) with adjacency
4
Q
dijkstras
A
with heap O((N+M)lgN) = O(MlgN) = O(ElogV)
with adjlist O(Dv)
with adj matrix O(V^2) = O(N^2)
5
Q
all pairs shortest path
A
O(N^3) with N*O(N^2) dijkstras
with disjkstras heap O(MNlgN)
with dynamic programming we get O(N^3) with better constants
6
Q
transitive closuer
A
N DFS = O(N(N+M))
adj matrix O(N^3)
7
Q
prims-min spanning tree
A
O(ElogV) = O(MlogN)
8
Q
kurskals min spanning tree
A
O(ElogV) = O(MlogN)
9
Q
sum of all degrees for a graph
A
2M
10
Q
undirected graph
A
M <= (N(N-1))/2
11
Q
directed graph
A
M <= N(N-1)
12
Q
connected graph
A
M >= N -1
13
Q
tree
A
M = N -1
14
Q
Forrest
A
M<= N -1
15
Q
Binary tree with h levels
A
2^h -1 nodes
