Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CS YEAR ONE > DSA - Graphs & Graph Algorithms > Flashcards

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is an unweighted & undirected Graph?

A

A Graph that points back & forth from each other and has no cost to traverse

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What algorithms are Graphs used in?

A

ROUTE FINIDING ALGORITHMS

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a Cycle?

A

Is a non-empty path whose first vertex is the same as its last vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

When is a Undirected Graph Connected?

A

If every pair of vertices has a path connecting them

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What are the 2 connections for a Directed Graph?

A

Weakly Connected & Strongly Connected

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

When is a Directed Graph Strongly Connected?

A

If there are paths leading both ways

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What are Neighbours?

A

Two Vertices connected by an Edge

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What does Adjacent mean?

A

Two edges with a vertex in common

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

How do you know a graph is Undirected?

A

If G[v][w] = G[w][v] for all vertices v & w

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is Adjacency List?

A

Have an array N of n-many Linked List
(one list for every vertex )

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Adjacency List for Unweighted Graph?

A

N[v] is the list of neighbours of v
(Neighbour if there is an edge between v and another one)

DON’T RECORD WEIGHT

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Adjacency List for Weighted Graph?

A

N[v] is the neighbours of v together with the weight of the edge that connects them with v.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Comparison Between Adjacency Matrix(AM) & Adjacency List (AL)?

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

What does SPARSE mean?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

What does DENSE mean?

A

Has Lots of Edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

What is Shortest Path?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

How does Dijkstra’s Algorithm work?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

What does d[w] represent?

A

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
Q

What does p[w] represent?

A

The PREDECESSOR on the path from w

INITIALLY, w itself

Identifies Node previous to w in its shortest path

36
Q

What does f[w] represent?

A

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
Q

Dijkstra’s Algorithm

A

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
Q

What is a Spanning Tree

A

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
Q

What is a Minimum Spanning Tree?

A

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
Q

Steps to Determine Dijkstra Time Complexity For Adjacency Matrix:

A

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
Q

Steps to Determine Dijkstra Time Complexity For Adjacency List:

A

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
Q

When is Adjacency List is more Suitable than Adjacency Matrix?

A

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
Q

Why is a dense graph O(n^2)?

A

Max case every node connects to each node so n*n where n is the no. of nodes

44
Q

In Adjacency List how can you SPEED up step C:
-Find w which is unfinished & with the smallest d[w]

A

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
Q

What is the new complexity of Step C when u SPEED it up?

A

O(n(cost of deleteMin) + m(cost of update))

46
Q

Using Binary Heap, When is it Ideal?

A

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
Q

Using Fibonacci Heap, When is it Ideal?

A

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
Q

What is Heapify Time Complexity

A

O(n)

49
Q

What is Inserting n-times Time Complexity?

A

O(nlog(n)) OR O(n)

50
Q

Does Initialisation Processes (Heapify OR inserting n-times) affect Total Time Complexity?

A

NO

51
Q

Can Adjacency Matrix be put it Priority Queue?

A

Yes but Won’t change Complexity

52
Q

Pseudocode for Adjacency Matrix:

A

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
Q

Pseudocode for Adjacency List:

A

dijkstra_with_lists(List<Edge>[]N ,int vi ntz){
n=G.length;
d=new int[n];p=new int[n];
Q=new MinPriorityQueue();</Edge>

for(intw=0;w<n;w++){
d[w]=infinity;p[w]=w;
Q.add(w,d[w]);
}
d[v]=0;
Q.update(v,0);

while(Q.notEmpty()){
w=Q.deleteMin()
for(Edge:N[w]){ // iterate over edges to
neighbors
u=e.target;
if(d[w]+e.weight<d[u]){ // should we update?
d[u]=d[w]+e.weight;
p[u]=w;
Q.update(u,d[u]);
}
}
}
return computeresult(v,z,G,d,p);
}

classEdge{
// target node
int target;

int weight;
}

54
Q

What is the IDEA for Jarnik-Prim Algortihm?

A

Iteratively extend the tree with an edge which has the smallest weight and which connects a yet unconnected node

55
Q

Steps for Jarnik-Prim Algorithm?

A
  • 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
Q

Jarnik-Prim Algorithm for Finding Minimal Spanning Tree:

A

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
Q

Code for min_unfinished AM ?

A

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
Q

Code for Update AM ?

A

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
Q

Prims Time Complexity?

A

SAME AS DIJKSTRA
Adjacency Matrices: O(n^2)

Adjacency List:
- Binary Heap : O((n+m)log n)
- Fibonacci Heap : O((nlog n)+m)

60
Q

What is the Compare Prims & Dijkstra?

A

Prims can have negative weights on edges, Dijkstra can’t

Everything else is exactly the same - COMPLEXITY

61
Q

Idea of Kruskal’s Algorithm?

A

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
Q

What is a forest?

A

A set of Trees

63
Q

What is a Minimal spanning Forest?

A

Set of minimal Spanning Trees

64
Q

Why is Kruskal Greedy?

A

-Always chooses the best edge to add at each step
- Finishes when no more edges can be added

65
Q

What is Performance dependent on in KRUSKAL?

A

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
Q

What are the 3 Methods in UNION-FIND?

A
  • makeSet(x)
  • find(x)
  • union(x,y)
67
Q

What does makeSet(x) do?

A

Make a new set containing the element x

68
Q

What does find(x) do?

A

Find the set x is an element of

69
Q

What does union(x,y) do?

A

Merges the two sets that contain x&y into 1 set that contains union of the 2 sets

70
Q

Idea of Union Find Naive ?

A
  • 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
Q

Problems with Naive Union Find?

A
  • 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
Q

Solutions for Naive Union Find?

A

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
Q

Changes of Union Find based on size?

A

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
Q

Changes of Union Find based on rank?

A

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
Q

Problem with rank?

A

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
Q

Fix rank issue?

A

Use heuristic of tracking the upperbound of the depth, no change on the rank is made during find(x) call

77
Q

Pro of sized based Union Find?

A
  • Nothing extra done to find(x)
  • Shortening the paths from root keeps the nodes in the same tree, so size doesn’t change
78
Q

Performance of Union Find?

A
  • 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
Q

Idea of Kruskal’s Algorithm?

A
  • 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
Q

KA COMPLEXITY?

A

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
Q

KA complexity when e ≈ n^2

A

O(eloge) = O(e log(n^2)) = O(2e log(n)) =
O(e log(n))

82
Q

KA complexity when graph is Sparse?

A

O(nlog(n))
- Sparse when it has n edges

83
Q

KA complexity when graph is Dense?

A

O(n^2log(n))
- dense when it has n^2 edges

84
Q

KA V Fib JP V AM JP

A
  • 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)

CS YEAR ONE (16 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions