图论中的贪婪算法_最小生成树

时间:2022-05-15 12:38:28

        没事怕手生了写写代码,看看图论中的一个题目,发现好久不写果然手生了不少。

        题目:

菜鸟物流有自己的运输网络,网络中包含 n个城市物流集散中心,和m对城市之间的运输线路(线路是双向的)。菜鸟物流允许淘宝卖家自行确定包裹的运输路径,但只有一条限制规则:不允许经过重复的城市。淘宝卖家小明从 aa 城市寄出快递后,希望包裹在 midmid 城市进行包装加工以后再寄往 bb 城市。现在小明希望算出一个满足他需求的合法运输路径,你可以帮他算出来么?已知这样的方案一定存在。请为小明输出任意一个可行方案。
输入格式
第一行一个正整数 T(1≤T≤10) 表示数据的组数。
每组数据第一行2个正整数n,m(3≤n≤100,m≤​n(n−1)/2),表示城市个数和运输线路数目。第二行3个互不相同正整数 a,b,mid,表示起点、终点和途径城市。接下来m行,每行2 个正整数 x,y(1≤x,y≤n),表示每条线路连接的 2个城市。每组数据一定存在至少一组合法方案。如果有多种满足小明需求的合法运输路径,输出任意一个即可。
输出格式
每组数据输出L个正整数,表示顺次经过的城市的编号,包括起点和终点。每两个整数之间一个空格,最后一个整数后面没有空格。
样例输入
1
5 5
1 5 3
1 2
2 3
3 4
4 5
5 1
样例输出
1 2 3 4 5

        其实直觉上感觉不难,自己画一个拓扑,基本上一眼就能看出来存不存在这样的路,但你要让机器来给你实现还真不是直觉上那么容易,起码你得选好存放图的数据结构、找一个合适的寻路算法、这个寻路算法又会涉及到什么辅助的数据结构,哎,眼高手低,也花了一晚上去写代码,所以跟看球赛一样,自己感觉是一回事,上去自己打打又是另一回事。

        一开始寻路我觉得应该用深度优先遍历,后来发现图这种数据结构不好整,图不像树一样没有环路,如果有环路你用深度优先便利这可有点麻烦,所以用广度优先遍历还是方便些,由近及远逐步扩大寻找范围,这不就是贪婪算法么,而且因为图中每条边的cost都是1,所以其实就是Prim最小生成树算法啊,只不过不是以加入连通图中所有节点为目标,而是以找到mid和终点为目标。

        这就清晰了基本的程序算法,图直接用邻接矩阵存储,广度优先遍历算法要用到用一个队列容器辅助实现,Prim算法涉及到集合,用set容器即可,路径信息用一个数组就可以存储。

        代码如下(后来在线提交时提示内存超了,优化了下,还是不行,懒得折腾了):

#include <iostream>
#include <stdlib.h>
#include <string>
#include <stdio.h>
#include <deque>
#include <queue>
#include <set>

//#define DEBUG
// 用邻接表来表示图;

int main()
{
	using namespace std;
	int edge[10][101][101];
	int T,n[10],m[10],a[10],b[10],mid[10];
	cin>>T;
	int num=0;
	for(int k=0;k<T;k++)
	{		
		cin>>n[num]>>m[num]>>a[num]>>b[num]>>mid[num];
		for(int i=1;i<=n[num];i++)
			for(int j=1;j<=n[num];j++)
				edge[num][i][j]=0;
		int x,y;
		for(int i=1;i<=m[num];i++)
		{
			cin>>x>>y;
			edge[num][x][y]=edge[num][y][x]=1;
		}
		num++;
	}
	deque<int> queuePath;
	queue<int> queueRequersion;
	set<int> spanningTree,pathSet;
	int path[101];
	for(int i=0;i<T;i++)
	{
		int s=a[i];
		int r=mid[i];
		int d=b[i];
		for(int j=1;j<=n[i];j++)	// 初始化,path用来记录节点在路径中的前一节点;
			path[j]=0;

		spanningTree.insert(s);
		bool isFindMid(true);
		for(int j=1;j<=n[i];j++)	// 用贪心算法来寻找到mid节点的路径,其实相当于Prim最小生成树的算法;
		{
			if(spanningTree.find(j)!=spanningTree.end())	// spanningTree为已遍历的被纳入同起始节点联通的节点集合;
				continue;
			if(edge[i][s][j]==1&&j!=d)		// 不能先经过目的节点再寻找mid节点,不然路径肯定有重复节点。
			{
				path[j]=s;
				queueRequersion.push(j);		// 用一个队列来辅助实现广度优先便利;
				spanningTree.insert(j);
				if(j==r)
				{		
					pathSet.clear();		// 将源节点到中间节点的路径节点存储,在寻找中间节点到目的节点时不能使用;
#ifdef DEBUG
					cout<<"mid to s:"<<endl;
#endif
					do
					{
						pathSet.insert(r);
#ifdef DEBUG
						cout<<r<<" ";
#endif
						r=path[r];
					}while(r!=a[i]);
					pathSet.insert(r);
#ifdef DEBUG
					cout<<r<<endl;
#endif
					break;
				}
			}
			if(j==n[i])	
			{
				if(queueRequersion.size()==0)		// 表示源节点联通子图已经便利完毕,但仍未发现mid节点;
				{
					cout<<"No Such Route!"<<endl;
					isFindMid=false;
					break;
				}
				else
				{
					s=queueRequersion.front();	// 用一个队列来辅助实现广度优先便利;
					queueRequersion.pop();
					j=0;
				}
			}
		}
		if(!isFindMid)	// 找到中间节点才能继续,否则pass;
			continue;

		bool isFindDest(false);
		queueRequersion.empty();
		r=mid[i];
		for(int j=1;j<=n[i];j++)	// 找目的节点;
		{
			if(pathSet.find(j)!=pathSet.end())	// 起点到中间节点路径上的节点直接pass;
				continue;
			if(edge[i][r][j]==1)
			{
				path[j]=r;
				queueRequersion.push(j);
				pathSet.insert(j);
				if(j==d)
				{
					isFindDest=true;
					do
					{
						queuePath.push_front(d);	// 目的节点先入队列,所以为了保持路径是从起点到终点的顺序,要从队列首部入队;
						d=path[d];
					}while(d!=a[i]);
					queuePath.push_front(d);
					break;
				}
			}
			if(j==n[i])
			{
				if(queueRequersion.size()==0)		// 题目说肯定存在路径,所以不考虑程序健壮性可以不要这个判断。
				{
					cout<<"No Such Route!"<<endl;
					isFindDest=false;
					break;
				}
				else
				{
					r=queueRequersion.front();
					queueRequersion.pop();
					j=0;
				}
			}
		}
		if(isFindDest)		// 输出找到的路,因为是贪婪算法,且每个路径长度都为1,所以找到的肯定是一个最短路。
		{
			while(queuePath.size()!=1)
			{
				cout<<queuePath.front()<<" ";
				queuePath.pop_front();
			}
			cout<<queuePath.front()<<endl;
			break;
		}

	}

	return 0;
}