圖5——判斷有向圖中是否存在回路

假設以鄰接矩陣作為圖的結構，編寫算法，判别在給定的有向圖中是否存在一個簡單的有向回路，若存在，則以頂點序列的方式輸出該回路（找到一條即可）（注意：圖中不存在頂點到自身的弧）

這是清華大學的考研試題。為了判斷有向圖是否存在環，可以通過深度優先搜尋的方法來實作。從編号0的頂點出發，若兩個頂點間存在路徑，則記錄下源頂點标記為已通路（标記為-1）。在周遊的過程中，若有頂點與源頂點相同，則說明存在環。

code:

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <conio.h>
using namespace std;
const int N = 100;
int G[N][N];
int path[N], visited[N], n, cycle;
int DFS(int u, int start)
{
	int i;
	visited[u] = -1;
	path[u] = start;
	for (i = 0; i < n;i++)
	{
		if (G[u][i]&&i!=start)
		{
			if (visited[i]<0)
			{
				cycle = u;
				return 0;

			}
			if (!DFS(i,u))
			{
				return 0;
			}
		}
	}
	visited[u] = 1;
	return 1;
}

void DisPath(int u)
{
	if (u<0)
	{
		return;
	}
	DisPath(path[u]);
	cout << " " << u;

}

void main()
{
	int i, j;
	cout << "請輸入圖中的頂點個數：" << endl;
	cin >> n;
	memset(G, 0, sizeof(G));
	cout << "請輸入一個" << n << "*" << n << "矩陣（1表示存在弧，0表示不存在弧）：" << endl;
	for (i = 0; i < n;i++)
	{
		for (j = 0; j < n;j++)
		{
			cin >> G[i][j];
		}
	}
	cycle = -1;
	for (i = 0; i < n;i++)
	{
		if (!visited[i]&&!DFS(i,-1))
		{
			break;

		}
	}
	if (cycle<0)
	{
		cout << "不存在環!" << endl;
	} 
	else
	{
		cout << "存在環!" << endl;
		DisPath(cycle);
		cout << endl;
	}

	system("pause");
}
           

結果：

該算法建立4x4矩陣對應的有向圖如下圖所示

其中，a，b，c，d分别對應的編号為0，1，2，3，有向圖有5條弧：<a,b> ,<a,c>,<b,c>,<b,d>和<d,a>，是以存在環a->b->d->a