Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11796
Последний выпуск: 19.06.2015

Задача о неориентированных графах

95K
28 февраля 2015 года
Kate Arskaya
1 / / 28.02.2015
Ребят, учим на английском. Всем классом думаем, ничего в голову не приходит. Решили спросить у могучих русских :)
Цитата:

Измените представление неориентированного графа посредством списков смежности так, чтобы первое ребро в списке смежности любой вершины мож- но было бы удалить за фиксированное время. Напишите процедуру удаления первых ребер, инцидентным вершинам, используя новое представление спи- сков смежности. Подсказка: как сделать так, чтобы две ячейки, соответст- вующие ребру (i, j), могли быстро находить друг друга?

Цитата:

15K
28 февраля 2015 года
xAtom
64 / / 17.01.2011
В списке смежности поиск так или иначе будет всегда за O(n), на то и есть список-смежности. Если памяти не жалко, то заводить надо матрицу-смежности здесь и доступ за константное время O(1). Или только довольствоваться амортизированным временем..
226
01 марта 2015 года
Ramon
1.0K / / 16.08.2003
Цитата:
Решили спросить у могучих русских :)

Нет таковых и небыло никогда.

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог