贪心算法本质
一个贪心算法总是做出当前最好的选择，也就是说，它期望通过局部最优选择从而得到全局最优的解决方案。
贪心算法在解决问题的策略上“目光短浅”，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心算法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。贪心算法能得到许多问题的整体最优解或整体最优解的近似解。
所谓贪心选择性质是指原问题的整体最优解可以通过一系列局部最优的选择得到。是运用贪心策略解决的问题在程序的运行过程中无回溯过程。根据贪心策略，一步一步地得到局部最优解。最终根据贪心策略，一步一步地得到局部最优解。
冒泡排序就使用了贪心算法，它的贪心策略就是每一次从剩下的序列中选一个最大的数，把这些选出来的数放在一起，就得到了从大到小的排序结果。
最优装载问题
该问题要求装载的物品的数量尽可能多，而船的容量是固定的，那么优先把重量小的物品放进去，在容量固定的情况下，装的物品最多。
采用重量最轻者先装的贪心选择策略，从局部最优达到全局最优，从而产生最优装载问题的最优解。
算法设计：
- 当载重量为定值c时，每件古董越小时，可装载的古董数量就越大。只要依次选择最小重量古董，直到不能再装为止。
- 把n个古董的重量从小到大排序，然后根据贪心策略尽可能多地选出古董，直到不能继续装为止，此时达到最优。
每个古董的重量如下表所示，海盗船的载重量c为30，那么在不打碎古董又不超过载重的情况下，要装入最多的古董。
-
因为贪心策略是每次选择重量最小的古董装入海盗船，因此可以按照古董重量非递减排序，排序后如下表所示。
-
按照贪心策略，每次选择重量最小的古董放入（tmp 代表古董的重量，ans 代表已装裁的古董个数）。
i=0，选择排序后的第 1 个，装入重量 tmp=2，不超过载重量 30，ans =1。
i=1，选择排序后的第 2 个，装入重量 tmp=2+3=5，不超过载重量 30，ans =2。
i=2，选择排序后的第 3 个，装入重量 tmp=5+4=9，不超过载重量 30，ans =3。
i=3，选择排序后的第 4 个，装入重量 tmp=9+5=14，不超过载重量 30，ans =4。
i=4，选择排序后的第 5 个，装入重量 tmp=14+7=21，不超过载重量 30，ans =5。
i=5，选择排序后的第 6 个，装入重量 tmp=21+10=31，超过载重量 30，算法结束。
即放入古董的个数为 ans=5 个。
运行代码：
//program 2-1
#include <iostream>
#include <algorithm>
const int N=1000005;
using namespace std;
double w[N]; //古董的重量数组
int main()
{
double c;
int n;
int m;
cin>>m;
while(m--)
{
cin>>c>>n;
for(int i=0; i<n; i++)
{
cin>>w[i]; //输入每个物品重量
}
// 可以利用 C++中的排序函数 sort（见附录 B），对古董的重量进行从小到大（非递减）排序。要使用此函数需引入头文件：
// #include <algorithm>
// 语法描述为：
// sort(begin, end)//参数 begin 和 end 表示一个范围，分别为待排序数组的首地址和尾地址
// sort 函数默认为升序
// 在本例中只需要调用 sort 函数对古董的重量进行从小到大排序：
sort(w,w+n); //按古董重量升序排序
double tmp=0.0;
int ans=0; // tmp为已装载到船上的古董重量，ans为已装载的古董个数
for(int i=0; i<n; i++)
{
tmp+=w[i];
if(tmp<=c)
ans++;
else
break;
}
cout<<ans<<endl;
}
return 0;
}
//输入
/*
请输入载重量 c 及古董个数 n：
30 8 //载重量 c 及古董的个数 n
请输入每个古董的重量，用空格分开：
4 10 7 11 3 5 14 2 //每个古董的重量，用空格隔开
*/
//输出
//能装入的古董最大数量为 Ans=5算法解析：
- 算法复杂度分析：
- 时间复杂度：首先需要按古董重量排序，调用 sort 函数，其平均时间复杂度为 O(nlogn)，输入和贪心策略求解的两个 for 语句时间复杂度均为 O(n)，因此时间复杂度为 O(n + nlog(n))
- 空间复杂度：程序中变量 tmp、ans 等占用了一些辅助空间，这些辅助空间都是常数阶的，因此空间复杂度为 O(1)
- 优化拓展：
- 为什么在没有装满的情况下，仍然是最优解？因为此算法要求装入最多数量，和价值无关，所以从重量小的开始装才能装入最多的数量。
- 如果想知道装入哪些古董，应当如何实现？
背包问题
假设山洞中有 n 种宝物，每种宝物有一定重量 w 和相应的价值 v，毛驴运载能力有限，只能运走 m 重量的宝物，一种宝物只能拿一样，宝物可以分割。那么怎么才能使毛驴运走宝物的价值最大呢？
答案是选择性价比（价值/重量）最高的宝物，如果可以达到运载重量m，那么一定能得到价值最大，即每次从剩下的宝物中选择性价比最高的宝物。
算法设计：
- 将 n 种宝物的重量和价值存储在结构体 three（包含重量、价值、性价比 3 个成员）中，同时求出每种宝物的性价比也存储在对应的结构体 three 中，将其按照性价比从高到低排序。采用 sum 来存储毛驴能够运走的最大价值，初始化为 0。
- 根据贪心策略，按照性价比从大到小选取宝物，直到达到毛驴的运载能力。每次选择性价比高的物品，判断是否小于 m（毛驴运载能力），如果小于 m，则放入，sum（已放入物品的价值）加上当前宝物的价值，m 减去放入宝物的重量；如果不小于 m，则取该宝物的一部分 m * p[i]，m=0，程序结束。m 减少到 0，则 sum 得到最大值。
有一批宝物的价值，价值和重量如表所示，毛驴的运载能力m=30。
-
按照性价比降序排序，排序后如下表所示：
-
每次选择性价比高的宝物放入：
第 1 次选择宝物 2，剩余容量 30−2=28，目前装入最大价值为 8。
第 2 次选择宝物 10，剩余容量 28−5=23，目前装入最大价值为 8+15=23。
第 3 次选择宝物 6，剩余容量 23−8=15，目前装入最大价值为 23+20=43。
第 4 次选择宝物 3，剩余容量 15−9=6，目前装入最大价值为 43+18=61。第 5 次选择宝物 5，剩余容量 6−5=1，目前装入最大价值为 61+8=69。
第 6 次选择宝物 8，发现上次处理完时剩余容量为 1，而 8 号宝物重量为 4，无法全部放入，那么可以采用部分装入的形式，装入 1 个重量单位，因为 8 号宝物的单位重量价值为1.5，因此放入价值 1×1.5=1.5，你也可以认为装入了 8 号宝物的 1/4，目前装入最大价值为69+1.5=70.5，剩余容量为 0。 -
构造最优解：
把这些放入的宝物序号组合在一起，就得到了最优解（2，10，6，3，5，8），其中最后一个宝物为部分装入（装了 8 号财宝的 1/4），能够装入宝物的最大价值为 70.5。
运行代码：
//program 2-2
#include<iostream>
#include<algorithm>
using namespace std;
const int M=1000005;
struct three{
double w;//每个宝物的重量
double v;//每个宝物的价值
double p;//性价比
}s[M];
//如果不使用自定义比较函数，那么sort函数排序时不知道按哪一项的值排序，因此采用自定义比较函数的办法实现宝物性价比的降序排序。
bool cmp(three a,three b)
{
return a.p>b.p;//根据宝物的单位价值从大到小排序
}
int main()
{
int n;//n 表示有n个宝物
double m ;//m 表示毛驴的承载能力
cout<<"请输入宝物数量n及毛驴的承载能力m ："<<endl;
cin>>n>>m;
cout<<"请输入每个宝物的重量和价值，用空格分开： "<<endl;
for(int i=0;i<n;i++)
{
cin>>s[i].w>>s[i].v;
s[i].p=s[i].v/s[i].w;//每个宝物单位价值
}
sort(s,s+n,cmp);// 前两个参数分别为待排序数组的首地址和尾地址，最后一个参数compare表示比较的类型
double sum=0.0;// sum 表示贪心记录运走宝物的价值之和
for(int i=0;i<n;i++)//按照排好的顺序贪心
{
if( m>s[i].w )//如果宝物的重量小于毛驴剩下的承载能力
{
m-=s[i].w;
sum+=s[i].v;
}
else//如果宝物的重量大于毛驴剩下的承载能力
{
sum+=m*s[i].p;//部分装入，m为剩余的装载能力，即还能装多少货物，s[i].p为单位重量价值，二者相乘为总价值。
break;
}
}
cout<<"装入宝物的最大价值Maximum value="<<sum<<endl;//输出装入宝物的最大价值
return 0;
}
//輸入
/*
6 19 //宝物数量，驴子的承载重量
2 8 //第 1 个宝物的重量和价值
6 1 //第 2 个宝物的重量和价值
7 9
4 3
10 2
3 4
*/
//输出
//Maxinum value=24.6算法解析：
-
算法复杂度分析：
- 时间复杂度：该算法的时间主要耗费在将宝物按照性价比排序上，采用的是快速排序，算法时间复杂度为 O(nlogn)
- 空间复杂度：空间主要耗费在存储宝物的性价比，空间复杂度为 O(n)
贪心策略是在每次取剩下物品里面性价比最高的物品，这样可以使得在相同重量条件下比选其他物品所得的价值更大，因此采用贪心策略能得到最优解。
-
优化拓展：
-
如果宝物不能分割，贪心算法是否能得到最优解？
不一定。有可能出现剩余容量，没有装满的情况。这种情况下可能存在刚好达到运载能力的选择方案，因此在宝物不可分割、没法装满的情况下，贪心算法并不能得到最优解，仅仅是最优解的近似解。
-
会议安排问题
会议安排的目的是能在有限的时间内召开更多的会议（任何两个会议不能同时进行）。在会议安排中，每个会议 i 都有起始时间 bi 和结束时间 e i，且 bi<ei，即一个会议进行的时间为半开区间[bi，ei）。如果[b i，ei）与[bj，ej）均在“有限的时间内”，且不相交，则称会议 i 与会议 j 相容的。也就是说，当 bi≥ej 或 bj≥ei 时，会议 i与会议 j 相容。会议安排问题要求在所给的会议集合中选出最大的相容活动子集，即尽可能在有限的时间内召开更多的会议。
尝试贪心策略：如果选择最早开始时间的会议，则如果会议持续时间很长，例如 8 点开始，却要持续 12 个小时，这样一天就只能安排一个会议；如果选择持续时间最短，则可能开始时间很晚，例如 19 点开始，20 点结束，这样也只能安排一个会议，所以我们最好选择那些开始时间要早，而且持续时间短的会议，即最早开始时间+持续时间最短，就是最早结束时间。
每次从剩下的会议中选择具有最早结束时间且与已安排的会议相容的会议安排。
算法设计：
- 初始化：将 n 个会议的开始时间、结束时间存放在结构体数组中（想一想，为什么不用两个一维数组分别存储？），如果需要知道选中了哪些会议，还需要在结构体中增加会议编号，然后按结束时间从小到大排序（非递减），结束时间相等时，按开始时间从大到小排序（非递增）；
- 根据贪心策略就是选择第一个具有最早结束时间的会议，用 last 记录刚选中会议的结束时间；
- 选择第一个会议之后，依次从剩下未安排的会议中选择，如果会议 i 开始时间大于等于最后一个选中的会议的结束时间 last，那么会议 i 与已选中的会议相容，可以安排，更新 last 为刚选中会议的结束时间；否则，舍弃会议 i，检查下一个会议是否可以安排。
原始的会议时间表：
排序后的会议时间表：
贪心选择过程：
-
首先选择排序后的第一个会议即最早结束的会议（编号为 2），用 last 记录最后一个被选中会议的结束时间，last=4。
-
检查余下的会议，找到第一个开始时间大于等于 last（last=4）的会议，子问题转化为从该会议开始，余下的所有会议。
从子问题中，选择第一个会议即最早结束的会议（编号为 3），更新 last 为刚选中会议的结束时间 last=7。
-
检查余下的会议，找到第一个开始时间大于等于 last（last=7）的会议，子问题转化为从该会议开始，余下的所有会议。
从子问题中，选择第一个会议即最早结束的会议（编号为 7），更新 last 为刚选中会议的结束时间 last=11。
-
检查余下的会议，找到第一个开始时间大于等于 last（last=11）的会议，子问题转化为从该会议开始，余下的所有会议。
从子问题中，选择第一个会议即最早结束的会议（编号为 10），更新 last 为刚选中会议的结束时间 last=14；所有会议检查完毕，算法结束。
-
从贪心选择的结果，可以看出，被选中的会议编号为{2，3，7，10}，可以安排的会议数量最多为 4。
运行代码：
//program 2-3
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct Meet
{
int beg; //会议的开始时间
int end; //会议的结束时间
int num; //记录会议的编号
}meet[1000]; //会议的最大个数为1000
class setMeet{
public:
void init();
void solve();
private:
int n,ans; // n:会议总数 ans: 最大的安排会议总数
};
//读入数据
void setMeet::init()
{
int s,e;
cout <<"输入会议总数："<<endl;
cin >> n;
int i;
cout <<"输入会议的开始时间和结束时间，以空格分开:"<<endl;
for(i=0;i<n;++i)
{
cin>>s>>e;
meet[i].beg=s;
meet[i].end=e;
meet[i].num=i+1;
}
}
bool cmp(Meet x,Meet y)
{
if (x.end == y.end)
return x.beg > y.beg;//结束时间相等时，按开始时间从大到小排序
return x.end < y.end;//按结束时间从小到大排序
}
void setMeet::solve()
{
sort(meet,meet+n,cmp); //对会议按结束时间排序
cout <<"排完序的会议时间如下:"<<endl;
int i;
cout <<"会议编号："<<" 开始时间 "<<" 结束时间"<<endl;
for(i=0; i<n;i++)
{
cout<< " " << meet[i].num<<"\t\t"<<meet[i].beg <<"\t"<< meet[i].end << endl;
}
cout <<"-------------------------------------------------"<<endl;
cout << "选择的会议的过程:" <<endl;
cout <<" 选择第"<< meet[0].num<<"个会议" << endl;//选中了第一个会议
ans=1;
int last = meet[0].end; //记录刚刚被选中会议的结束时间
for( i = 1;i < n;++i)
{
if(meet[i].beg>=last)
{ //如果会议i开始时间大于等于最后一个选中的会议的结束时间
ans++;
last = meet[i].end;
cout <<" 选择第"<<meet[i].num<<"个会议"<<endl;
}
}
cout <<"最多可以安排" <<ans << "个会议"<<endl;
}
int main()
{
setMeet sm;
sm.init();//读入数据
sm.solve();//贪心算法求解
return 0;
}
//输入
/*
输入会议总数：
10
输入会议的开始时间和结束时间，以空格分开：
3 6
1 4
5 7
2 5
5 9
3 8
8 11
6 10
8 12
12 14
*/
//输出
/*
排完序的会议时间如下：
会议编号 开始时间 结束时间
2 1 4
4 2 5
1 3 6
3 5 7
6 3 8
5 5 9
8 6 10
7 8 11
9 8 12
10 12 14
选择的会议的过程：
选择第 2 个会议
选择第 3 个会议
选择第 7 个会议
选择第 10 个会议
最多可以安排 4 个会议
*/算法解析：
- 算法复杂度分析：
- 时间复杂度：在该算法中，问题的规模就是会议总个数 n。显然，执行次数随问题规模的增大而变化。首先在成员函数 setMeet::init()中，输入 n 个结构体数据。输入作为基本语句，显然，共执行 n 次。而后在调用成员函数 setMeet::solve()中进行排序，易知 sort 排序函数的平均时间复杂度为 O(nlogn)。随后进行选择会议，贡献最大的为 if(meet[i].beg>=last)语句，时间复杂度为 O(n)，总时间复杂度为 O(n +nlogn)= O(nlogn)
- 空间复杂度：在该算法中，meet[]结构体数组为输入数据，不计算在空间复杂度内。辅助空间有 i、n、ans 等变量，则该程序空间复杂度为常数阶，即 O(1)
- 优化拓展：
- 有没有更好的办法，比如有更小的算法时间复杂度？
最短路径
给定有向带权图 G =（V，Ｅ），其中每条边的权是非负实数。此外，给定 V 中的一个顶点，称为源点。现在要计算从源到所有其他各顶点的最短路径长度，这里路径长度指路上各边的权之和。
算法设计：
Dijkstra 算法是解决单源最短路径问题的贪心算法，它先求出长度最短的一条路径，再参照该最短路径求出长度次短的一条路径，直到求出从源点到其他各个顶点的最短路径。
Dijkstra 算法的基本思想是首先假定源点为 u，顶点集合 V 被划分为两部分：集合 S和 V−S。初始时 S 中仅含有源点 u，其中 S 中的顶点到源点的最短路径已经确定。集合V−S 中所包含的顶点到源点的最短路径的长度待定，称从源点出发只经过 S 中的点到达V−S 中的点的路径为特殊路径，并用数组 dist[]记录当前每个顶点所对应的最短特殊路径长度。将其连接的 V−S 中的顶点加入到集合 S 中，同时更新数组 dist[]。一旦 S 包含了所有顶点，dist[]就是从源到所有其他顶点之间的最短路径长度。
- 数据结构。设置地图的带权邻接矩阵为 map[][]，即如果从源点 u 到顶点 i 有边，就令 map[u][i]等于<u，i>的权值，否则 map[u][i]=∞（无穷大）；采用一维数组 dist[i]
来记录从源点到 i 顶点的最短路径长度；采用一维数组 p[i]来记录最短路径上 i 顶点的前驱。 - 初始化。令集合 S={u}，对于集合 V−S 中的所有顶点 x，初始化 dist[i]=map[u][i]，如果源点 u 到顶点 i 有边相连，初始化 p[i]=u，否则 p[i]= −1。
- 找最小。在集合 V−S 中依照贪心策略来寻找使得 dist[j]具有最小值的顶点 t，即dist[t]=min（dist[j]|j 属于 V−S 集合），则顶点 t 就是集合 V−S 中距离源点 u 最近的顶点。
- 加入 S 战队。将顶点 t 加入集合 S 中，同时更新 V−S。
- 判结束。如果集合 V−S 为空，算法结束，否则转（6）。
- 借东风。在（3）中已经找到了源点到 t 的最短路径，那么对集合 V−S 中所有与顶点 t 相邻的顶点 j，都可以借助 t 走捷径。如果 dis[j]>dist[t]+map[t][j]，则 dist[j]=dist[t]+map[t][j]，记录顶点 j 的前驱为 t，有 p[j]= t，转（3）。
由此，可求得从源点 u 到图 G 的其余各个顶点的最短路径及长度，也可通过数组 p[]逆向找到最短路径上经过的城市。
算法步骤如下。
初始景点地图：
设置地图的带权邻接矩阵为 map[][]，即如果从顶点 i 到顶点 j 有边，则 map[i][j]等于<i,j>的权值，否则 map[i][j]=∞（无穷大）:
令集合 S={1}，V−S={2，3，4，5}，对于集合 V−S 中的所有顶点 x，初始化最短距离数组 dist[i]=map[1][i]，dist[u]=0，如图 2-12 所示。如果源点 1 到顶点 i 有边相连，初始化前驱数组 p[i]=1，否则 p[i]= −1，如图 2-13 所示：
在集合 V−S={2，3，4，5}中，依照贪心策略来寻找 V−S 集合中 dist[]最小的顶点 t，如图 2-14 所示。
找到最小值为 2，对应的结点 t=2。
将顶点 t=2 加入集合 S 中 S={1，2}，同时更新 V−S={3，4，5}，如图 2-15 所示。
刚刚找到了源点到 t=2 的最短路径，那么对集合 V−S 中所有 t 的邻接点 j，都可以借助 t 走捷径。我们从图或邻接矩阵都可以看出，2 号结点的邻接点是 3 和 4 号结点，如图 2-16 所示。
先看 3 号结点能否借助 2 号走捷径：dist[2]+map[2][3]=2+2=4，而当前 dist[3]=5>4，因此可以走捷径即 2—3，更新 dist[3]=4，记录顶点 3 的前驱为 2，即 p[3]= 2。
再看 4 号结点能否借助 2 号走捷径：如果 dist[2]+map[2][4]=2+6=8，而当前 dist[4]=∞>8，因此可以走捷径即 2—4，更新 dist[4]=8，记录顶点 4 的前驱为 2，即 p[4]= 2。
更新后如图 2-17 和图 2-18 所示。
在集合 V−S={3，4，5}中，依照贪心策略来寻找 dist[]具有最小值的顶点 t，依照贪心策略来寻找 V−S 集合中 dist[]最小的顶点 t，如图 2-19 所示。
找到最小值为 4，对应的结点 t=3。
将顶点 t=3 加入集合 S 中 S={1，2，3}，同时更新 V−S={4，5}，如图 2-20 所示。
刚刚找到了源点到 t =3 的最短路径，那么对集合 V−S 中所有 t 的邻接点 j，都可以借助t 走捷径。我们从图或邻接矩阵可以看出，3 号结点的邻接点是 4 和 5 号结点。
先看 4 号结点能否借助 3 号走捷径：dist[3]+map[3][4]=4+7=11，而当前 dist[4]=8<11，比当前路径还长，因此不更新。
再看 5 号结点能否借助 3 号走捷径：dist[3]+map[3][5]=4+1=5，而当前 dist[5]=∞>5，因此可以走捷径即 3—5，更新 dist[5]=5，记录顶点 5 的前驱为 3，即 p[5]=3。
更新后如图 2-21 和图 2-22 所示。
在集合 V−S={4，5}中，依照贪心策略来寻找 V−S 集合中 dist[]最小的顶点 t，如图 2-23 所示。
找到最小值为 5，对应的结点 t=5。
将顶点 t=5 加入集合 S 中 S={1，2，3，5}，同时更新 V−S={4}，如图 2-24 所示。
刚刚找到了源点到 t =5 的最短路径，那么对集合 V−S 中所有 t 的邻接点 j，都可以借助 t 走捷径。我们从图或邻接矩阵可以看出，5 号结点没有邻接点，因此不更新。
在集合 V−S={4}中，依照贪心策略来寻找 dist[]最小的顶点 t，只有一个顶点，所以很容易找到。
找到最小值为 8，对应的结点 t=4。
V−S={ }为空时，算法停止。
由此，可求得从源点 u 到图 G 的其余各个顶点的最短路径及长度，也可通过前驱数组p[]逆向找到最短路径上经过的城市。
例如，p[5]=3，即 5 的前驱是 3；p[3]=2，即 3 的前驱是 2；p[2]=1，即 2 的前驱是 1；p[1]= −1，1 没有前驱，那么从源点 1 到 5 的最短路径为 1—2—3—5。
运行代码：
//program 2-4
#include <iostream>
#include<windows.h>
#include<stack>
using namespace std;
const int N=100; // 城市的个数可修改
const int INF=1e7; // 无穷大10000000
int map[N][N],dist[N],p[N],n,m;//n城市的个数，m为城市间路线的条数
bool flag[N]; //如果s[i]等于true，说明顶点i已经加入到集合S;否则顶点i属于集合V-S
void Dijkstra(int u)
{
for(int i=1; i<=n; i++)
{
dist[i] =map[u][i]; //初始化源点u到其他各个顶点的最短路径长度
flag[i]=false;
if(dist[i]==INF)
p[i]=-1; //源点u到该顶点的路径长度为无穷大，说明顶点i与源点u不相邻
else
p[i]=u; //说明顶点i与源点u相邻，设置顶点i的前驱p[i]=u
}
dist[u] = 0;
flag[u]=true; //初始时，集合S中只有一个元素：源点u
for(int i=1; i<=n; i++)
{
int temp = INF,t = u;
for(int j=1; j<=n; j++) //在集合V-S中寻找距离源点u最近的顶点t
if(!flag[j]&&dist[j]<temp)
{
t=j;
temp=dist[j];
}
if(t==u) return ; //找不到t，跳出循环
flag[t]= true; //否则，将t加入集合
for(int j=1;j<=n;j++)//更新与t相邻接的顶点到源点u的距离
if(!flag[j]&& map[t][j]<INF)
if(dist[j]>(dist[t]+map[t][j]))
{
dist[j]=dist[t]+map[t][j] ;
p[j]=t ;
}
}
}
void findpath(int u)
{
int x;
stack<int>s;
cout<<"源点为："<<u<<endl;
for(int i=1;i<=n;i++)
{
x=p[i];
while(x!=-1)
{
s.push(x);
x=p[x];
}
cout<<"源点到其它各顶点最短路径为：";
while(!s.empty())
{
cout<<s.top()<<"--";
s.pop();
}
cout<<i<<";最短距离为："<<dist[i]<<endl;
}
}
int main()
{
int u,v,w,st;
system("color 0d");
cout << "请输入城市的个数："<<endl;cin >> n;
cout << "请输入城市之间的路线的个数:"<<endl;cin >>m;
cout << "请输入城市之间的路线以及距离："<<endl;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
map[i][j]=INF;//初始化邻接矩阵为无穷大
}
while(m--)
{
cin >> u >> v >> w;
map[u][v] =min(map[u][v],w); //邻接矩阵储存，保留最小的距离
}
cout <<"请输入小明所在的位置:"<<endl; ;
cin >> st;
Dijkstra(st);
cout <<"小明所在的位置:"<<st<<endl;
for(int i=1;i<=n;i++)
{
cout <<"小明:"<<st<<" - "<<"要去的位置:"<<i;
if(dist[i] == INF)
cout << "sorry,无路可达"<<endl;
else
cout << " 最短距离为:"<<dist[i]<<endl;
}
findpath(st);
return 0;
}
//输入
/*
请输入城市的个数：
5
请输入城市之间的路线的个数：
11
请输入城市之间的路线以及距离：
1 5 12
5 1 8
1 2 16
2 1 29
5 2 32
2 4 13
4 2 27
1 3 15
3 1 21
3 4 7
4 3 19
请输入小明所在的位置：
5
*/
//输出
/*
小明所在的位置：5
小明:5 - 要去的位置:1 最短距离为：8
小明:5 - 要去的位置:2 最短距离为：24
小明:5 - 要去的位置:3 最短距离为：23
小明:5 - 要去的位置:4 最短距离为：30
小明:5 - 要去的位置:5 最短距离为：0
*/因为我们在程序中使用 p[]数组记录了最短路径上每一个结点的前驱，因此除了显示最短距离外，还可以显示最短路径上经过了哪些城市，可以增加一段程序逆向找到该最短路径上的城市序列。
void findpath(int u)
{
int x;
stack<int>s;//利用 C++自带的函数创建一个栈 s，需要程序头部引入#include<stack>
cout<<"源点为："<<u<<endl;
for(int i=1;i<=n;i++)
{
x=p[i];
while(x!=-1)
{
s.push(x);//将前驱依次压入栈中
x=p[x];
}
cout<<"源点到其他各顶点最短路径为：";
while(!s.empty())
{
cout<<s.top()<<"--";//依次取栈顶元素
s.pop();//出栈
}
cout<<i<<";最短距离为："<<dist[i]<<endl;
}
}只需要在主函数末尾调用该函数：
findpath(st);//主函数中 st 为源点
//输出结果如下
/*
源点为：5
源点到其他各顶点最短路径为：5--1；最短距离为：8
源点到其他各顶点最短路径为：5--1--2；最短距离为：24
源点到其他各顶点最短路径为：5--1--3；最短距离为：23
源点到其他各顶点最短路径为：5--1--3--4；最短距离为：30
源点到其他各顶点最短路径为：5；最短距离为：0
*/算法解析：
-
算法复杂度分析：
- 时间复杂度：在 Dijkstra 算法描述中，一共有 4 个 for 语句，第①个 for 语句的执行次数为 n，第②个 for 语句里面嵌套了两个 for 语句③、④，它们的执行次数均为 n，对算法的运行时间贡献最大，当外层循环标号为 1 时，③、④语句在内层循环的控制下均执行 n 次，外层循环②从 1～n。因此，该语句的执行次数为 n*n= n²，算法的时间复杂度为 O(n²)
- 空间复杂度：由以上算法可以得出，实现该算法所需要的辅助空间包含为数组 flag、变量 i、j、t 和 temp 所分配的空间，因此，空间复杂度为 O(n)
-
优化拓展：
-
在 for 语句③中，即在集合 V−S 中寻找距离源点 u 最近的顶点 t，其时间复杂度为 O(n)，如果我们使用优先队列，则可以把时间复杂度降为 **O(log n)**那么如何使用优先队列呢？
//program 2-4-1 #include <queue> #include <iostream> #include<cstring> #include<windows.h> using namespace std; const int N = 100; // 城市的个数可修改 const int INF = 1e7; // 无穷大 int map[N][N],dist[N],n,m; int flag[N]; struct Node{ int u,step; Node(){}; Node(int a,int sp){ u=a;step=sp; } bool operator < (const Node& a)const{ // 重载 < return step>a.step; } }; void Dijkstra(int st){ priority_queue <Node> Q; // 优先队列优化 Q.push(Node(st,0)); memset(flag,0,sizeof(flag));//初始化flag数组为0 for(int i=1;i<=n;++i) dist[i]=INF; // 初始化所有距离为，无穷大 dist[st]=0; while(!Q.empty()) { Node it=Q.top();//优先队列队头元素为最小值 Q.pop(); int t=it.u; if(flag[t])//说明已经找到了最短距离，该结点是队列里面的重复元素 continue; flag[t]=1; for(int i=1;i<=n;i++) { if(!flag[i]&&map[t][i]<INF){ // 判断与当前点有关系的点，并且自己不能到自己 if(dist[i]>dist[t]+map[t][i]) { // 求距离当前点的每个点的最短距离,进行松弛操作 dist[i]=dist[t]+map[t][i]; Q.push(Node(i,dist[i]));// 把更新后的最短距离压入优先队列，注意：里面的元素有重复 } } } } } int main() { int u,v,w,st; system("color 0d");//设置背景及字体颜色 cout << "请输入城市的个数："<<endl; cin >> n; cout << "请输入城市之间的路线的个数:"<<endl; cin >>m; for(int i=1;i<=n;i++)//初始化图的邻接矩阵 for(int j=1;j<=n;j++) { map[i][j]=INF;//初始化邻接矩阵为无穷大 } cout << "请输入城市之间u,v的路线以及距离w："<<endl; while(m--) { cin>>u>>v>>w; map[u][v]=min(map[u][v],w); //邻接矩阵储存，保留最小的距离 } cout<<"请输入小明所在的位置:"<<endl; ; cin>>st; Dijkstra(st); cout <<"小明所在的位置:"<<st<<endl; for(int i=1;i<=n;i++) { cout <<"小明:"<<st<<"--->"<<"要去的位置:"<<i; if(dist[i]==INF) cout << "sorry,无路可达"<<endl; else cout << " 最短距离为:"<<dist[i]<<endl; } return 0; }
-
哈夫曼编码
通常的编码方法有固定长度编码和不等长度编码两种。这是一个设计最优编码方案的问题，目的是使总码长度最短。这个问题利用字符的使用频率来编码，是不等长编码方法，使得经常使用的字符编码较短，不常使用的字符编码较长。如果采用等长的编码方案，假设所有字符的编码都等长，则表示 n 个不同的字符需要[log n]位。例如，3 个不同的字符 a、b、c，至少需要 2 位二进制数表示，a 为 00，b 为 01，c 为 10。如果每个字符的使用频率相等，固定长度编码是空间效率最高的方法。
-
编码尽可能短
我们可以让使用频率高的字符编码较短，使用频率低的编码较长，这种方法可以提高压缩率，节省空间，也能提高运算和通信速度。即频率越高，编码越短。
-
不能有二义性
例如，ABCD 四个字符如果编码如下。
A：0。B：1。C：01。D：10。
那么现在有一列数 0110，该怎样翻译呢？是翻译为 ABBA，ABD，CBA，还是 CD？那么如何消除二义性呢？解决的办法是：任何一个字符的编码不能是另一个字符编码的前缀，即前缀码特性。
算法设计：
哈夫曼算法采取的贪心策略是每次从树的集合中取出没有双亲且权值最小的两棵树作为左右子树，构造一棵新树，新树根节点的权值为其左右孩子结点权值之和，将新树插入到树的集合中，求解步骤如下。
- 确定合适的数据结构。编写程序前需要考虑的情况有：
- 哈夫曼树中没有度为 1 的结点，则一棵有 n 个叶子结点的哈夫曼树共有 2n−1 个结点（n−1 次的“合并”，每次产生一个新结点），
- 构成哈夫曼树后，为求编码，需从叶子结点出发走一条从叶子到根的路径。
- 译码需要从根出发走一条从根到叶子的路径，那么我们需要知道每个结点的权值、双亲、左孩子、右孩子和结点的信息。
- 初始化。构造 n 棵结点为 n 个字符的单结点树集合 T={t1，t2，t3，…，t n}，每棵树只有一个带权的根结点，权值为该字符的使用频率。
- 如果 T 中只剩下一棵树，则哈夫曼树构造成功，跳到步骤（6）。否则，从集合 T中取出没有双亲且权值最小的两棵树 t i 和 t j，将它们合并成一棵新树 zk，新树的左孩子为 t i，右孩子为 t j，zk 的权值为 t i 和 t j 的权值之和。
- 从集合 T 中删去 t i，t j，加入 zk。
- 重复以上（3）～（4）步。
- 约定左分支上的编码为“0”，右分支上的编码为“1”。从叶子结点到根结点逆向求出每个字符的哈夫曼编码，从根结点到叶子结点路径上的字符组成的字符串为该叶子结点的哈夫曼编码。算法结束。
下图是一些字符和它们的使用频率：
我们可以把每一个字符作为叶子，它们对应的频率作为其权值，为了比较大小方便，可以对其同时扩大 100 倍，得到 a～f 分别对应 5、32、18、7、25、13。
-
初始化。构造 n 棵结点为 n 个字符的单结点树集合 T={a，b，c，d，e，f}，如图 2-33 所示。
-
从集合 T 中取出没有双亲的且权值最小的两棵树a 和 d，将它们合并成一棵新树 t1，新树的左孩子为 a，右孩子为 d，新树的权值为 a 和 d 的权值之和为 12。新树的树根 t1 加入集合 T，a 和 d 从集合T中删除，如图 2-34 所示。
-
从集合 T 中取出没有双亲的且权值最小的两棵树 t1 和 f，将它们合并成一棵新树 t2，新树的左孩子为 t1，右孩子为 f，新树的权值为 t1 和 f 的权值之和为 25。新树的树根 t2 加入集合 T，将 t1 和 f 从集合 T 中删除，如图 2-35 所示。
-
从集合 T 中取出没有双亲且权值最小的两棵树 c 和 e，将它们合并成一棵新树 t3，新树的左孩子为 c，右孩子为 e，新树的权值为 c 和 e 的权值之和为 43。新树的树根 t3 加入集合 T，将 c 和 e 从集合 T 中删除，如图 2-36 所示。
-
从集合 T 中取出没有双亲且权值最小的两棵树 t2和 b，将它们合并成一棵新树 t4，新树的左孩子为 t2，右孩子为 b，新树的权值为 t2 和 b 的权值之和为 57。新树的树根t4 加入集合 T，将 t2 和 b 从集合 T 中删除，如图 2-37 所示。
-
从集合 T 中取出没有双亲且权值最小的两棵树 t3和 t4，将它们合并成一棵新树 t5，新树的左孩子为 t4，右孩子为 t3，新树的权值为 t3 和 t4的权值之和为 100。新树的树根 t5 加入集合 T，将 t3 和 t4 从集合 T 中删除，如图 2-38所示。
-
T 中只剩下一棵树，哈夫曼树构造成功。
-
约定左分支上的编码为“0”，右分支上的编码为“1”。从叶子结点到根结点逆向求出每个字符的哈夫曼编码，从根结点到叶子结点路径上的字符组成的字符串为该叶子结点的哈夫曼编码，如图 2-39 所示。
运行代码：
//program 2-5
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXBIT 100
#define MAXVALUE 10000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2 -1
typedef struct
{
double weight;
int parent;
int lchild;
int rchild;
char value;
} HNodeType; /* 结点结构体 */
typedef struct
{
int bit[MAXBIT];
int start;
} HCodeType; /* 编码结构体 */
HNodeType HuffNode[MAXNODE]; /* 定义一个结点结构体数组 */
HCodeType HuffCode[MAXLEAF];/* 定义一个编码结构体数组*/
/* 构造哈夫曼树 */
void HuffmanTree (HNodeType HuffNode[MAXNODE], int n){
/* i、j： 循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值，
x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
int i, j, x1, x2;
double m1,m2;
/* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
for (i=0; i<2*n-1;i++)
{
HuffNode[i].weight=0;//权值
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
}
/* 输入 n 个叶子结点的权值 */
for (i=0; i<n; i++)
{
cout<<"Please input value and weight of leaf node "<<i+1<<endl;
cin>>HuffNode[i].value>>HuffNode[i].weight;
}
/* 构造 Huffman 树 */
for (i=0; i<n-1; i++)
{//执行n-1次合并
m1=m2=MAXVALUE;
/* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
x1=x2=0;
/* 找出所有结点中权值最小、无父结点的两个结点，并合并之为一棵二叉树 */
for (j=0;j<n+i;j++)
{
if (HuffNode[j].weight<m1&&HuffNode[j].parent==-1)
{
m2 = m1;
x2 = x1;
m1 = HuffNode[j].weight;
x1 = j;
}
else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
}
/* 设置找到的两个子结点 x1、x2 的父结点信息 */
HuffNode[x1].parent = n+i;
HuffNode[x2].parent = n+i;
HuffNode[n+i].weight = m1+m2;
HuffNode[n+i].lchild = x1;
HuffNode[n+i].rchild = x2;
cout<<"x1.weight and x2.weight in round "<<i+1<<"\t"<<HuffNode[x1].weight<<"\t"<<HuffNode[x2].weight<<endl; /* 用于测试 */
}
}
/* 哈夫曼树编码 */
void HuffmanCode(HCodeType HuffCode[MAXLEAF], int n){
HCodeType cd; /* 定义一个临时变量来存放求解编码时的信息 */
int i,j,c,p;
for(i=0;i<n;i++)
{
cd.start=n-1;
c=i;
p=HuffNode[c].parent;
while(p!=-1)
{
if(HuffNode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--; /*前移一位 */
c=p;
p=HuffNode[c].parent; /* 设置下一循环条件 */
}
/* 把叶子结点的编码信息从临时编码cd中复制出来，放入编码结构体数组 */
for (j=cd.start+1; j<n; j++)
HuffCode[i].bit[j]=cd.bit[j];
HuffCode[i].start=cd.start;
}
}
int main()
{
int i,j,n;
cout<<"Please input n:"<<endl;
cin>>n;
HuffmanTree(HuffNode,n); //构造哈夫曼树
HuffmanCode(HuffCode,n); // 哈夫曼树编码
//输出已保存好的所有存在编码的哈夫曼编码
for(i=0;i<n;i++)
{
cout<<HuffNode[i].value<<": Huffman code is: ";
for(j=HuffCode[i].start+1;j<n;j++)
cout<<HuffCode[i].bit[j];
cout<<endl;
}
return 0;
}
//输入
/*
Please input n：
6
Please input value and weight of leaf node 1
a 0.05
Please input value and weight of leaf node 2
b 0.32
Please input value and weight of leaf node 3
c 0.18
Please input value and weight of leaf node 4
d 0.07
Please input value and weight of leaf node 5
e 0.25
Please input value and weight of leaf node 6
f 0.13
*/
//输出
/*
x1.weight and x2.weight in round 1 0.05 0.07
x1.weight and x2.weight in round 2 0.12 0.13
x1.weight and x2.weight in round 3 0.18 0.25
x1.weight and x2.weight in round 4 0.25 0.32
x1.weight and x2.weight in round 5 0.43 0.57
a: Huffman code is: 1000
b: Huffman code is: 11
c: Huffman code is: 00
d: Huffman code is: 1001
e: Huffman code is: 01
f: Huffman code is: 101
*/算法解析：
-
算法复杂度分析：
-
时间复杂度：由程序可以看出，在函数 HuffmanTree()中，if (HuffNode[j].weight<m1&&HuffNode[j].parent==−1)为基本语句，外层 i 与 j 组成双层循环：
i=0 时，该语句执行 n 次；
i=1 时，该语句执行 n+1 次；
i=2 时，该语句执行 n+2 次；
…
i=n−2 时，该语句执行 n+n−2 次；
则基本语句共执行 n+（n+1）+（n+2）+…+（n+（n−2））=（n−1）*（3n−2）/2 次（等
差数列）；在函数 HuffmanCode()中，编码和输出编码时间复杂度都接近 n2；则该算法时间复
杂度为 O(n2) -
空间复杂度：所需存储空间为结点结构体数组与编码结构体数组，哈夫曼树数组HuffNode[]中的结点为 n 个，每个结点包含 bit[MAXBIT]和 start 两个域，则该算法空间复杂度为 O(n*MAXBIT)
-
-
优化拓展：
- 函数 HuffmanTree()中找两个权值最小结点时使用优先队列，时间复杂度为 logn，执行 n−1 次，总时间复杂度为 O( n logn)
- 函数 HuffmanCode()中，哈夫曼编码数组 HuffNode[]中可以定义一个动态分配空间的线性表来存储编码，每个线性表的长度为实际的编码长度，这样可以大大节省空间。
最小生成树
Prim算法：
某学校下设 10 个学院，3 个研究所，1 个大型图书馆，4 个实验室。其中，1～10 号节点代表 10 个学院，11～13 号节点代表 3 个研究所，14 号节点代表图书馆，15～18 号节点代表 4 个实验室。该问题用无向连通图 G =（V，E）来表示通信网络，V 表示顶点集，E 表示边集。把各个单位抽象为图中的顶点，顶点与顶点之间的边表示单位之间的通信网络，边的权值表示布线的费用。如果两个节点之间没有连线，代表这两个单位之间不能布线，费用为无穷大。
那么我们如何设计网络电缆布线，将各个单位连通起来，并且费用最少呢？
对于 n 个顶点的连通图，只需 n−1 条边就可以使这个图连通，n−1 条边要想保证图连通，就必须不含回路，所以我们只需要找出 n−1 条权值最小且无回路的边即可。
算法设计：
如果在一个图中深度搜索或广度搜索有没有回路，是一件繁重的工作。有一个很好的办法—避圈法。
在生成树的过程中，我们把已经在生成树中的结点看作一个集合，把剩下的结点看作另一个集合，从连接两个集合的边中选择一条权值最小的边即可。
首先任选一个结点，例如 1 号结点，把它放在集合 U 中，U={1}，那么剩下的结点即V−U={2，3，4，5，6，7}，V 是图的所有顶点集合。如图 2-60 所示。
现在只需在连接两个集合（V 和 V−U）的边中看哪一条边权值最小，把权值最小的边关联的结点加入到集合 U。从图 2-60 可以看出，连接两个集合的 3 条边中，结点 1 到结点 2的边权值最小，选中此条边，把 2 号结点加入 U 集合 U={1，2}，V−U={3，4，5，6，7}。
再从连接两个集合（V 和 V−U）的边中选择一条权值最小的边。从图 2-61 可以看出，连接两个集合的 4 条边中，结点 2 到结点 7 的边权值最小，选中此条边，把 7 号结点加入 U集合 U={1，2，7}，V−U={3，4，5，6}。
如此下去，直到 U=V 结束，选中的边和所有的结点组成的图就是最小生成树。这就是Prim算法。
-
确定合适的数据结构。设置带权邻接矩阵 C 存储图 G，如果图 G 中存在边（u，x），令 C[u][x]等于边（u，x）上的权值，否则，C[u][x]=∞ ；bool 数组 s[]，如果 s[i]=true，说明顶点 i 已加入集合 U。可以通过设置两个数组来找到集合中最短的边，closest[j]表示 V−U 中的顶点 j 到集合 U 中的最邻近点，lowcost[j]表示 V−U中的顶点 j 到集合 U 中的最邻近点的边值，即边（j,closest[j]）的权值。
例如，在图 2-62 中，7 号结点到 U 集合中的最邻近点是 2，closest[7]=2，如图 2-63 所示。7 号结点到最邻近点 2 的边值为 1，即边（2，7）的权值，记为 lowcost[7]=1，如图 2-64所示。
只需要在 V−U 集合中找 lowcost[]值最小的顶点即可。
-
初始化。令集合 U={u0 }，u0∈V，并初始化数组 closest[]、lowcost[]和 s[]。
-
在 V−U 集合中找 lowcost 值最小的顶点 t，即 lowcost[t]=min{lowcost[j]|j∈V−U}，满足该公式的顶点 t 就是集合 V−U 中连接集合 U 的最邻近点。
-
将顶点 t 加入集合 U。
-
如果集合 V−U，算法结束，否则，转步骤 6。
-
对集合 V−U 中的所有顶点 j，更新其 lowcost[]和 closest[]。更新公式：if（C[t][j]<lowcost [j] ) { lowcost [j]= C [t] [j]; closest [j] = t; }，转步骤 3。
运行代码：
//program 2-6
#include <iostream>
using namespace std;
const int INF = 0x3fffffff;
const int N = 100;
bool s[N];
int closest[N];
int lowcost[N];
void Prim(int n, int u0, int c[N][N])
{ //顶点个数n、开始顶点u0、带权邻接矩阵C[n][n]
//如果s[i]=true,说明顶点i已加入最小生成树
//的顶点集合U；否则顶点i属于集合V-U
//将最后的相关的最小权值传递到数组lowcost
s[u0]=true; //初始时，集合中U只有一个元素，即顶点u0
int i;
int j;
for(i=1; i<=n; i++)
{
if(i!=u0)
{
lowcost[i]=c[u0][i];
closest[i]=u0;
s[i]=false;
}
else
lowcost[i]=0;
}
for(i=1; i<=n;i++) //在集合中V-u中寻找距离集合U最近的顶点t
{
int temp=INF;
int t=u0;
for(j=1;j<=n;j++)
{
if((!s[j])&&(lowcost[j]<temp))
{
t=j;
temp=lowcost[j];
}
}
if(t==u0)
break; //找不到t，跳出循环
s[t]=true; //否则，讲t加入集合U
for(j=1; j<=n;j++) //更新lowcost和closest
{
if((!s[j])&&(c[t][j]<lowcost[j]))
{
lowcost[j]=c[t][j];
closest[j]=t;
}
}
}
}
int main()
{
int n, c[N][N], m, u, v, w;
int u0;
cout<<"输入结点数n和边数m:"<<endl;
cin>>n>>m;
int sumcost=0;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
c[i][j]=INF;
cout <<"输入结点数u,v和边值w:"<<endl;
for(int i=1; i<=m; i++)
{
cin>>u>>v>>w;
c[u][v]=c[v][u]=w;
}
cout <<"输入任一结点u0:"<<endl;
cin >> u0 ;
//计算最后的lowcos的总和，即为最后要求的最小的费用之和
Prim(n, u0, c);
cout <<"数组lowcost的内容为"<<endl;
for(int i = 1; i <= n; i++)
cout << lowcost[i] << " ";
cout << endl;
for(int i = 1; i <= n; i++)
sumcost += lowcost[i];
cout << "最小的花费是："<<sumcost<<endl;
return 0;
}
//输入
/*
输入结点数 n 和边数 m：
7 12
输入结点数 u，v 和边值 w：
1 2 23
1 6 28
1 7 36
2 3 20
2 7 1
3 4 15
3 7 4
4 5 3
4 7 9
5 6 17
5 7 16
6 7 25
输入任一结点 u0：
1
*/
//输出
/*
数组 lowcost 的内容为：
0 23 4 9 3 17 1
最小的花费是：57
*/算法解析：
-
算法复杂度分析：
- 时间复杂度：在 Prim（int n，int u0，int c[N][N]）算法中，一共有 4 个 for 语句，第①个 for 语句的执行次数为 n，第②个 for 语句里面嵌套了两个 for 语句③、④，它们的执行次数均为 n，对算法的运行时间贡献最大。当外层循环标号为 1 时，③、④语句在内层循环的控制下均执行 n 次，外层循环②从 1～n。因此，该语句的执行次数为 n*n=n²，算法的时间复杂度为 O(n²)
- 空间复杂度：算法所需要的辅助空间包含 i、j、lowcost 和 closest，则算法的空间复杂度是 O(n)
-
优化拓展：
- for 语句③找 lowcost 最小值时使用优先队列，每次出队一个最小值，时间复杂度为logn，执行 n 次，总时间复杂度为 O( n logn)
- for 语句④更新 lowcost 和 closest 数据时，如果图采用邻接表存储，每次只检查t的邻接边，不用从 1～n 检查，检查更新的次数为 E（边数），每次更新数据入队，入队的时间复杂度为 logn，这样更新的时间复杂度为 O( Elogn)
Kurskal算法：
算法设计：
构造最小生成树还有一种算法，Kurskal 算法：设 G=（V，E）是无向连通带权图，V={1，2，…，n}；设最小生成树 T=（V，TE），该树的初始状态为只有 n 个顶点而无边的非连通图T=（V，{}），Kruskal 算法将这 n 个顶点看成是 n 个孤立的连通分支。它首先将所有的边按权值从小到大排序，然后只要 T 中选中的边数不到 n−1，就做如下的贪心选择：在边集 E 中选取权值最小的边（i，j），如果将边（i，j）加入集合 TE 中不产生回路（圈），则将边（i，j）加入边集 TE 中，即用边（i，j）将这两个连通分支合并连接成一个连通分支；否则继续选择下一条最短边。把边（i，j）从集合 E 中删去。继续上面的贪心选择，直到 T 中所有顶点都在同一个连通分支上为止。此时，选取到的 n−1 条边恰好构成 G 的一棵最小生成树 T。
怎样判断加入某条边后图 T 会不会出现回路呢？
Kruskal 算法用了一个非常聪明的方法，就是运用集合避圈：如果所选择加入的边的起点和终点都在 T 的集合中，那么就可以断定一定会形成回路（圈）。
运行代码：
//program 2-7
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100;
int nodeset[N];
int n, m;
struct Edge {
int u;
int v;
int w;
}e[N*N];
bool comp(Edge x, Edge y) {
return x.w < y.w;
}
void Init(int n)
{
for(int i = 1; i <= n; i++)
nodeset[i] = i;
}
int Merge(int a, int b)
{
int p = nodeset[a];
int q = nodeset[b];
if(p==q) return 0;
for(int i=1;i<=n;i++)//检查所有结点，把集合号是 q 的改为 p
{
if(nodeset[i]==q)
nodeset[i] = p;//a 的集合号赋值给 b 集合号
}
return 1;
}
int Kruskal(int n)
{
int ans = 0;
for(int i=0;i<m;i++)
if(Merge(e[i].u, e[i].v))
{
ans += e[i].w;
n--;
if(n==1)
return ans;
}
return 0;
}
int main() {
cout <<"输入结点数n和边数m:"<<endl;
cin >> n >> m;
Init(n);
cout <<"输入结点数u,v和边值w:"<<endl;
for(int i=1;i<=m;i++)
cin>>e[i].u>>e[i].v>>e[i].w;
sort(e, e+m, comp);
int ans = Kruskal(n);
cout << "最小的花费是：" << ans << endl;
return 0;
}算法解析：
-
算法复杂度分析：
- 时间复杂度：算法中，需要对边进行排序，若使用快速排序，执行次数为 eloge，算法的时间复杂度为 O(eloge)。而合并集合需要 n−1 次合并，每次为 O(n)，合并集合的时间复杂度为 O(n^2)
- 空间复杂度：算法所需要的辅助空间包含集合号数组 nodeset[n]，则算法的空间复杂度是 O(n)
-
优化拓展：
-
该算法合并集合的时间复杂度为 O(n2 )，我们可以用并查集的思想优化，使合并集合的时间复杂度降为 O(e*logn)，优化后的程序如下:
//program 2-7-1 #include <iostream> #include <algorithm> using namespace std; const int N = 100; int father[N]; int n, m; struct Edge { int u; int v; int w; }e[N*N]; bool comp(Edge x, Edge y) { return x.w < y.w; } void Init(int n) { for(int i = 1; i <= n; i++) father[i] = i; } int Find(int x) { if(x != father[x]) father[x] = Find(father[x]); return father[x]; } int Merge(int a, int b) { int p = Find(a); int q = Find(b); if(p==q) return 0; if(p > q) father[p] = q;//小的赋值给大的集合号 else father[q] = p; return 1; } int Kruskal(int n) { int ans = 0; for(int i=0;i<m;i++) if(Merge(e[i].u, e[i].v)) { ans += e[i].w; n--; if(n==1) return ans; } return 0; } int main() { cout <<"输入结点数n和边数m:"<<endl; cin >> n >> m; Init(n); cout <<"输入结点数u,v和边值w:"<<endl; for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w; sort(e, e+m, comp); int ans = Kruskal(n); cout << "最小的花费是：" << ans << endl; return 0; } //输入 /* 输入结点数 n 和边数 m： 7 12 输入结点数 u，v 和边值 w： 1 2 23 1 6 28 1 7 36 2 3 20 2 7 1 3 4 15 3 7 4 4 5 3 4 7 9 5 6 17 5 7 16 6 7 25 */ //输出 //最小的花费:57
-
本文摘录于《趣学算法》一书，欲学习其他算法请购买正版书籍！