ruslan.rakhimov's blog

By ruslan.rakhimov, 6 years ago, In Russian

При изучении алгоритма на e-maxx Проверка графа на ацикличность и нахождение цикла понял, что алгоритм прекращает работу при нахождении первого цикла. Как найти все циклы в графе? Я переделал исходный алгоритм. При реализации моего алгоритма, некоторые циклы упускаются из вида. Например:

Ребра в неориент. графе: 1 2 1 3 2 3 2 4 3 4 Циклы: 1 2 3 1 2 3 4 2 1 2 4 3 1

Мой алгоритм find_cycles() не находит третий цикл. Как можно это исправить?

int ncycle = 0;
vector<int> cycle[MAXN];
vector<int> g[MAXN];

int add_cycle(int cycle_end, int cycle_st)
{
	cycle[ncycle].clear();
	cycle[ncycle].push_back(cycle_st);
	for(int v = cycle_end; v != cycle_st; v = p[v])
		cycle[ncycle].push_back(v);
	cycle[ncycle].push_back(cycle_st);
	
	reverse(cycle[ncycle].begin(), cycle[ncycle].end());
	
	return cycle[ncycle].size();		
}
void dfs(int v)
{
	color[v] = 1;
	for(int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i];
		if(color[to] == 0)
		{
			p[to] = v;
			dfs(to);
		}
		else if(color[to] == 1)
		{
			CycleFound = true;
			if(add_cycle(v, to) > 3) // Исключение вырожденных случаев, н: 1 2 1
				ncycle++;
		}
	}
	color[v] = 0; // Исправлено. Было: color[v] = 2;
}
void find_cycles()
{
	for(int i = 0; i < n; i++)
		if(color[i] == 0)
			dfs(i);
}

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it