Discover published sets by community

Purpose: To find the minimum spanning tree of a connected and undirected graph. Approach: It grows the spanning tree from an arbitrary start node by adding the cheapest possible connection to another node at each step.

Purpose: To order the vertices in a directed graph such that for every directed edge from vertex $A$ to vertex $B$, vertex $A$ comes before $B$ in the ordering. Approach: It uses Depth-First Search to explore nodes, and produces a topological ordering by recording the nodes in reverse postorder.

Purpose: To find shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). Approach: It is a dynamic programming algorithm that computes shortest paths between all pairs of vertices by trying each vertex as an intermediate vertex.

Purpose: To find the shortest paths between nodes in a graph, which may represent, for example, road networks. Approach: It uses a greed-based strategy that selects the unvisited vertex with the shortest distance so far at each step.

Purpose: To traverse or search a graph by exploring as far as possible along each branch before backtracking. Approach: It uses a stack, either as a recursion call stack or an explicit stack data structure, to keep track of unexplored edges.

Purpose: To compute shortest paths from a single source vertex to all other vertices in a weighted digraph. It is capable of handling graphs with negative weight edges. Approach: It relaxes each edge in the graph repeatedly to reach the minimum weight distance to reach each vertex.

Purpose: To compute the maximum flow in a network. Approach: It repeatedly finds augmenting paths between the source and the sink and increases the flow through them until no more augmenting paths can be found.

Purpose: To traverse or search a graph level by level, starting from a given node. Approach: It uses a queue to explore all of the neighbor nodes at the present depth before moving on to nodes at the next depth level.

Purpose: To find the shortest path between two nodes in a weighted graph, using a heuristic to guide its search. Approach: It combines aspects of Dijkstra's shortest path algorithm and the heuristic nature of Best-First-Search.