最小生成樹 (Minimum Spanning Tree)

• An MST is a subset of the edges of the connected, undirected graph that connect all the vertices together, in which there is no forming of a cycle and there should be minimum possible total edge weight.

  MST是已連接的無向圖的邊的子集，該邊將所有頂點連接在一起，其中不形成循環，因此總邊的權重應最小。

• In this weight of a tree is defined as the sum of the weight of all its edges which are connected but no formation of the cycle is there.

  在該樹中，樹的權重定義為樹的所有相連邊的權重之和，但沒有形成循環。

• A tree T is said to be a spanning tree of a connected graph X if T is a subgraph of X and T contains all vertices of X.

  如果T是X的子圖并且T包含X的所有頂點，則將樹T稱為連通圖X的生成樹。

生成樹的應用 (Application of Spanning Tree)

1. Spanning tree has wide applications in many areas like network design.

   生成樹在網絡設計等許多領域都有廣泛的應用。

2. Spanning tree is important in designing routing algorithms.

   生成樹在設計路由算法時很重要。

3. Practical application based on minimum spanning tree includes taxonomy and cluster analysis.

   基于最小生成樹的實際應用包括分類法和聚類分析。

1)Kruskal算法 (1) Kruskal’s Algorithm)

• It is an application of a greedy algorithm.

  它是貪婪算法的一種應用。

• In this edges are selected with minimum weight and added to MST till no cycle is formed.

  在這種情況下，以最小的重量選擇邊緣，并將其添加到MST中，直到沒有循環形成為止。

• It is used to find a minimum cost.

  它用于查找最低成本。

• It finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

  它找到形成樹的邊緣子集，該樹包括每個頂點，樹中所有邊緣的總權重最小。

• Kruskal algorithm does not form a tree at each step.

  Kruskal算法并非在每個步驟都形成一棵樹。

Steps for the kruskal’s algorithm are as follows:

kruskal算法的步驟如下：

1. Firstly arrange all the edges in increasing order of their weight.

   首先，以重量增加的順序排列所有邊緣。

2. Then the edges should be added if it does not form a circuit.

   如果沒有形成電路，則應添加邊緣。

3. Continue these steps till all the edges are visited and MST is formed.

   繼續這些步驟，直到訪問了所有邊緣并形成了MST。

4. Add the cost of all edges in MST to get a minimum cost of a spanning tree.

   在MST中添加所有邊的成本，以獲取生成樹的最低成本。

2)Prim的算法 (2) Prim’s algorithm)

• This algorithm generally focused on vertices.

  該算法通常集中在頂點上。

• Prim's algorithm always forms a tree at every step.

  Prim的算法總是在每一步都形成一棵樹。

• It applies the nearest neighbor method to select new edges.

  它應用最近鄰居方法來選擇新邊。

• This algorithm is generally used when we have to find a minimum cost of a dense graph because this number of edges will be high.

  當我們必須找到密集圖的最低成本時，通常會使用此算法，因為該邊緣數量很高。

• Basically, Prim's algorithm is faster than the Kruskal's algorithm in the case of the complex graph.

  基本上，在復雜圖的情況下，Prim算法比Kruskal算法更快。

Steps for the Prim’s algorithms are as follows:

Prim算法的步驟如下：

1. Start with a vertex, say u.

   從頂點開始，說u 。

2. Select another vertex v such that edges are formed from u and v and are of minimum weight, connect uv and add it to set of MST for edges A.

   選擇另一個頂點v ，以使邊緣由u和v形成并具有最小權重，連接uv并將其添加到邊緣A的MST集。

3. Now among the set of all vertices find other vertex v_i that is not included in A such that (v_i, v_j) is minimum labeled and is the nearest neighbor of all vertices in set A and it does not form a cycle, add it to A.

   現在，集所有頂點中找到其他頂點v _我是不包含在使得(V _{I，V j)}為最小的標記，是集合A中的所有頂點的近鄰，并沒有形成一個周期，加它到A。

4. Continue this process till we get an MST, then the MST formed will be of minimum cost.

   繼續執行此過程，直到獲得MST為止，然后形成的MST成本最低。

Reference: Kruskal's algorithm

參考： Kruskal算法

翻譯自: https://www.includehelp.com/algorithms/p-and-k-algorithms.aspx