We can find the minimum #202207081445 in 202204112129# and 202204112118#. However, the solution for digraph appears to be more difficult.
For undirected graph, if it is connected, then there will be a tree that connects all the vertices in the graph, that is the minimum spanning tree. The number of edges of the minimum spanning tree will be \(\vert V \vert - 1\) as \(V\) is the total number of edges of the undirected graph.
In an undirected graph, it could be solved by two algorithms:
Prism’s Algorithm is a #202204151143 which is used to solve #202204272006. It is pretty much the same to 202204151059#. The update rule for the algorithm could be simplified to \(d_w = \text{min}(d_w, c_{w,v})\) after vertex \(v\) is selected for each unknown \(w\) adjacent vertices. \(d\) denoted the weight of the edge.
Kruskal’s Algorithm is an #202204151143 which used to solve the #202204272006. It uses Disjoint Set as its basic data structure and utilises the Union or Find algorithm.