find_all_loops.cpp

找出有向图中所有简单回路

#include <iostream>
int const MAX = 101;
using namespace std;

typedef struct directed_graph
{
	int v;
	int e;
	int adj[MAX][MAX];
	int flg[MAX];
}Graph;

void find_all_loops( Graph& G, int v, int len, int path[MAX+1] )
{
	path[len] = v;
	if (G.flg[v])
	{
		G.flg[v] = 0;
		for (int i=0; i<=len; i++)
			cout << path[i];
		cout << endl;
		return;
	}
	G.flg[v] = 1;
	for (int i=1; i<=G.v; i++)
		if (G.adj[v][i])
			find_all_loops(G, i, len+1, path);
}

int main()
{
	Graph G;
	cout << "Enter the number of vertices:" << endl;
	cin >> G.v;
	cout << "Enter the number of edges:" << endl;
	cin >> G.e;
	for (int i=0; i<=G.v; i++)
	{
		G.flg[i] = 0;
		for(int j=0; j<=G.v; j++)
			G.adj[i][j] = 0;
	}
	for (int i=1,a,b; i<=G.e; i++)
	{
		cout << "enter edge" << i << "(m n):";
		cin >> a >> b;
		G.adj[a][b] = 1;
	}
	int path[MAX];
	find_all_loops(G, 1, 0, path);
	system("pause");
	return 0;
}