这学期总体来说学到不少东西，算法留了不少作业，现在整理一下。以备后用
一、Kruskal算法（最小生成树）
Input: A weighted connected undirected graph G=(V,E) with n vertices.
Output:The set of edges T of a minimum cost spanning trees weight
1.Sort the edges in E by nondecreasing weight
2.for each vertex v ∈V
3. MAKESET({v})
4.end for
5.T={}
6.while|T|<n-1
7. Let(x,y) be the next edge in E
8. if FIND(x)!=FIND(y) then
9. Add(x,y) to T
10. UNION(x,y)
11. end if
12.end while
以下用C#实现，其中树也在程序中写出，当然可以提供一个输入接口，不过我们重点在算法，就不写输入了。
using System;using System.Collections.Generic;using System.Text;
namespace FFind{ class Program { static int[] arr = new int[] { 0, 0, 0, 0, 0, 0 }; static edge[] graph = new edge[] { new edge(1, 2, 1), new edge(1, 3, 2), new edge(4, 6, 3), new edge(5, 6, 4), new edge(2, 3, 6), new edge(4, 5, 7), new edge(3, 4, 9), new edge(2, 4, 11), new edge(3, 5, 13) }; static void Main(string[] args) { Program pro = new Program(); for (int i = 0; i < 9; i++) { int x = graph[i].pre; int y = graph[i].tail; if (pro.Find(x) != pro.Find(y)) { Console.WriteLine("("+x+","+y+")"); pro.Uion(x,y); } } } struct edge { public int pre; public int tail; public int weight; public edge(int ppre, int ttail, int wweiht) { this.pre = ppre; this.tail = ttail; this.weight = wweiht; } } public int Find(int val) { int y=val; while (arr[y - 1] != 0) y = arr[y - 1]; return y;
} public void Uion(int valx, int valy) { int u = Find(valx); int v = Find(valy); arr[u - 1] = v; } }}
