Brainscape's Knowledge GenomeTM

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


See full index

Algorithms and Data Structures > Graphs > Flashcards

Graphs Flashcards

1
Q

examples of brute sorting algorithms for graphs

A

depth first search

breadth first search

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

examples of decrease and conquer algorithms for graphs

A

topological sort

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

which graphing algorithm can deal with cycles

A

topological sort

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

what is a path

A

sequence of vertices connected by edges

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

what is a cyccle

A

path whose first and last vertices are the same

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

what is an adjacency list

A

an array with each element containing a vertex

vertex has a linked list of all the nodes that it has a link to

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

does depth first search work for noth directed and undirected graphs

A

yes

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

what data structure is used when implementing depth first seatch

A

stack

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

how does depth first search algorithm work

A

follow edges as far as possible

if we encounter a node that has already been visited, retrace steps

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

time complexity of dfs

A

O(V+E)

vertices for the seen for loop
edges for the adjacency for loop

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

space complexity of dfs

A

O(V)

seen boolean array

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

what is dfs useful for

A

seeing if there is a path that exists between two nodes

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

what data structure is used for breadth first search

A

queue

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

what is bfs used for

A

to find shortest path between two nodes

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

time complexity of bf s

A

O(V+E)

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

how does bfs work

A

start at a node
visit all its neighbours
visit all their neighbours and so on

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

in which order foes BFS examine vertices

A

in increasing distance from the source vertex

18
Q

what does it mean if a graph is directed

A

the edges flow in one direction

19
Q

examples of directed graphs irl

A

games - legal moves
web pages - hyperlinks
streets - one way

20
Q

how do adjacency lists work for directed graphs

A

edges are listed in the directions they exist

21
Q

time complexity of topological sort

A

O(V+E)

22
Q

when is topological sorting useful

A

when some events have to occur before others can eg class prequisties

23
Q

what data structure has a topological order by nature

A

tree

24
Q

how does topological sort algorithm work

A

pick an unvisited node
do dfs exploring only unvisited nodes
add topological ordering back in reverse order

25
Q

what does DAG stand for

A

directed acyclic graph

26
Q

how can directed cycles be detected

A

do dfs from every vertex

keep track of whats been visited
if we visit the same node twice, there is a loop

27
Q

why does considering weights of paths matter

A

multiple hops could end up being cheaper than a single heavy weighted hop

28
Q

what is edge relaxation

A

when distanceTo [] array is updated with a shorted value path

29
Q

how does Dijkstra algorithm work

A

always expand on path with smallest weight

if new, shorter path found, relax edge

30
Q

does Dijskstra work on negative weights

A

no

31
Q

how does greedy best search work

A

uses a heuristic to estimate how far it is away from the destination vertex

Goes for minimum cost at each step, ignoring the cost of the edges

32
Q

how does the a* algorithm work

A

uses the dijkstra method of finding the value of the path so far

this gets added to

the estimated cost of the remainder of the path (greedy)

It picks the smallest of these

33
Q

what is a heuristic in greedy algorithm

A

some function that tells us how close we are to the goal node

34
Q

what does it mean for the heuristic to be admissible

A

NEVER overestimates the cost of a path

35
Q

what does it mean if a heuristic is consistent

A

cannot overestimate the cost of any individual path

in a single path:
heuristic - actual weight <= next heuristic

36
Q

why does underestimating the cost of a path in A* algorithm not lose optimality

A

this would just be the dijkstra algorithm

37
Q

which algorithm can be used to most efficiently determine the presence of a cycle in a given graph ?

A

depth first search

38
Q

how does an adjacency matrix work

A

it is a 2D array of VxV vertices, each row and column representing a vertex

the value of element[i][j] is 1 if there is an edge connecting vertices i and j

39
Q

trade off in adjacency matrix

A

extremely quick search

can take up a lot of space

40
Q

how does an adjacency list work

A

The index of the array represents a vertex and each element in its linked list represents the other vertices that form an edge with the vertex

Algorithms and Data Structures (19 decks)

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