数据结构 第八讲 图（下）

一、最小生成树问题

是一棵树：无回路、|V|个顶点一定有|V|-1条边
是生成树：包含全部顶点，|V|-1条边都在图里
边的权重和最小

最小生成树<---->图连通

贪心算法

什么是贪？每一步都要最好的
什么是好？权重最小的边
需要约束：只能用图里面存在的边；只能正好用掉|V|-1条边；不能有回路

Prim算法——让一棵小树长大

dist[V] = E<s,V>或正无穷
parent[s] = -1;
void Prim()
{
	MST = {s};
	while(1)
	{
		V = 未收录顶点中dist最小者;
		if(这样的V不存在) break;
		将V收录进MST：dist[V] = 0;
		for(V的每个邻接点W)
		{
			if(dist[W]!=0)
			{
				if(E<V,W> < dist[W])
				{
					dist[W] = E<V,W>;
					parent[W] = V;	
				}
			}
		}
	}
	if(MST中收的顶点不到|V|个)
		Error("生成树不存在");	
} 

时间复杂度 T = O（V）^2 适合稠密图

Kruskal算法——将森林合并成树

非常直接了当的贪心，每次在图里面找权重最小的边收进来
注意：不可形成回路！

void Kruskal(Graph G)
{
	MST = { };
	while(MST中不到|V|-1条边&& E中还有边)
	{
		从E中取一条权重最小的边E<V,W>;		//最小堆
		将E<V,W>从E中删除;
		if(E<V,W>不在MST中构成回路)			//并查集 
		将E<V,W>加入MST;
		else 
			彻底无视E<V,W>; 
	}
	if(MST中不到|V|-1条边)		//图是不连通的 
		Error("生成树不存在"); 
}

时间复杂度：T = O（V logV）

课后练习

题1的解释图

二、拓扑排序

拓扑序：如果图中从v到w有一条有向路径，则v一定排在w之前。满足此条件的顶点序列称为一个拓扑序
获得一个拓扑序的过程就是拓扑排序
AOV（网络）如果有合理的拓扑序，则必定是有向无环图（Directed Acyclic Graph,DAG）

初级算法（T = O(N^2)）

void TopSort() T=O(N^2)
{
	for(cnt = 0;cnt < |V|;cnt++)
	{
		V = 未输入的入度为0的顶点;
		if(这样的V不存在)
		{
			Error("图中有回路");
			break; 
		}
		输出V，或者记录V的输出序号;
		for(V的每个邻接点W)
			Indegree[W]--;
	}
} 

算法优化（T = O（V+E））

随时将入度变为0的顶点放到一个容器里
此算法还可用于检测此图是否为有向无环图（DAG）

void TopSort()
{
	for(图中每个顶点V)
	{
		if(Indegree[V] == 0)
		{
			Enqueue(V,Q);
		}
		while(!Isempty(Q))
		{
			V = Dequeue(Q);
			输出V，或者记录V的输出序号;
			cnt++;
			for(V的每个邻接点W)
			{
				if(--Indegree[W] == 0)
					Enqueue(W,Q);	
			}
		}
		if(cnt!=|V|)
			Error("图中有回路！");
	}
}

三、拓扑排序应用：关键路径问题

AOE（Activity On Edge）网络：一般用于安排项目的工序

课后练习

选A，由图可知，从0到3的时间是12，是由0-2-3决定的，而不是0-1-3。而4也是由0-2影响的，所以加快以后，能提前完工。