Algorithms - Trees Flashcards
What is the minimum spanning tree?
A minimum spanning tree is a subgraph of a graph that includes all the vertices of the original graph, but contains zero cycles.
Thus, the minimum spanning tree represents the lowest-cost way to connect all points.
What is the shortest path?
The shortest path is the lowest-cost path between two nodes.
We can find this using Dijkstra’s or A* algorithm.
What is meant by topological sort?
Topological sort is an ordering of the nodes in the graph such that if there is an edge (u, v) in the graph, then u appears before v in the ordering.
How can we get the topological sort of a graph?
We can use recursive DFS to get the reverse topological sort of the graph, and then reverse it to get the true topological sort.
What is the general method of Prim’s algorithm?
First, we find an initial edge, which is the minimum cost edge of the entire graph.
Then, we need to repeatedly find the smallest edge connected to our selected vertices, until our minimum spanning tree is found.
What is Prim’s algorithm used for?
Prim’s algorithm is a greedy method to get us the minimum spanning tree of a connected graph G.
What is Dijkstra’s algorithm used for?
Dijkstra’s algorithm is a greedy method to get the shortest possible path from a starting to a terminal vertex.
What is the general method of Dijkstra’s algorithm?
We start by giving every vertex in the graph a value based on their distance from the initial vertex. For vertices that are not directly connected, we give them a value of infinity.
Then, we recursively select the shortest unvisited path. From this new point, we perform a process called relaxation - we say that if the distance of our current vertex + the distance to the next vertex is shorter than the existing distance in our array, we update that value.
We repeat this until we have visited every vertex, and at this point we have an array consisting of the shortest path to each vertex. From here, we can generate a path between the initial and terminal vertex to get our shortest path.
What is the general method of a Breadth First Search algorithm?
First, we visit our initial vertex.
Then, we explore this vertex, placing all vertices around it into a queue. The order does not matter.
Then, we will visit the next vertex in the queue, and also explore that vertex, placing all around it into the queue.
We repeat this over and over again until we have a list of visited vertices in the queue.
What is a BFS/DFS Spanning Tree?
A BFS/DFS Spanning Tree is a tree created in the process of performing a breath-first or depth-first search, where we treat the initial vertex as the root of a rooted tree, and have all explored vertices be subtrees of that vertex.
What is the general method of a Depth First Search algorithm?
First, we visit our initial vertex.
Then, we explore this vertex, selecting the first vertex in sight. If we find a vertex, we place it onto our stack, “suspending” it for now.
If we do not find a vertex, then we push the vertex off the stack, returning to our previous vertex.
DFS is almost as if we are taking a mad dash to every vertex until we hit a dead end.
What is the general method for Heapsort?
First, we treat the given array as if it were a tree. We do this using a level-based definition.
Then, we turn that tree into a heap using a max-heapify function. We know that the first element heap[0] is the maximum value, so we swap it with the final value in the array, and call that sorted.
We then recursively do this for n - 1 elements, until we have a fully sorted array.
What are the benefits and downsides to Heapsort?
Heapsort is not stable, so Mergesort is a better option if you’re looking for pure stability.
However, Heapsort is much faster, operating at a guaranteed worst-case complexity of O(n log n), which is very fast compared to Mergesort’s O(n) complexity.
Furthermore, Heapsort is inplace, making it very memory efficient, with a space complexity of O(1).
