Graphs general Flashcards

1
Q

Representations: Set

A

“big buckets” of nodes and edges - edges store connecting node information

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

Representations: Adjacency list

A

Array of LinkedLists, where each list contains the indeces of nodes that that node is adjacent to

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

Representations: Adjacency matrix

A

2D array (size numNodes^2) containing whether two nodes are adjacent

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

Depth-first search

A

Starting at an inputted node, traverses and explores all “children” in the paths going out from that node

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

DFS: implementation ADT

A

Stack

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

Breadth-first search

A

Starting at an inputted node, explores the remainder of the graph by “radiating out”

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

BFS: Implementation ADT

A

Queue

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

Dijsktra’s (dyke-stra) shortest paths algorithm: (unweighted) Basic concept?

A

BFS

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

Dijsktra’s (dyke-stra) shortest paths algorithm: (directed) Basic concept?

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