Тема: Поиск компонент связности
Алгоритм с сайта работает не так как надо Или у меня руки кривые
Можно простой пример его работы ?
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Algo » Поиск компонент связности
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Алгоритм с сайта работает не так как надо Или у меня руки кривые
Можно простой пример его работы ?
Алгоритм с сайта работает не так как надо Или у меня руки кривые
Можно простой пример его работы ?
Если что-то конкретно непонятно - спросите, возможно вам помогут. Алгоритм довольно простой, попробуйте нарисовать граф на бумажке и просимулировать его работу на нем.
Вот в этом коде
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;
}
Подскажите я не правильно понял код или что?
Нет, в массиве g хранятся не 0 или 1, а списки смежных вершин. То есть g[v] это список всех вершин, которые смежные с v.
ну тогда все понятно! спасибо)
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Algo » Поиск компонент связности