实验3 贪心算法和回溯法
一、实验目的
1. 理解最小生成树算法——Prim算法和Kruskal算法的基本思想，学会编程实现这两种算法；
2. 理解并查集的特点与适用环境，学会使用并查集解决常见的问题；
3. 理解单源最短路径算法——Dijkstra算法的基本思想，学会编程实现Dijkstra算法；
4. 理解回溯法的基本思想，学会使用回溯法解决常见的问题。

二、实验内容
1. 编程实现Prim算法。

输入：顶点编号及边权重。

例：
0 1 10
0 2 15
1 2 50
输出：最小生成树。

例：
0 1 10
0 2 15
2. 在某个城市里住着n个人，现在给定关于这n个人的m条信息（即某2个人认识）。

假设所有认识的人一定属于同一个单位，请计算该城市最多有多少
单位？
输入：第1行的第1个值表示总人数，第2个值表示总信息数；第2行开始为具体的认识关系信息。

例：
10 4
2 3
4 5
4 8
5 8
输出：单位个数。

例：
7
3. 编程实现Kruskal算法。

输入：顶点编号及边权重。

例：0 1 10
0 2 15
1 2 50
输出：最小生成树。

例：
0 1 10
0 2 15
4. 编程实现Dijkstra算法。

输入：第1行第1个值表示顶点个数，第2个值表示边个数；第2行开始为边权重。

例：
5 7
0 1 10
0 3 30
0 4 100
1 2 50
2 4 10
3 2 20
3 4 60
输出：顶点0到每一个顶点的最短路径长度。

例：
0 10 50 30 60
5. 使用回溯法求解N皇后问题。

输入：皇后的个数。

例：
4
输出：每一个方案及总方案数。

例：0 1 0 0
0 0 0 2
3 0 0 0
0 0 4 0
----------------
0 0 1 0
2 0 0 0
0 0 0 3
0 4 0 0
----------------
总方案数为2。

6. 使用回溯法求解0-1背包问题。

输入：两个一维数组分别存储每一种物品的价值和重量，以及一个整数表示背包的总重量。

例：价值数组v[] = {6,3,6,5,4}，重量数组w[] = {2,2,4,6,5}，背包重量C=10。

输出：背包的最大总价值。

例：
最大总价值=15．。