Get started today!

Good to have you back!
If you've signed in to StudyBlue with Facebook in the past, please do that again.

- StudyBlue
- United Kingdom
- University of Bristol
- Mathematics And Computer Science
- Mathematics And Computer Science 101
- Lecturers
- DSA

James T.

Breadth-first search

- Computes the minimum distance from a source node 's' to every other node in the graph
- Directed or undirected
- Uses a
**QUEUE**structure - Runtime: O(V + E)

Depth-first search

- Computes the minimum distance from a source node 's' to every other node in the graph
- Directed or undirected
- Uses a
**STACK**structure - Runtime: O(V + E)

Advertisement
)

Topological sort

A linear ordering of nodes of an acyclic graph, such that for every directed edge *uv* from vertex *u *to vertex *v*, *u *comes before *v *in the ordering.

Dynamic Programming

- Characterise the structure of an
**optimal solution** **Recursively**define the value of an optimal solution- compute the value of an optimal solution in a
**bottom-up**fashion - construct an optimal solution from constructed information

Kruskal's algorithm

- Finds a minimum spanning tree or forest of a connected or disconnected graph
- Order the edges by increasing weight, go through this list, adding an edge if it does not create a cycle.
- runtime O(Elog(V))

Prim's algorithm

- Finds a minimum spanning tree of a connected, undirected graph
- Grow the tree by one edge at a time, pick the minimum edge connecting the tree to the vertices not in the tree
- runtime: O(V
^{2})

Bellman-Ford algorithm

- Finds the shortest path from a source node 's' to every other node in the graph
- Weighted, directed, negative edges ok
- AT MOST will iterate |V| - 1 times
- source vertex given path weight 0, all other vertices have path weight infinity. go through the vertices, looking at outward edges to find shorter paths to other evrtices.

Floyd-Warshal algorithm

- Finds the shortest path between
**all**pairs of vertices - weighted, directed graph, negative edges ok
- if (dist[i][j] > dist [i][k] + dist [k][j])
- O(|V|
^{3})

Dijkstra's algorithm

- Finds the shortest path from a source node 's' to every other node
- weighted, directed graph, negative edges not ok
- Set source, find path weights to neightbours, pick node with smallest weight, repeat
- runtime: O(|E| + |V|log|V|

QuickSort algorithm

O(n log n)

Heapsort

- runtime: O(n log n)

Advertisement

* The material on this site is created by StudyBlue users. StudyBlue is not affiliated with, sponsored by or endorsed by the academic institution or instructor.

"StudyBlue is great for studying. I love the study guides, flashcards and quizzes. So extremely helpful for all of my classes!"

Alice , Arizona State University"I'm a student using StudyBlue, and I can 100% say that it helps me so much. Study materials for almost every subject in school are available in StudyBlue. It is so helpful for my education!"

Tim , University of Florida"StudyBlue provides way more features than other studying apps, and thus allows me to learn very quickly!??I actually feel much more comfortable taking my exams after I study with this app. It's amazing!"

Jennifer , Rutgers University"I love flashcards but carrying around physical flashcards is cumbersome and simply outdated. StudyBlue is exactly what I was looking for!"

Justin , LSU