DSA - Graphs & Graph Algorithms Flashcards
1
Q
How are GRAPHS formed?
A
Is formed of a set of vertices/nodes & a set of edges between them
2
Q
What is an unweighted & undirected Graph?
A
A Graph that points back & forth from each other and has no cost to traverse
3
Q
What is a unweighted & directed Graph?
A
A Graph that has no cost to traverse, but each edge can ONLY travel in 1 direction.
4
Q
What is an weighted & undirected Graph?
A
A Graph that has a cost to traverse between nodes, and has bi-directional edges.
(CAN TRAVERSE IN EITHER DIRECTION BETWEEN THE NODES)
5
Q
What is an weighted & directed Graph?
A
A Graph that has a cost to traverse, but each edge can ONLY travel in 1 direction.
6
Q
What algorithms are Graphs used in?
A
ROUTE FINIDING ALGORITHMS
7
Q
When is a Graph called SIMPLE?
A
- Has no self loops (EDGES CONNTED TO ITSELF)
- No more than ONE edge between any pair of nodes
8
Q
What is a Path?
A
A sequence of vertices v_1,…,v_n such that v_i & v_i+1 are connected by an edge for all 1<= i <= n-1
9
Q
What is a Cycle?
A
Is a non-empty path whose first vertex is the same as its last vertex
10
Q
When is a Path Simple?
A
If no Vertex appears Twice
- Except a cycle, where the first & last vertex may be the same
11
Q
When is a Undirected Graph Connected?
A
If every pair of vertices has a path connecting them
12
Q
What are the 2 connections for a Directed Graph?
A
Weakly Connected & Strongly Connected
13
Q
When is a Directed Graph Weakly Connected?
A
If for every 2 vertices A & B there is either a path From A to B OR B to A
14
Q
When is a Directed Graph Strongly Connected?
A
If there are paths leading both ways
15
Q
Difference Between Tree & Graph?
A
Tree can be viewed as a simple connected graph with no cycles & one node identified as a root
In a Graph, no one node has a greater influence then the rest of the graph unless specified otherwise.
(NO ROOT WHICH THERE IS A UNIQUE PATH TO EACH VERTEX)
|=> Does not make sense to speak of parents & children in a graph
16
Q
What are Neighbours?
A
Two Vertices connected by an Edge
17
Q
What does Adjacent mean?
A
Two edges with a vertex in common
18
Q
How can you implement a graph like a BST?
A
Must have an arbitrary number of pointer for each node in graph, due to having an arbitrary number of connection to a graph
19
Q
What is an Adjacency Matrix?
A
2D array / Matrix n*n where each cell G[v][w] contains information about the connection from vertex v to vertex w.
20
Q
In a Adjacency Matrix for an UNWEIGHTED GRAPHS what does G[v][w] = 1 mean?
A
There is an edge going from v to w
21
Q
In a Adjacency Matrix for an UNWEIGHTED GRAPHS what does G[v][w] = 0 mean?
A
There is no such edge (NO CONNECTION)
22
Q
In a Adjacency Matrix for an WEIGHTED GRAPHS what does G[v][w] = ∞ mean?
A
There is no such edge (NO CONNECTION)
∞ = (ANY LARGE NUM U WILL NEVER USE)
23
Q
In a Adjacency Matrix for an WEIGHTED GRAPHS what does G[v][w] = 0* mean?
A
Does not have SELF links so Zero
- other values possible depend on application
0 ALSO means I don’t need to go further to get to a node
24
Q
In a Adjacency Matrix for an WEIGHTED GRAPHS what does G[v][w] = x (ANY VAL) mean?
A
x (CAN BE ANY VALUE)is just the weight of the edge going from v to w
25
How do you know a graph is Undirected?
If G[v][w] = G[w][v] for all vertices v & w
26
What is Adjacency List?
Have an array N of n-many Linked List
(one list for every vertex )
27
Adjacency List for Unweighted Graph?
N[v] is the list of neighbours of v
(Neighbour if there is an edge between v and another one)
DON'T RECORD WEIGHT
28
Adjacency List for Weighted Graph?
N[v] is the neighbours of v together with the weight of the edge that connects them with v.
29
Comparison Between Adjacency Matrix(AM) & Adjacency List (AL)?
Checking if there is an edge v => w :
AM: Reading G[v][w] is O(1)
AL: Checks if w is in the list N[v]
(LINEAR SEARCH NOT THROUGH ALL NODE
ONLY NEIGHBOUR)
(COST DEPENDS ON THE DENSITY OF THE
GRAPH)
Allocated Space:
AM: n arrays of size n = O(n*n) = O(n^2) space
AL: n Linked List storing m edges; Total= O(m+n)
(EACH NODE HAS m NO. OF NEIGHBOURS
EDGES = NEIGHBOURS)
( SAVES MEMORY WHEN USING A LARGE
GRAPH)
Traversing Neighbours:
AM: Traversing all G[v][0],...,G[v][n-1] takes O(n) time
(ITERATE THROUGH ALL THE ELEMENTS OF
ROWS IN MATRIX)
AL: Traversing only the Linked List N[v]
(NOT LOOKING AT NON_EDGES, JUST
ITERATE THROUGH THE NODE)
30
What does SPARSE mean?
There are relatively few edges
Relatively few edges compared to number of Vertices
m/n is SMALL
If m is O(n) or LESS, Besides O(n^2)
Due to it being sparse, the allocated space of AL is much smaller than AM, Then traversing through Neighbours is faster than AM.
31
What does DENSE mean?
Has Lots of Edges
32
What is Shortest Path?
A to B is a path for which the sum of the weights are less than or equal to the sum of weights on another path of A to B.
33
How does Dijkstra's Algorithm work?
Maintaining certain data & Updating it as it goes to steadily increase the INFO about shortest path between nodes. Till Finally finds shortest path to destination node
34
What does d[w] represent?
Shortest distance from v to w so far
(HOLDS SHORTEST DISTANCE FROM v => w )
INDEX by NODE USING NODE NUMBERS
Order does not matter just need numbers to loop it up in an array
e.g=> Graph with 20 Nodes, numbered between 0-19
35
What does p[w] represent?
The PREDECESSOR on the path from w
INITIALLY, w itself
Identifies Node previous to w in its shortest path
36
What does f[w] represent?
Is the Computation of d[w] finished?
INITIALLLY FALSE
Identifies the shortest path that gets to w is shortest path overall
When TRUE, whatever path found to w is the length of the shortest path p[w] is the node before w
37
Dijkstra's Algorithm
set d[v] = 0
while there are unfinished vertices:
set w = YET unfinished vertex with smallest d[w]
set f[w] = true // CAUSE IT IS FINISHED
for every neighbour u of w:
if d[w] + weight(w,u) < d[u];
set d[u] = d[w] + weight(w,u) and p[u] = w
Where weight(w,u)=>is the weight of the edge w to u
38
What is a Spanning Tree
Minimal possible selection of edges that connects all vertices
DON'T CONTAIN ANT CYCLES
Throw away edges, where you throw away every edge where you can without breaking graph into disconnected part
39
What is a Minimum Spanning Tree?
Spanning Tree that the sum of weights of its edges is the minimal such
WE WANT TO LOOK FOR THE ONE WITH SMALLEST SUM OF WEIGHTS
40
Steps to Determine Dijkstra Time Complexity For Adjacency Matrix:
n = no. of Vertices , m= total no. of edges
DO THE FOLLOWING n TIMES:
a) Mark w as Finished, takes O(n)
// n times to mark nodes as finished
b) Update every Neighbour, takes O(n^2)
// Iterate through the row of w to find its neighbour
c) Find w which is unfinished & with the smallest d[w], takes O(n^2)
// Go through all nodes and check it is Unfinished & Find distance for the that node
OVERALL TIME COMPLEXITY is O(n^2)
41
Steps to Determine Dijkstra Time Complexity For Adjacency List:
n = no. of Vertices , m= total no. of edges
DO THE FOLLOWING n TIMES:
a) Mark w as Finished, takes O(n)
// n times to mark nodes as finished
b) Update every Neighbour, takes O(m)
// Update every edge
c) Find w which is unfinished & with the smallest d[w], takes O(n^2)
// Go through all nodes and check it is Unfinished & Find distance for the that node n * O(n)
OVERALL TIME COMPLEXITY is O(n^2)
where, m <= n^2
42
When is Adjacency List is more Suitable than Adjacency Matrix?
If a Graph is Sparse then it has only n edges, so it will only be O(n), so the list is suitable when graph is sparse than using matrix
43
Why is a dense graph O(n^2)?
Max case every node connects to each node so n*n where n is the no. of nodes
44
In Adjacency List how can you SPEED up step C:
-Find w which is unfinished & with the smallest d[w]
Use a MIN-priority Queue: Priority of u is d[u]
- Initialise queue by inserting all node into it with a priority of ∞, EXCEPT first value you put in
- Call deleteMin to find the unfinished node with smallest d[w]
45
What is the new complexity of Step C when u SPEED it up?
O(n*(cost of deleteMin) + m*(cost of update))
46
Using Binary Heap, When is it Ideal?
O(nlog(n) + mlog(n))
Sparse: O(nlog(n))
Dense: O(n^2*log(n))
Better when sparse because O(nlog(n)) < O(n^2) , so it quicker
But when it's dense list it's not suitable as O(n^2) is better than O(n^2*log(n))
UPDATE & deleteMin are in O(log(n))
47
Using Fibonacci Heap, When is it Ideal?
O(nlog(n) + m)
Sparse: O(nlog(n))
Dense: O(n^2)
Better when sparse because O(nlog(n)) < O(n^2) , so it quicker
But when it's dense list it doesn't matter as O(n^2) is the same as O(n^2)
UPDATE is O(1) & deleteMin are in O(log(n)), BOTH amortized
48
What is Heapify Time Complexity
O(n)
49
What is Inserting n-times Time Complexity?
O(nlog(n)) OR O(n)
50
Does Initialisation Processes (Heapify OR inserting n-times) affect Total Time Complexity?
NO
51
Can Adjacency Matrix be put it Priority Queue?
Yes but Won't change Complexity
52
Pseudocode for Adjacency Matrix:
dijkstrawithmatrix ( int [ ] [ ] G , int v , int z ) {
n = G . length ;
d = new int [ n ] ; p = new int [ n ] ; f =new bool [ n ] ;
for ( i n t w = 0 ; w < n ; w++) {
d [ w ] = i n f t y ; p [ w ] = w ; f [ w ] = f a l s e ;
}
d [ v ] = 0 ;
while ( t r u e ) {
w = minunfinished ( d , f ) ;
i f (w == −1)
b r e a k ;
f o r ( i n t u = 0 ; u < n ; u++)
u p d a t e (w , u , d , p ) ;
f [ w ] = t r u e ;
}
// compute r e s u l t s i n d e s i r e d form
return computeresult ( v , z , G , d , p ) ;
}
53
Pseudocode for Adjacency List:
dijkstra_with_lists(List[]N ,int vi ntz){
n=G.length;
d=new int[n];p=new int[n];
Q=new MinPriorityQueue();
for(intw=0;w
54
What is the IDEA for Jarnik-Prim Algortihm?
Iteratively extend the tree with an edge which has the smallest weight and which connects a yet unconnected node
55
Steps for Jarnik-Prim Algorithm?
- Intialise all the nodes to ∞
- Then Start from any Node
- Iterate through its neighbours and update its instances. Mark Start Node as Finished
- Find the Smallest Unfinished node in Current Tree
- Repeat for the other nodes
- Until all nodes are connected
56
Jarnik-Prim Algorithm for Finding Minimal Spanning Tree:
For each vertex w of the graph, keep track of the following:
-d[w] = current distance from the tree (Initially = ∞)
- p[w] = vertex which connects the tree (Initially= w)
- f[w] = has w been added to tree? (Initially = FALSE)
IDEA:
set d[0] = 0//vertex 0 can be replaced by another v
while there are unfinished vertices:
set w = yet unfinished vertex with smallest d[w]
set f[w] = true // when finished
for every neighbour u of w:
if wieght(w,u) < d[u]:
set d[u] = weight(w,u) and p[u] = w
// Update it to weight on edge not entire distance
USE SAME TABLE AS DIJKSTRA's
57
Code for min_unfinished AM ?
int min_unfinished ( int [ ] d , bool [ ] f ) {
int min = infty ;
int idx = −1;
for ( int i =0; i < d . length ; i ++) {
if ( ( notf [ i ] ) && d [ i ] < min ) {
idx = i ;
min = d [ i ]
}
}
return idx ;
}
58
Code for Update AM ?
void update (w , u , G , d , p ) {
if ( d [ w ] + G [ w ] [ u ] < d [ u ] ) {
d [ u ] = d [ w ] + G [ w ] [ u ] ;
p [ u ] = w ;
}
}
59
Prims Time Complexity?
SAME AS DIJKSTRA
Adjacency Matrices: O(n^2)
Adjacency List:
- Binary Heap : O((n+m)log n)
- Fibonacci Heap : O((nlog n)+m)
60
What is the Compare Prims & Dijkstra?
Prims can have negative weights on edges, Dijkstra can't
Everything else is exactly the same - COMPLEXITY
61
Idea of Kruskal's Algorithm?
Starting with a forest where every node in a graph is a separate tree
Greedily adds edges with min weights s.t each edge is between different trees
LOOKS AT ALL EDGES AND ADD THE ONE WITH THE SMALLEST WEIGHT
62
What is a forest?
A set of Trees
63
What is a Minimal spanning Forest?
Set of minimal Spanning Trees
64
Why is Kruskal Greedy?
-Always chooses the best edge to add at each step
- Finishes when no more edges can be added
65
What is Performance dependent on in KRUSKAL?
1) If an edge is between nodes in the same tree
2) If an edge is between 2 different Trees, which 2 Trees these are
66
What are the 3 Methods in UNION-FIND?
- makeSet(x)
- find(x)
- union(x,y)
67
What does makeSet(x) do?
Make a new set containing the element x
68
What does find(x) do?
Find the set x is an element of
69
What does union(x,y) do?
Merges the two sets that contain x&y into 1 set that contains union of the 2 sets
70
Idea of Union Find Naive ?
- makeSet(x)
==> Makes each every node a tree and its parents itself
- int find(x)
==> Check if v is its own parent if so returns v, otherwise Recursively does find until it finds parent[x]
e.g a => b =>c
find(a) => b is a's parent but not its own so then goes to c and c is its own parent.
- void union(a,b)
==> Identifies the sets of a,b, by doing find a & find b
==> if a!= b then b's parent becomes a
71
Problems with Naive Union Find?
- Deep Chains, sets can end up deep and narrow or linear (SIMILAR TO AN UNBALNCED BST)
- find(x) will need a linear search up long chain to find root
- union(x,y) just makes y the child of x. If y is a deeper tree than the first tree, this makes the resulting tree deeper and reduces find(x) performance
72
Solutions for Naive Union Find?
find(x) can be fixed, just sets the parent of all nodes on the path traversed to be the root. REDUCES find(x) cost for all future calls on any of those nodes
Just require an extra record to rank level of the tree rooted at each node or the size of the subtree rooted at each node
ONLY MAINTAIN THE DEPTH OR SIZE OF THE ROOT NODES
73
Changes of Union Find based on size?
makeSet(x)
- includes a list of size and for all nodes gives it a size of 1
union(x,y)
- after performing a!=b, checks if sizes of a is smaller than b's
-swaps a&b if is smaller than b (want to add smaller size to larger list )
- makes b's parent a
- Increases a's size to incorporate b's size
(size[a] += size[b]
74
Changes of Union Find based on rank?
makeSet(x)
- includes a list of rank and for all nodes gives it a rank of 0
union(x,y)
- after performing a!=b, checks rank of a is smaller than b's
-swaps a&b if a is smaller than b (want to add smaller size to larger list )
- makes b's parent a
- if rank of a & b are the same increase the rank of a by 1
- if not the same rank inserts smaller tree to larger one
75
Problem with rank?
Approximation:
UPPER BOUND of height of the tree
SO LOSES ACCURACY
Does not efficiently reduce the rank correctly because find(x) reduces the path lengths that would require path from all leaves to roots, rather than individual paths
76
Fix rank issue?
Use heuristic of tracking the upperbound of the depth, no change on the rank is made during find(x) call
77
Pro of sized based Union Find?
- Nothing extra done to find(x)
- Shortening the paths from root keeps the nodes in the same tree, so size doesn't change
78
Performance of Union Find?
- Trees can have height of O(n) so find(x) & union(x,y) have O(n) complexity
- Optimisation methods amortized complexity of each operation is θ( α(n))
α(n) is Reverse ackermann function (VERY SLOW GROWING) NOT EXCEED FOR ANY REALISTIC VALUE OF N
- AMORTISED upperbound complexity for all operations is O(1)
79
Idea of Kruskal's Algorithm?
- Create an empty list of edges called Result
- makeSet(n) for each node in G
- Create list E that stores sorted edges of G in increasing order
- for ever edge e = (u,v) in E, check if u,v don't have same find(x) value
- If the don't add edge to result and union(u,v)
- After for loops stops return result
80
KA COMPLEXITY?
e = no. of edges
- Sorting edges by weight is O(eloge)
- Linear search through edges which is O(1), thus for all edges O(e)
- Total complexity is O(eloge + e) = O(eloge)
e is at most n^2 where n is the number of nodes in the graph
81
KA complexity when e ≈ n^2
O(eloge) = O(e log(n^2)) = O(2e log(n)) =
O(e log(n))
82
KA complexity when graph is Sparse?
O(nlog(n))
- Sparse when it has n edges
83
KA complexity when graph is Dense?
O(n^2log(n))
- dense when it has n^2 edges
84
KA V Fib JP V AM JP
- KA & FJP have same complexity for sparse
O(nlog(n))
- Both JP methods are better than KA for dense graphs as n^2 < n^2log(n)
KA computes a spanning forest if graph is not connected or spanning tree if it is connected
(KA WILL RETURN 2 SEPARATE SPANNING TREES, FOR DISCONNECTED GRAPH, TOGETHER THEY MAKE SPANNING TREE)
THIS MAKES UP FOR HAVING NOT AS GOOD COMPLEXITY THAN
JP can ONLY calculate a spanning tree on Connected graph (GIVE DISCONNECTED GRAPH ONLY RETURNS CONNECT PARTS)
