数据结构常用算法分析(C++版)-图及算法-2-图的3大应用

简述DPT

上一节我们说了：要看一下PFS的更多应用，所以呢，这一节，我们就以优先级优先搜索（PFS）为基础，探讨一下图3大应用：

无向图：Dijkstra最优路径规划算法/Prime最小生成树算法；
有向图：Topology 拓扑排序

本节需一些DFS和PFS的基础知识~ 如果不知道相关原理的同学，对上面的话看不懂，可以看看上一节的内容从优先级看图的搜索

好了，话不多说，我们直接进入正题！

D-Dijkstra最优路径规划

Dijkstra最优路径规划，带权无向图的一种应用，算法可以得到从某点出发到图中任意节点的最短距离！

算法以PFS为基础进行实现！因为对非连通图进行路径规划无意义，我们就不考虑非联通图的状况啦~

算法步骤如下：

1：访问当前节点
2：更新所有节点的距离（求和取小），并将距离作为优先级，值越小优先级越高
3：需找优先级最小的元素，进行访问标记
4：当遇到优先级最小的元素，也被访问，则说明所有节点访问完毕


template <typename T>
void Grap<T>::DUP(int s,int w)
{
	V[0].priority=0;
	if(G[s][w]==0)
		G[s][w]=PMAX;//优先级置最大值
	else if(V[w].priority>V[s].priority+G[s][w])
	{
		this->V[w].priority=V[s].priority+G[s][w];//更新优先级，到最小值
	}
}



//单源最短路径问题
template <typename T>
void Grap<T>::dijkstra(int v)
{
	int minind=0;//帮助最后越界的判断
	int minpri=PMAX;
	
	this->visited[v]=true;
	(this->V[v]).vprint();

	while(true)
	{
		minpri=PMAX;//复位最大值
		for(int i1=nextV(v,0);i1<this->n;i1=nextV(v,i1+1))//更新所有邻接点的优先级
		{
			if(!this->visited[i1])
				this->DUP(v,i1);//更新优先级
		}
		
		for(int i=0;i<this->n;i++)
		{
			if((!this->visited[i])&&(minpri>this->V[i].priority))// 1-10 值越小，优先级越高
			{
				minind=i;
				minpri=this->V[i].priority;
			}
		}
		if(this->visited[minind])
			break;
		else
		{
			this->visited[minind]=true;
			(this->V[minind]).vprint();
			v=minind;
		}
	}
}

P-Prime最小生成树

Prime算法主要用于生成最小生成树，算法可以找到连接图中所有点的最小路径！算法每次都遵照当前最优的原则，属于贪心算法的一种！

当然，算法要应用于无向图，而且要求是连通性吆~

算法的程序结构与Dijkstra类似：从某一点出发，按照优先级顺序依次遍历途中各点！与Dijkstra的区别就在于优先级更新算法啦！

算法流程如下：

1：访问当前节点
2：更新所有节点的距离（取小值），并将距离作为优先级，值越小优先级越高
3：查找优先级最小的元素，进行访问标记
4：当遇到优先级最小的元素，也已经被访问，则说明所有节点访问完毕


template <typename T>
void Grap<T>::PUP(int s,int w)
{
	if(G[s][w]==0)
		G[s][w]=PMAX;//优先级置最大值
	else if(V[w].priority>G[s][w])
	{
		this->V[w].priority=G[s][w];//更新优先级，到最小值
	}
}


//prime 最小生成树 (不考虑非联通图)

template <typename T>
void Grap<T>::prime(int v)
{
	int minind=0;
	int minpri=PMAX;
	
	this->visited[v]=true;
	(this->V[v]).vprint();

	while(true)
	{
		minpri=PMAX;
		for(int i1=nextV(v,0);i1<this->n;i1=nextV(v,i1+1))//更新所有邻接点的优先级
		{
			if(!this->visited[i1])
				this->PUP(v,i1);
		}
		
		for(int i=0;i<this->n;i++)//需找最高优先级
		{
			if((!this->visited[i])&&(minpri>this->V[i].priority))// 1-10 值越小，优先级越高
			{
				minind=i;
				minpri=this->V[i].priority;
			}
		}
		if(this->visited[minind])
			break;
		else
		{
			this->visited[minind]=true;
			(this->V[minind]).vprint();
			v=minind;
		}
	}
}

T-Topology 拓扑排序

拓扑排序常用来判断一个有向图是否有环，也可用于寻找一些多对多关键点的先后顺序！我们就从入度为0、出度为0两个角度来进行有向无环图的拓扑排序！

基于入度为0的拓扑排序

算法基于：能被拓扑排序的图一定存在入度为0 的点！这是按照拓扑排序的定义，也是最常用的拓扑排序方法，一起看看步骤：

1：找到图中入度为0的点，入队
2：出队元素，然后去掉所有从该点出发的边，若入度减为0则继续入队；
3：循环2，直到队为空，循环结束，并判断总的访问元素与图中节点的大小是否相等！

使用队列存储排序的结果

代码代码：


template <typename T>
void Grap<T>::TsortQueue()
{
	queue<int>q;
	
	int temp;
	int sum;
	 //init入度
	for(int i=0;i<this->n;i++)
	{
		sum = 0;
		this->visited[i]=false;
		for(int j=0;j<this->n;j++)
		{
			if(this->G[j][i]>0)//出度
				sum++;
		}
		this->V[i].priority=sum;
		if(sum == 0)
		{
			q.push(i);
		}
	}
	while(!q.empty())
	{
		temp=q.front();
		V[temp].vprint();
		q.pop();
		for(int i=0;i<=this->n;i++)//遍历从temp出发的每一条边，入度--
		{
			if(G[temp][i]>0)
			{
				V[i].priority--;
				if(V[i].priority==0)
					q.push(i);
			}
		}
	}
}

基于出度为0的DFS拓扑排序

算法基于：能被拓扑排序的图一定存在出度为0 的点！你可以证明一下哈哈~ 也用到了递归的一点属性：DFS函数返回时，节点的出度一定为0！

桥豆麻袋~

按照这个逻辑，是逆拓扑排序定义而为，所以得到的结果也不是真正拓扑排序的结果！我们就需要一个栈结构，来把排序结果进行逆序输出~

步骤如下：

1：初始化图中各点的出度；
2：循环图中节点，从某点出发进行DFS；
3：在DFS函数尾部对节点入栈；
4：循环完成判断栈大小与图中节点个数的关系

注意：（排序是可以提前结束的！）

与DFS不同的是，节点有3种状态：未访问：0 已访问并入栈：2 已访问但未入栈：１当DFS过程遇到状态为１的节点说明，遇到了前面调用过的点，即遇到回路！！！！！排序结束！！！



template <typename T>
void Grap<T>::TsortDFS(int v,stack<vertex<T> > * st)
{
	this->Tvisited[v]=1;//路径状态
	for(int num=nextV(v,0);num<this->n;num=nextV(v,num+1))
	{
		if(this->Tvisited[num]==0)
		{
			TsortDFS(num,st);
		}
		else if(this->Tvisited[num]==1)
		{
			cout<<"有环！！！！"<<endl;//有回路
			return;
		}
	}

	st->push(this->V[v]);
	this->Tvisited[v]=2;//入栈状态
}

  

// 用优先级保存节点的入度，入度为0则进行输出

template <typename T>
void Grap<T>::Tsort(int s)
{
	stack<vertex<T> > st;
	int sum;
	//init出度
	for(int i=0;i<this->n;i++)
	{
		sum=0;
		this->Tvisited[i]=0;
		for(int j=0;j<this->n;j++)
		{
			if(this->G[i][j]>0)//出度
				sum++;
		}
		this->V[i].priority=sum;
	}


	for(int j=0;j<this->n;j++)
	{
		if(this->Tvisited[j]==0)
			TsortDFS(j,&st);
	}

	cout<<st.size()<<endl;
	if(st.size() == this->n)
	{
		cout<<"拓扑排序成功: "<<endl;
		while(!st.empty())
		{
			st.top().vprint();
			st.pop();
		}
	}
	else
	{
		cout<<"拓扑排序失败!"<<endl;
	}
}

总结

接着上一节，我们看了D/P/T 3种图算法的实现，其中前两种均基于PFS实现，只是在更新优先级有所不同！

Topo排序使用基于DFS和Queue两种方式，希望以后能够灵活运用！

最后总结一下吧：

这2节基本覆盖了数据结构-图的基本知识，图的复习也就先到这吧，我的想法肯定有很多不足，各位看官可以在下面多多提意见哈！(#^_^#)

上一节从优先级看图的搜索

小鸟在嗷嗷