Brainscape's Knowledge GenomeTM

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


See full index

Data Structures and Algorithm Analysis (3345) > Graph Algorithms > Flashcards

Graph Algorithms Flashcards

1
Q

What are the 2 sets of graphs

A

V, set of vertices/nodes
E, set of edges/links

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

What is the degree of a vertex

A

The number of edges connected to it

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

What are digraphs

A

Directed graphs, edges are pointed

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

What is a simple path

A

All nodes are distinct

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

What is the sum of weights of paths called

A

Path cost

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

What is a graph without cycles called

A

Directed Acyclic Graph (DAG)

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

What is a connected graph

A

every node has a way to get to every other node

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

what is a complete graph

A

every single node is connected

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

what is a graph that has lots of edges vs few edges called

A

dense vs sparse

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

What is the 2D array representing a graph called

A

Adjacency Matrix

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

Can topological sorts have multiple answers

A

yes

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

What kind of graph are topological sorts for

A

DAGs

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

What is the topological sort algorithm

A

List the in-degree for all nodes and softly delete each node with 0 in-degree while decrementing what it is pointing, repeat

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

What is the time complexity of topological sort using a list

A

O(V^2)

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

What is the time complexity of topological sorting using a queue

A

O(E+V)

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

What is the time complexity of Dijkstra’s algorithm

A

O(ElogV)

17
Q

What kind of search is finding shortest path for unweighted graphs and what is the time complexity of

A

bread-first, O(E+V)

18
Q

What makes a digraph strongly connected

A

there is a path from any node to any other node

19
Q

What is the running time for unweighted shortest path using

A

O(v^2), O(E+V) if using level-order tree with queue and adjacency list

20
Q

What is the running time for Dijkstra’s algorithm for shortest path of weighted graph

A

O(E+V^2), or if using priority queue with decreaseKey then O(ElogV)

21
Q

What does does finding the minimal subset of edges result in

A

A tree (spanning tree problem)

22
Q

what is running time of Prim’s minimum spanning tree

A

O(V^2), or O(ElogV) with binary heaps

23
Q

when is Prim’s minimum spanning tree good to use

A

if the graph is dense

24
Q

what is running time of Kruskal’s algorithm

A

O(ElogE) using union/find with heap

25
Q

when is Kruskal’s algorithm good to use

A

if the graph is sparse

26
Q

an undirected graph is connected only if …

A

a DFS from any node visits every node

27
Q

what type of algorithm for graphs results in O(V^2), and what would make it better

A

greedy, using queues

Data Structures and Algorithm Analysis (3345) (7 decks)

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