Я так понимаю можно модифицировать bfs/dfs ? как ?
1 2012-05-10 21:51:33
Тема: Поиск всех путей между двумя вершинами ? (2 ответов, оставленных в Algo)
2 2011-03-24 20:44:14
Re: Поиск компонент связности (4 ответов, оставленных в Algo)
ну тогда все понятно! спасибо)
3 2011-03-23 23:51:50
Re: Поиск компонент связности (4 ответов, оставленных в Algo)
Вот в этом коде
http://e-maxx.ru/algo/connected_components
меня смущает вот этот цикл
for (vector<int>::iterator i=g[cur].begin(); i!=g[cur].end(); ++i)
if (!used[*i]) {
used[*i] = true;
q[t++] = *i;
cout << ", " << *i;
}
насколько я понимаю в g хранятся 0 и 1 показывающие связаны ли вершины ребрами, тогда в used[] мы обращаемся только по индексам 0 и 1.
Т. е. например есть матрица смежности
0 1 1
1 0 0
1 0 0
этот код выведет :
Components :
[ 0, 1]
[ 2]
хотя должно получиться (как я понимаю)
Components :
[ 0, 1, 2]
Решил эту проблему переписыванием выше упомянутого цикла на :
for(int j = 0; j<n; j++)
if (g[cur][j] == 1 && !used[j]) {
used[j] = true;
q[t++] = j;
cout << ", " << j;
}
Подскажите я не правильно понял код или что?
4 2011-03-23 06:01:28
Тема: Поиск компонент связности (4 ответов, оставленных в Algo)
Алгоритм с сайта работает не так как надо Или у меня руки кривые
Можно простой пример его работы ?