浙大数据结构 第八讲 图(下)

数据结构 第八讲 图(下)

一、最小生成树问题

是一棵:无回路、|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影响的,所以加快以后,能提前完工。

上一篇:弹球距离123421


下一篇:Dijkstra:计算最短路径,不适用负权边