На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> петли и параллельные ребра в неор.графе
Всем хай! Сходу к делу!

Определение:
Ребра, имеющие одинаковые концевые вершины, называются параллельными.
Например, ребро, соединяющее вершины №4 и №8 и ребро, соединяющее вершины №8 и №4 - являются параллельными. Тут вроде все понятно. Также в графе может быть более 2ух параллельных ребер для двух вершин.

Определение:
Ребро, концевые вершины которого совпадают, называется петлей. Например, задается как 3-3, т е ребро выходит из вершины №3 и заходит в вершину №3.

Вопрос: две петли одной вершины можно считать параллельными ребрами??
-----------------------------------------------------
Второй вопрос.
Дано несколько сотен вершин неориентированного графа. + задаются все ребра графа через вершины. Надо проверить, содержит ли граф || ребра.
формат входных данных типа такого:
a b
1 2
3 17
4 6
2 1
5 5
...
а - кол-во вершин графа, b - кол-во ребер.

Алгоритм. Можно, конечно, тупо выделить память для динамической матрицы размером a x a (ну, т е формировать матрицу смежности) и при считывании очередного ребра в соот-щей ячейке ставить 1, как будто-то это не ребро, а ДУГА + параллельно проверять симметричную ячейку, если и там и там стоит по 1 - все, конец обработке - граф содержит || ребра.
1. А, что делать с петлями??
2. Есть более совершенный алгоритм решения?

спс за внимание
Сообщение отредактировано: FasterHarder -
Цитата FasterHarder @
Вопрос: две петли одной вершины можно считать параллельными ребрами??

Конечно. Не просто "можно считать" - они таковые и есть...

Цитата FasterHarder @
2. Есть более совершенный алгоритм решения?

В неориентированном графе порядок вершин неважен. Так что обработать, и для вершин, где конечная точка меньше по индексу - перевернуть. И результат - отсортировать.
Сообщение отредактировано: Akina -
Цитата Akina @
Конечно. Не просто "можно считать" - они таковые и есть...

ок, понял, спс

Цитата Akina @
В неориентированном графе порядок вершин неважен. Так что обработать, и для вершин, где конечная точка меньше по индексу - перевернуть. И результат - отсортировать.

про неор.граф понятно, что порядок не важен вершин, смущает другое - предложение отсортировать после ввода входных данных (на др.форуме была такая же идея). Но сортировка ведь далеко не самая быстрая операция. В моем варианте анализ происходит НА ЛЕТУ(!) и в половине случаев обработка сразу прервется при нахождении хотя бы одной пары || ребер. Здесь же придется сначала ВСЕ прочитать, потом сортировать...не уверен, что это будет производительнее

для учета петель ведь можно завести одномерный динамический массив, состоящий из "а" элементов (а - кол-во вершин графа). Обнулить все элементы и делать +1, когда встретилась петля. Как только стало в любом элемента == 2 - встретилась петля 2 раза для одной вершины - конец обработке.


в общем насчет сортировки не уверен...+этих способов сортировки "тысячи"
В мап клади пары, отсортированные, как Akina сказал. Уже есть такая пара - всё, приехали. Обработка петель ничем не отличается
Цитата FasterHarder @
смущает другое - предложение отсортировать после ввода входных данных (на др.форуме была такая же идея). Но сортировка ведь далеко не самая быстрая операция.

Чегой-то после-то? непосредственно в процессе...
Цитата FasterHarder @
встретилась петля 2 раза для одной вершины - конец обработке.

Вот что-то в исходном состоянии заданного вопроса чего-то типа "убедиться, что параллельные рёбра отсутствуют" - не вижу. Тогда и этот этап - проверка на дубликат,- тоже распрекрасно выполняется в процессе ввода.
Цитата MBo @
В мап клади пары, отсортированные

а, если язык "чистый" СИ)
но, на самом деле язык С++, поэтому все эти шаблоны вроде можно юзать. Но я работаю с СИ раз так в 10 больше, чем с С++, поэтому плохо умею мыслить в терминах stl.

Цитата Akina @
Чегой-то после-то? непосредственно в процессе...

сортировать на лету? чуть позже вернемся к сортировке

Цитата Akina @

Вот что-то в исходном состоянии заданного вопроса чего-то типа "убедиться, что параллельные рёбра отсутствуют" - не вижу.

Здесь не понял тебя. Если после проверки на || ребер таких нет, то автоматически заданный граф НЕ содержит || ребер

Я вот совсем НЕ выкупаю, зачем здесь ЧТО-ТО сортировать???!
Берем СТЛ. Там ведь есть шаблон "множество уникальных значений" (сет или мап или еще как-то называется - вообще не суть). После считывания ребра (2 целых числа) ставим меньшее слева, а большее справа и запихиваем в множество. Но перед тем, как запихнуть, проверяем, а нет ли такого элемента в множестве. Если есть, значит попытка добавить дубликат, что равносильно тому, что в графе появилось || ребро - все, конец обработке!

Зачем здесь что-то сортировать?????

Добавлено
на всякий случай уточню относительно постановки задачи:
Цитата FasterHarder @
Надо проверить, содержит ли граф || ребра.

т е ответом должно быть "Да" или "Нет", т е не нужно находить эти || ребра, важен сам факт
Цитата FasterHarder @
зачем здесь ЧТО-ТО сортировать???!

Чтобы:

1) быстрее вставлять очередную запись в сортированный список, сохраняя сортировку
2) при этом быстрее выполнять проверку на дублирование

Глупо вводить всё, когда уже на середине ввода станет возможно дать ответ.
Akina, а я вот считаю, что сортировка здесь НЕ нужна вообще - и так все прекрасно сработает
здесь вообще о сортировке даже речи быть не может

есть множество (stl-ское какое-нибудь) и через него все можно сделать. Вот единственная проблема, что я плохо помню устройство этих контейнеров set/map и пр., поэтому не хочу спорить сильно)

зы: а вообще я ведь реализовал изначально через заполнение матрицы смежности 0 и 1 + доп.вектор для петель - прожка прошла все тесты по времени и производительности (не забыл поставить register для счетчиков циклов :yes: ) - можно считать, что на "чистом" си была выполнена. И считывание данных заканчивалось, как только была обнаружена 1ая пара || ребер. Все ок
------------------------------------------------------------
краем глаза прочитал про stl-ский set: пишут, что при добавлении в множество автоматически происходит сортировка в порядке возрастания. + перед тем, как добавить элемент в сет, можно узнать через find, а существует ли такое значение в сете.

в общем я НЕ понимаю, зачем здесь что-то сортировать вручную
В кои-то веки согласен с FasterHarder. Сортировать не надо, можно просто в std::set/std::unordered_set очередное ребро запихивать.
Убрать сортировку "под капот" - не значит избавиться от нее. Даже если это не сортировка, а хеширование - все равно полезно помнить про накладные расходы.

В данной задаче, вероятно, сортировка и правда не нужна. Если для каждой вершины меньше десятка инцидентных ей ребер, то можно для каждой вершины завести неупорядоченный односвязный список смежных вершин и искать элементы простым перебором.

Цитата
я ведь реализовал изначально через заполнение матрицы смежности 0 и 1 + доп.вектор для петель

А зачем доп.вектор для петель? Петля - это, по сути, вершина, смежная сама с собой, так что матрицы достаточно.
1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
0 пользователей:


Рейтинг@Mail.ru
[ Script Execution time: 0,1094 ]   [ 19 queries used ]   [ Generated: 1.03.21, 22:07 GMT ]