|
Grey_DeMonstr
|
|
Software Fiend
|
|
|
|
|
|
|
Рег.: 04.04.2005
|
|
Сообщений: 5517
|
|
Из: .
|
|
Рейтинг: 2400
|
|
[алгоритмическая задача] подсчитать количество достижимых вершин
12.02.2010 17:22
|
|
|
Задача: для каждой вершины произвольного ориентированного графа подсчитать количество достижимых из нее вершин. Размеры графов - от десятков тысяч до миллионов вершин, так что оптимизация по скорости критична. Куда копать?
Редактировал DarkGray (13.02.2010 13:29)
|
У меня все работает. Что я делаю неправильно?
Сага об XYZ |
|
|
vissi
|
|
|
|
|
|
|
|
|
Рег.: 30.09.2007
|
|
Сообщений: 9275
|
|
|
|
Рейтинг: 8222
|
|
|
ребер у вершины сколько бывает?
я правильно понимаю, что тебе подойдет поиск в ширину?
если граф сильно связный (со множеством сильно связных компонент), то это же вообще довольно много данных.
|
|
|
|
eyescream
|
|
nächste Riff
|
|
|
|
|
|
|
Рег.: 20.02.2005
|
|
Сообщений: 426
|
|
|
|
Рейтинг: 392
|
|
|
В каком виде хранится граф?
|
Current Mortal Sin: гордыня.
Current Wise Thought: was ist wenn der Vorhang fällt? |
|
|
Vlad
|
|
addict
|
|
|
|
|
|
|
Рег.: 18.09.2004
|
|
Сообщений: 446
|
|
|
|
Рейтинг: 236
|
|
|
Для начала выдели сильно связные компоненты (за линейное от числа вершин и ребер время, если не ошибаюсь).
Засчет этого можно (если повезет) ощутимо уменьшить размер задачи, и рассматривать только даги.
|
|
|
Grey_DeMonstr
|
|
Software Fiend
|
|
|
|
|
|
|
Рег.: 04.04.2005
|
|
Сообщений: 5517
|
|
Из: .
|
|
Рейтинг: 2400
|
|
Re: Подскажите хороший алгоритм...
[re: vissi]
12.02.2010 17:32
|
|
|
Quote:
ребер у вершины сколько бывает?
Исходящих - от 0 до нескольких десятков. С поиском в ширину - там ведь могут быть циклы, так что не получится учесть, считали мы уже текущую вершину или нет.
|
У меня все работает. Что я делаю неправильно?
Сага об XYZ |
|
|
Grey_DeMonstr
|
|
Software Fiend
|
|
|
|
|
|
|
Рег.: 04.04.2005
|
|
Сообщений: 5517
|
|
Из: .
|
|
Рейтинг: 2400
|
|
Re: Подскажите хороший алгоритм...
[re: eyescream]
12.02.2010 17:33
|
|
|
Quote:
В каком виде хранится граф?
Специальные внутренние форматы. Или я не понял вопрос?
|
У меня все работает. Что я делаю неправильно?
Сага об XYZ |
|
|
FMX
|
|
Математег
|
|
|
|
|
|
|
Рег.: 29.05.2006
|
|
Сообщений: 3744
|
|
|
|
Рейтинг: 1502
|
|
|
1. Построить фактор-граф по отношению эквивалентности - вхождение в одну компонент сильно-связности. Сложность O(V+E). Результатом является ациклический ориентированный граф, вершины которого соответствуют компонентам сильно-связности исходного графа.
2. Начиная с "листовых" компонент для каждой вершины суммируем кол-во вершин в содержащей ее компоненте, а также в тех компонентах, которые достижимы из данной. Сложность O(V + N^2), где N - число компонент связности.
Редактировал FMX (12.02.2010 18:54)
|
|
|
Grey_DeMonstr
|
|
Software Fiend
|
|
|
|
|
|
|
Рег.: 04.04.2005
|
|
Сообщений: 5517
|
|
Из: .
|
|
Рейтинг: 2400
|
|
|
Список
Плоский
Дерево
