Graphs

Question 1

examples of brute sorting algorithms for graphs

Answer 1

depth first search

breadth first search

Question 2

examples of decrease and conquer algorithms for graphs

Answer 2

topological sort

Question 3

which graphing algorithm can deal with cycles

Answer 3

topological sort

Question 4

what is a path

Answer 4

sequence of vertices connected by edges

Question 5

what is a cyccle

Answer 5

path whose first and last vertices are the same

Question 6

what is an adjacency list

Answer 6

an array with each element containing a vertex

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

Question 7

does depth first search work for noth directed and undirected graphs

Answer 7

yes

Question 8

what data structure is used when implementing depth first seatch

Answer 8

stack

Question 9

how does depth first search algorithm work

Answer 9

follow edges as far as possible

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

Question 10

time complexity of dfs

Answer 10

O(V+E)

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

Question 11

space complexity of dfs

Answer 11

O(V)

seen boolean array

Question 12

what is dfs useful for

Answer 12

seeing if there is a path that exists between two nodes

Question 13

what data structure is used for breadth first search

Answer 13

queue

Question 14

what is bfs used for

Answer 14

to find shortest path between two nodes

Question 15

time complexity of bf s

Answer 15

O(V+E)

Question 16

how does bfs work

Answer 16

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

Question 17

in which order foes BFS examine vertices

Answer 17

in increasing distance from the source vertex

Question 18

what does it mean if a graph is directed

Answer 18

the edges flow in one direction

Question 19

examples of directed graphs irl

Answer 19

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

Question 20

how do adjacency lists work for directed graphs

Answer 20

edges are listed in the directions they exist

Question 21

time complexity of topological sort

Answer 21

O(V+E)

Question 22

when is topological sorting useful

Answer 22

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

Question 23

what data structure has a topological order by nature

Answer 23

tree

Question 24

how does topological sort algorithm work

Answer 24

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

Question 25

what does DAG stand for

Answer 25

directed acyclic graph

Question 26

how can directed cycles be detected

Answer 26

do dfs from every vertex keep track of whats been visited if we visit the same node twice, there is a loop

Question 27

why does considering weights of paths matter

Answer 27

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

Question 28

what is edge relaxation

Answer 28

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

Question 29

how does Dijkstra algorithm work

Answer 29

always expand on path with smallest weight if new, shorter path found, relax edge

Question 30

does Dijskstra work on negative weights

Answer 30

no

Question 31

how does greedy best search work

Answer 31

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

Question 32

how does the a* algorithm work

Answer 32

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

Question 33

what is a heuristic in greedy algorithm

Answer 33

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

Question 34

what does it mean for the heuristic to be admissible

Answer 34

NEVER overestimates the cost of a path

Question 35

what does it mean if a heuristic is consistent

Answer 35

cannot overestimate the cost of any individual path in a single path: heuristic - actual weight <= next heuristic

Question 36

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

Answer 36

this would just be the dijkstra algorithm

Question 37

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

Answer 37

depth first search

Question 38

how does an adjacency matrix work

Answer 38

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

Question 39

trade off in adjacency matrix

Answer 39

extremely quick search can take up a lot of space

Question 40

how does an adjacency list work

Answer 40

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