Exploring Pathfinding Algorithms

What is Dijkstra's algorithm used for?

• Sorting a list of numbers efficiently.

• Finding the minimum spanning tree in a graph.

• Calculating the maximum flow in a network.

• Finding the shortest path in a graph.

List the main steps of Prim's algorithm.

• 1. Initialize the tree with a starting vertex. 2. Add the smallest edge connecting the tree to a new vertex. 3. Repeat until all vertices are included.

• Select the largest edge from the entire graph.

• Start with all vertices included.

• Add edges randomly until all vertices are connected.

Describe the process of Kruskal's algorithm.

• Kruskal's algorithm adds edges randomly until all vertices are connected.

• Kruskal's algorithm requires a complete graph to function properly.

• Kruskal's algorithm finds the maximum spanning tree by removing edges.

• Kruskal's algorithm finds the minimum spanning tree by sorting edges and adding them without forming cycles.

What are the common methods for graph representation?

• Adjacency list, adjacency matrix, edge list, incidence matrix

• Graph traversal methods

• Graph coloring techniques

• Graph algorithms for sorting

Define a minimum spanning tree.

• A minimum spanning tree is a tree that connects all vertices with the maximum total edge weight.

• A minimum spanning tree is a cycle that includes all edges in a graph.

• A minimum spanning tree is a tree that connects only some vertices in a graph.

• A minimum spanning tree is a tree that connects all vertices in a graph with the least total edge weight.

How does the efficiency of Prim's algorithm compare to Kruskal's algorithm?

• Prim's algorithm is always faster than Kruskal's algorithm.

• Prim's algorithm is more efficient for dense graphs, while Kruskal's algorithm is better for sparse graphs.

• Both algorithms have the same efficiency regardless of graph density.

• Kruskal's algorithm is more efficient for all types of graphs.

Provide a simple example of Prim's algorithm in action.

• Minimum spanning tree edges: AB (0), BC (2), CD (7)

• Minimum spanning tree edges: AB (3), BC (1), CD (4)

• Minimum spanning tree edges: AB (1), BC (2), CD (5)

• Minimum spanning tree edges: AB (2), BC (3), CD (6)

Provide a simple example of Kruskal's algorithm in action.

• BC, CD, DE

• AD, AE, BE

• Minimum spanning tree edges: AB, BC, AC

• AB, AC, AD

What is the time complexity of Dijkstra's algorithm?

• O((V + E) log V)

• O(V^2)

• O(E)

• O(V log V)

Explain how a priority queue is used in Dijkstra's algorithm.

• A priority queue is used to store all edges of the graph.

• A priority queue is used to sort all vertices in ascending order.

• A priority queue is used to find the maximum distance vertex.

• A priority queue is used to retrieve the vertex with the smallest tentative distance efficiently.