Graph Flashcards
Fenwick tree - usage, complexity (create, update, search)
Usage: fast prefix sum
Space complexity: O(n)
Time complexity: create->O(nlogn), update all elements->O(logn), search->O(logn)
Binary tree - traversal methods (three) and how
Time complexity?
1) pre order (visit - left - right) (usual one)
2) in order (L-V-R)
3) post order (L-R-V)
Time complexity: O(n)
Binary tree - searching time (balanced/unbalanced)
Balance: O(logn)
Unbalanced: O(n)
Binary tree - insertion time complexity (balanced/unbalanced)
Balance: O(logn)
Unbalanced: O(n)
Topological sort - time complexity
Time: O(v+e)
Where v is the number of vertices and e is the number of edges
Topological sort - how does it work?
Prepare: set, stack
1) choose a random node
2) Mark the node as visited and put it into the set
3) explore its children and continue with step 2
4) if the node has no children, put it into the stack and go back
5) the stack order from top to the bottom is the final state of topological sort
Dijkstra’s algorithm - restriction
It can only work when there is no negative distance on edges.
Dijkstra’s algorithm - usage
Given a source node
Find all shortest path from that node to every other node
Dijkstra’s algorithm - space and time complexity
Time: O(elogv)
Space: O(e+v)
Where e is the number of edges and v is the number of vertices
DFS (cycle detection (directed graph)) - time complexity
Time: O(e+v)
Where e is the number of edges and v is the number of vertices
DFS (cycle detection (directed graph)) - how it works
Prepare: white set(not visit), grey set(visiting), black set(visited)
1) randomly pick a node from white set
2) do dfs while putting passed node into great set
3) if dfs find a node who is going to visit and also in the grey set, it is found
4) if not put the node in the black set so we are not going to visit again
Edges list (graph representation) - space complexity
Space: O(v+e)
Where v is the number of vertices and e is the number of edges
Edges list (graph representation) - how does it work?
1) create a class with starting and ending vertices and optionally adding value
2) store in a list..
struct edge { Int start; Int end; Int value; };
Vector list(n);
Edges list (graph representation) - time complexity of finding all adjacent node of given node
Time: O(n)
Where n is the size of edges list
Edges list (graph representation) - what is it?
I can’t believe you forgot about this important thing!
Go Google for photo.
Adjacency graph (graph representation) - space complexity
Space: O(v^2)
Where v is the number of vertices in the graph
Adjacency graph (graph representation) - time complexity on finding adjacent node and check two node connectivity
1) O(v)
2) O(1)
Graph representation - ways(3)
1) adjacency list - good
2) adjacency matrix - ok but consume space
3) vertices list- ok but time consuming on searching
Disjoint set (cycle detection (undirected graph)) - how it works?
1) create a set for every element
2) start union two set by edges
3) if their representative is not the same, combine them
Else, that edge make a cycle on the graph
Tree - root/node/leaf node/non-leaf node/ancestor/descendant/sibling/degree
Root - top of the tree/has no parent
Node - all other node except root
Leaf node - they don’t have child node
Non-leaf node - they have child node
Ancestor - all node from root to the given node (exclude given node)
Descendant - all node from given node to leaf node (exclude given node)
Sibling - two node having the same parent is called sibling
Degree - number of leaf node to the given node
AVL tree (self balancing binary tree) - rotations (4)
- RR -> rotate left
- LL -> rotate right
- LR -> rotate left and then right
- RL -> rotate right and then left
Binary tree - full / proper / strict binary tree
- each node has 0 or 2 children
Binary tree - complete binary tree
- all level of node are completely filled (except last level)
- node from the last level are filled from left to right
Binary tree - perfect binary tree
- all leaf node are on the same level
- all internal node has two children
Binary tree - degenerated binary tree
- all node has only 1 child
AVL tree (self balancing binary tree) - priorities
- the balancing factor of each node must be {-1,0,1}
- balancing factor = height of left subtree - height of right subtree
Red black tree (self balancing binary tree) - priorities
- root node has to be black
- there cannot be two consecutive red node
- the number of black node of every path from the node to (the node after leaf node = null) should be the same
Red black tree (self balancing binary tree) - insertion
if (tree == empty) {
create a root node with color black;
} else {
follow the instructions of binary insertion to create a node with red colour;
if (the parent of the created node == black) {
return;
} else {
if (the sibling node of the parent of the created node == red) {
the sibling node of the parent of the created node = black;
the parent of the created node = black;
if (the parent is above two node != root node) {
the parent is above two node = red;
recheck();
}
} else {
rotation();
recolour();
}
}
}
Binary tree - deletion (with no child node / one child node / two children node)
No - just delete it
One - replace the node with its child and delete the child node (recursively call until reach leaf node)
Two - choose inorder predecessor / inorder successor and replace it
Predecessor = the largest node from the left tree
Successor = the smaller node from the right tree
Spanning tree - what is spanning tree
- connected tree
- no cycle
- have same vertices as the original graph
- have v-1 edges
Prim’s algorithm (find minimum spanning tree) - how it works
1) remove loop and parallel
2) choose a random node to start with
3) choose the minimum edges connected to visited node
4) choose (|v|-1) edges and done
Kruskals algorithm (find minimum spanning tree) - how it works
1) remove loop and parallel
2) create a list of edges with given weight in increasing order
3) choose edges and form a graph without any cycle
4) choose (|v|-1) edges
Connected component - how to find
The number of call (dfs / bfs) to the graph = ans
Bellman Ford algorithm (single source shortest path) - time complexity
Time: O(ev)
Where e is the number of edges and v is the number of vertices
Bellman Ford algorithm (single source shortest path) - drawback
It cannot work on negative weighted cycle
Bellman Ford algorithm (single source shortest path) - how it works
1) list all the edges
2) relax all the edges for (|v|-1) times
Relax: d[u] = min(d[u], d[v]+c(u, v))
Floyd Warshell algorithm (all pair shortest path) - time and space complexity
Time - O(v^3)
Space - O(v^3)
Where v is the number of vertices
Floyd Warshell algorithm (all pair shortest path) - formula
Dk[i, j] = min(D(k-1)[i, k]+D(k-1)[k, j], D(k-1)[i, j])
Segment tree - usage
Perform range quiet and range update in O(logn) time
Segment tree - how to implement
1) create an array with 2n size
2) all leaf node are the original data
3) internal node will be the sum(or can be other with different situation) of theirs children
Segment tree - update time (point/range)
O(logn)
Last propagation (segment tree) - how
1) keep a tree with same size of the segment tree with 0
2) every time when the update range is not the leaf node - lazy tree will keep an pending update of the children
3) when every time reaches the node, the same node in lazy tree need to be checked
4) if 0 = no update, else update it with the (number x range) and pass the update to its children
Strongly connected component - ?
Only exists in directed graph
When two arbitrary node is selected, they will have a path
Tree - properties
Having only one connected component
Edges +1 = vertices