判断有向图是否有环及拓扑排序

旧城等待， 2022-08-03 13:39 217阅读 0赞

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。

一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程的开始是以它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。

// Topological_Sort.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<vector>
    #include<iostream>  
    
    using namespace std;
    
    #define N 9  
    typedef struct{
    	int vexnum, arcnum;
    	char vexs[N];
    	int matirx[N][N];
    }graph;
    
    graph g;
    int re[N];
    
    // 初始化图数据    
    // 0---1---2---3---4---5---6---7---8---    
    // A---B---C---D---E---F---G---H---I---    
    void initiate_graph()
    {
    	// A-B, A-D, A-E  
    	g.matirx[0][1] = 1;
    	//g.matirx[1][0] = 1;
    	g.matirx[0][3] = 1;
    	//g.matirx[3][0] = 1;
    	g.matirx[0][4] = 1;
    	//g.matirx[4][0] = 1;
    	// B-C    
    	//g.matirx[1][2] = 1;
    	g.matirx[2][1] = 1;
    	// C-F    
    	g.matirx[2][5] = 1;
    	//g.matirx[5][2] = 1;
    	// D-E, D-G    
    	g.matirx[3][4] = 1;
    	//g.matirx[4][3] = 1;
    	//g.matirx[3][6] = 1;
    	g.matirx[6][3] = 1;
    	// E-F, E-H    
    	g.matirx[4][5] = 1;
    	//g.matirx[5][4] = 1;
    	//g.matirx[4][7] = 1;
    	g.matirx[7][4] = 1;
    	// F-H, F-I    
    	//g.matirx[5][7] = 1;
    	g.matirx[7][5] = 1;
    	//g.matirx[5][8] = 1;
    	g.matirx[8][5] = 1;
    	// G-H    
    	g.matirx[6][7] = 1;
    	//g.matirx[7][6] = 1;
    	// H-I    
    	g.matirx[7][8] = 1;
    	//g.matirx[8][7] = 1;
    
    }
    //判断有向图是否有环
    bool is_cycle(graph g)
    {
    	int k = 0;
    	while (k < N)
    	{
    		int a[N] = { 0 };
    		a[k] = 1;
    		vector<int>aa,cycle;
    		cycle.push_back(k);
    		vector<vector<int>>bb;
    		for (int i = 0; i < N; i++)
    			if (g.matirx[k][i])
    				aa.push_back(i);
    		if (!aa.empty())
    		{
    			bb.push_back(aa);
    			while (!bb.empty())
    			{
    				while ((bb.back()).empty())
    				{
    					bb.pop_back();
    					a[cycle.back()] = 0;
    					cycle.pop_back();
    					if (bb.empty())
    						break;
    				}
    				if (bb.empty())
    					break;
    				int m = (bb.back()).back();
    				(bb.back()).pop_back();
    				a[m] = 1;
    				cycle.push_back(m);
    				vector<int>cc;
    				for (int i = 0; i < N; i++)
    					if (g.matirx[m][i])
    					{
    						if (a[i] == 1)
    							return true;
    						cc.push_back(i);
    					}
    				if (!cc.empty())
    					bb.push_back(cc);
    				else
    				{
    					a[m] = 0;
    					cycle.pop_back();
    				}
    			}
    		}
    		k++;
    	}
    	return false;
    }
    
    void topological_sort(graph g)
    {
    	int aa[N] = { 0 };
    	for (int i = 0; i < N; i++)
    		for (int j = 0; j < N; j++)
    		{
    			if (g.matirx[j][i])
    				aa[i]++;
    		}
    	int k = 0;
    	while (k < N)
    	{
    		for (int i = 0; i < N; i++)
    			if (aa[i] == 0)
    			{
    				re[k] = i;
    				aa[i] = -1;
    				for (int j = 0; j < N; j++)
    				{
    					if (g.matirx[i][j])
    						aa[j]--;
    				}
    				k++;
    				break;
    			}
    	}
    }
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	initiate_graph();
    	if (!is_cycle(g))
    		topological_sort(g);
    
    	system("pause");
    	return 0;
    }