グラフィックストピックのまとめ:トポロジーのソート

トポロジのソート
トポロジーソートは有向図に対して行われ、トポロジーソートには2つの役割がある:(1)ある定義された「より小さい」関係に対してノードソートである;(2)有向図に有向リングが存在するか否かを判断する.DFSを用いてトポロジーソートを完了することができる.
次に、有向図gに有向リングが含まれているか否かを判断するコードを示す.

#define N 100+10
int c[N], g[N][N];//      g     
int n;//   ，   0  

bool toposort(int u)
{
	c[u] = -1;//    
	for (int v = 0; v < n; v++)
	if (g[u][v])
	{
		if (c[v] < 0)return true;//     ，  true
		else if (!c[v] && toposort(v))return true;
	}
	c[u] = 1;//    
	return false;//      
}
bool have_circle()
{
	memset(c, 0, sizeof(c));
	for (int i = 0; i < n;i++)
	if (!c[i])
	if (toposort(i))return true;//     ，  true
	return false;//      ，  false
}

紫書のコード

#define N 110
int g[N][N];
int c[N], topo[N], t;
int n;//    

bool dfs(int u)
{
	c[u] = -1;
	for (int v = 0; v < 26;v++)
	if (g[u][v])
	{
		if (c[v] < 0)return false;
		if (!c[v] && !dfs(v))return false;
	}
	c[u] = 1;
	topo[--t] = u;
	return true;
}

bool toposort()
{
	t = n;
	memset(c, 0, sizeof(c));
	memset(topo, 0, sizeof(topo)); 
	for (int u = 0; u < n;u++)
	if (!c[u])
	if (!dfs(u))return false;
	return true;
}