Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.145.35.178] |
|
Сообщ.
#1
,
|
|
|
Всем хай! Сходу к делу!
Определение: Ребра, имеющие одинаковые концевые вершины, называются параллельными. Например, ребро, соединяющее вершины №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. Есть более совершенный алгоритм решения? спс за внимание |
Сообщ.
#2
,
|
|
|
Цитата FasterHarder @ Вопрос: две петли одной вершины можно считать параллельными ребрами?? Конечно. Не просто "можно считать" - они таковые и есть... Цитата FasterHarder @ 2. Есть более совершенный алгоритм решения? В неориентированном графе порядок вершин неважен. Так что обработать, и для вершин, где конечная точка меньше по индексу - перевернуть. И результат - отсортировать. |
Сообщ.
#3
,
|
|
|
Цитата Akina @ Конечно. Не просто "можно считать" - они таковые и есть... ок, понял, спс Цитата Akina @ В неориентированном графе порядок вершин неважен. Так что обработать, и для вершин, где конечная точка меньше по индексу - перевернуть. И результат - отсортировать. про неор.граф понятно, что порядок не важен вершин, смущает другое - предложение отсортировать после ввода входных данных (на др.форуме была такая же идея). Но сортировка ведь далеко не самая быстрая операция. В моем варианте анализ происходит НА ЛЕТУ(!) и в половине случаев обработка сразу прервется при нахождении хотя бы одной пары || ребер. Здесь же придется сначала ВСЕ прочитать, потом сортировать...не уверен, что это будет производительнее для учета петель ведь можно завести одномерный динамический массив, состоящий из "а" элементов (а - кол-во вершин графа). Обнулить все элементы и делать +1, когда встретилась петля. Как только стало в любом элемента == 2 - встретилась петля 2 раза для одной вершины - конец обработке. в общем насчет сортировки не уверен...+этих способов сортировки "тысячи" |
Сообщ.
#4
,
|
|
|
В мап клади пары, отсортированные, как Akina сказал. Уже есть такая пара - всё, приехали. Обработка петель ничем не отличается
|
Сообщ.
#5
,
|
|
|
Цитата FasterHarder @ смущает другое - предложение отсортировать после ввода входных данных (на др.форуме была такая же идея). Но сортировка ведь далеко не самая быстрая операция. Чегой-то после-то? непосредственно в процессе... Цитата FasterHarder @ встретилась петля 2 раза для одной вершины - конец обработке. Вот что-то в исходном состоянии заданного вопроса чего-то типа "убедиться, что параллельные рёбра отсутствуют" - не вижу. Тогда и этот этап - проверка на дубликат,- тоже распрекрасно выполняется в процессе ввода. |
Сообщ.
#6
,
|
|
|
Цитата MBo @ В мап клади пары, отсортированные а, если язык "чистый" СИ) но, на самом деле язык С++, поэтому все эти шаблоны вроде можно юзать. Но я работаю с СИ раз так в 10 больше, чем с С++, поэтому плохо умею мыслить в терминах stl. Цитата Akina @ Чегой-то после-то? непосредственно в процессе... сортировать на лету? чуть позже вернемся к сортировке Цитата Akina @ Вот что-то в исходном состоянии заданного вопроса чего-то типа "убедиться, что параллельные рёбра отсутствуют" - не вижу. Здесь не понял тебя. Если после проверки на || ребер таких нет, то автоматически заданный граф НЕ содержит || ребер Я вот совсем НЕ выкупаю, зачем здесь ЧТО-ТО сортировать???! Берем СТЛ. Там ведь есть шаблон "множество уникальных значений" (сет или мап или еще как-то называется - вообще не суть). После считывания ребра (2 целых числа) ставим меньшее слева, а большее справа и запихиваем в множество. Но перед тем, как запихнуть, проверяем, а нет ли такого элемента в множестве. Если есть, значит попытка добавить дубликат, что равносильно тому, что в графе появилось || ребро - все, конец обработке! Зачем здесь что-то сортировать????? Добавлено на всякий случай уточню относительно постановки задачи: Цитата FasterHarder @ Надо проверить, содержит ли граф || ребра. т е ответом должно быть "Да" или "Нет", т е не нужно находить эти || ребра, важен сам факт |
Сообщ.
#7
,
|
|
|
Цитата FasterHarder @ зачем здесь ЧТО-ТО сортировать???! Чтобы: 1) быстрее вставлять очередную запись в сортированный список, сохраняя сортировку 2) при этом быстрее выполнять проверку на дублирование Глупо вводить всё, когда уже на середине ввода станет возможно дать ответ. |
Сообщ.
#8
,
|
|
|
Akina, а я вот считаю, что сортировка здесь НЕ нужна вообще - и так все прекрасно сработает
здесь вообще о сортировке даже речи быть не может есть множество (stl-ское какое-нибудь) и через него все можно сделать. Вот единственная проблема, что я плохо помню устройство этих контейнеров set/map и пр., поэтому не хочу спорить сильно) зы: а вообще я ведь реализовал изначально через заполнение матрицы смежности 0 и 1 + доп.вектор для петель - прожка прошла все тесты по времени и производительности (не забыл поставить register для счетчиков циклов ) - можно считать, что на "чистом" си была выполнена. И считывание данных заканчивалось, как только была обнаружена 1ая пара || ребер. Все ок ------------------------------------------------------------ краем глаза прочитал про stl-ский set: пишут, что при добавлении в множество автоматически происходит сортировка в порядке возрастания. + перед тем, как добавить элемент в сет, можно узнать через find, а существует ли такое значение в сете. в общем я НЕ понимаю, зачем здесь что-то сортировать вручную |
Сообщ.
#9
,
|
|
|
В кои-то веки согласен с FasterHarder. Сортировать не надо, можно просто в std::set/std::unordered_set очередное ребро запихивать.
|
Сообщ.
#10
,
|
|
|
Убрать сортировку "под капот" - не значит избавиться от нее. Даже если это не сортировка, а хеширование - все равно полезно помнить про накладные расходы.
В данной задаче, вероятно, сортировка и правда не нужна. Если для каждой вершины меньше десятка инцидентных ей ребер, то можно для каждой вершины завести неупорядоченный односвязный список смежных вершин и искать элементы простым перебором. Цитата я ведь реализовал изначально через заполнение матрицы смежности 0 и 1 + доп.вектор для петель А зачем доп.вектор для петель? Петля - это, по сути, вершина, смежная сама с собой, так что матрицы достаточно. |