输出所有可能的拓扑排序-Toy模板网

这篇具有很好参考价值的文章主要介绍了输出所有可能的拓扑排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

对于一个有向无环图

由某个集合上的一个偏序得到该集合上的一个全序的操作过程称为拓扑排序。

通俗易懂的说就是，想要的到一个有先后顺序的序列。

比如要上课，要先学了一年级的数学，才能学二年级的数学课一样。但学习几年级的语文课，对你要学习数学课没有影响。

想要得到该图的拓扑排序的一种可能，步骤：

(1) 在有向图中选一个没有前驱的顶点且输出之。

(2) 从图中删除该顶点和所有与他连接的边。

重复上述两步，直至全部顶点均已输出，或者当前图不存在无前驱的顶点为止，后一种情况说明有向图中存在环。

这种方法通过DFS就可以很简单的就得到一个拓扑排序。

那要得到所有可能的拓扑排序要怎么做呢？

可以用DFS+回溯法来得到

回溯算法在数据结构中是一种常用的算法，也是一种暴力求解法，基本思想，选择一条路一步一步走，当走不通的时候或者已经求得正确的结果，返回上一步，接着选择另一条路走，直到遍历完所有节点。问题的解通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。

这里定义了一个成员变量answer字符串，用来存储得到的答案。

我采用邻接矩阵的存储方式：

下面是拓扑排序的代码，注释超详细。

bool graph::order(int i ,int pos)	//得到的answer是否符合拓扑排序的顺序
{
	for(int j=0; j<pos; j++)		//对answer中顺序检查
	{
		for(int k=0; k<dot_num; k++)		//找到answer【j】对应的点的索引
		{
			if(answer[j]==dot[k])
			{
				if(side[i][k]==1)		//如果answer中出现不符合顺序的两个点，则返回0
				{
					return 0;
				}
			}
		}
	}
	return 1;
}
void graph::topolgical_dfs(int pos)		//拓扑排序专用dfs，第pos-1次递归，当pos+1=点数时，完成一条线路的深度搜索，及拓扑排序递归
{
	if(pos==dot_num)            //搜索到了所有的点
	{
		cout<<answer<<endl;
	}
	else
	{
		for(int i=0; i<dot_num; i++)		//对每个点都进行搜索
		{
			if(tag[i]==0 && order(i,pos))	//该店没被访问，并且第i个点在answer中pos的位置符合拓扑排序
			{
				tag[i]=1;
				answer[pos]=dot[i];
				topolgical_dfs(pos+1);      //从当前点进行下一次搜索
				tag[i]=0;					//可以回溯
			}
		}
	}

}

完整代码，附带很多无效的东西，（为了完成老师的任务）

#include <iostream>
using namespace std;
#define max 100
class graph
{
	public:
		int  dot_num;
		char dot[max];
		bool tag[max];
		int side[max][max];
		int out_d[max],in_d[max];
		string answer;
		graph()
		{
			cout<<"input the number of dot:";
			int n;
			cin>>n;							//输入点的个数
			dot_num=n;
			for(int i=0; i<n; i++)			//加入点
			{
				char dian;
				cout<<"the name of dot(char)"<<i+1<<":";
				cin>>dian;
				answer+=dian;		//初始化answer
				dot[i]=dian;		//设置点
				out_d[i]=0;			//出度设为0
				in_d[i]=0;			//入度设为0
				tag[i]=0;			//标志设为0
				for(int j=0; j<n; j++)
					side[i][j]=0;
			}
			cout<<"input the side(input 0 to end):"<<endl;
			string s;
			while(1)							//加入边，格式：ab（为从点a到点b的边）
			{
				cin>>s;
				if(s=="0")
					break;
				for(int i=0; i<n; i++)
				{
					if(s[0]==dot[i])
					{
						for(int j=0; j<n; j++)
						{
							if(s[1]==dot[j])
							{
								side[i][j]=1;		//边设为1
								out_d[i]=1;			//出度设为0
								in_d[j]=1;			//入度设为1
							}
						}
					}
				}

			}

		}
		void set_tag_0(); 					//全部标志置为0
		void DFS(int pos); 					//深度优先搜索
		bool order(int i ,int j);			//判断拓扑排序是否符合顺序
		void topolgical_dfs(int pos);		//拓扑排序专用DFS
		bool no_loop();						//判断有没有环
		void all_topolgical_sort();			//输出所有拓扑排序
};
void graph::set_tag_0()
{
	for(int i=0; i<dot_num; i++)
		tag[i]=0;
}
void graph::DFS(int pos)					//从dot【pos】开始深度优先遍历
{
	tag[pos]=1;
	for(int j=0; j<dot_num; j++)
	{
		if(side[pos][j]==1)
		{
			if(tag[j]==0)
				DFS(j);
		}
	}
}
bool graph::no_loop()
{
	for(int i=0; i<dot_num; i++)	//每个点都找有没有环
	{
		set_tag_0();
		DFS(i);			//对当前点进行DFS
		for(int j=0; j<dot_num; j++)
		{
			if(side[j][i]==1)		//存在 j 点到 i 点的边 
			{
				if(tag[j]==1)	//并且从 i 点可以访问到 j 点
				{
					return 0;
				}
			}
		}
	}
	return 1;
}
bool graph::order(int i ,int pos)	//是否符合拓扑排序的顺序
{
	for(int j=0; j<pos; j++)		//对answer中顺序检查
	{
		for(int k=0; k<dot_num; k++)		//找到answer【j】对应的点的索引
		{
			if(answer[j]==dot[k])
			{
				if(side[i][k]==1)		//如果answer中出现不符合顺序的两个点，则返回0
				{
					return 0;
				}
			}
		}
	}
	return 1;
}
void graph::topolgical_dfs(int pos)		//第pos-1次递归，当pos+1=点数时，完成一条线路的深度搜索，及拓扑排序递归
{
	if(pos==dot_num)
	{
		cout<<answer<<endl;
	}
	else
	{
		for(int i=0; i<dot_num; i++)		//对每个符合要求的点，访问
		{
			if(tag[i]==0 && order(i,pos))	//没被访问，并且该字母不在字符串中
			{
				tag[i]=1;
				answer[pos]=dot[i];
				topolgical_dfs(pos+1);
				tag[i]=0;					//可以回溯
			}
		}
	}

}
void graph::all_topolgical_sort()
{
	if(no_loop())				//不存在环，才开始找拓扑排序
	{
		set_tag_0();
		topolgical_dfs(0);		//从0开始构造

	}
	else
		cout<<"there is loop in this graph."<<endl;

}
int main(void)
{
	graph mygraph;
	mygraph.all_topolgical_sort();
	return 0;
}

通过输入节点及边创建一个图。当该图有环时，输出有环。

输出所有可能的拓扑排序文章来源地址https://www.toymoban.com/news/detail-485599.html