4337 / 1469 / 680
Регистрация: 12.03.2009
Сообщений: 5,310
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
1 | |||||||||||||||||||||||||||||||||||||||||||||||||||
FAQ по графам08.04.2010, 19:30. Просмотров 85367. Ответов 28
Иногда на форуме появляются просьбы решить задачу на теорию графов. На теории такие задачи решаются не так уж и сложно, ведь сколько существует различных теорем, гипотез и так далее. Но когда дело доходит до программной реализации - возникают трудности. Поскольку теория графов является не только одной из сложных тем в высшей математике, но ещё сложнее реализовать какой-нибудь алгоритм на языке программирования. Также это излюбленная тема в олимпиадном программировании, поэтому данный материал также будет полезен не только для учащихся технических ВУЗов, но и для участников всевозможных олимпиад по информатике (я сам таковым являюсь
![]() Если у вас есть предложения по развитию этого FAQ или у вас есть подходящие материалы, то пишите мне в ЛС. Рассмотрю всё ![]() Итак, начнём. ![]() 1) ПЕРЕД ТЕМ, КАК ЧИТАТЬ ДАЛЬШЕ Для решения задач следует понимать, что представляет из себя граф. http://ru.wikipedia.org/wiki/Граф_(математика) 2) СПОСОБ ХРАНЕНИЯ ГРАФОВ В ПАМЯТИ. Чаще всего используют два способа хранения:
sp[i,1] — от какой вершины отходит ребро i sp[i,2] — к какой вершине приходит ребро i; Отдельно можно завести массив P(M), где P[i] будет хранить вес ребра i;
3)ВВОД И ВЫВОД По умолчанию в программах будет рассматриваться ввод с клавиатуры. Я не стану пока описывать процедуры чтения из файла, так как в разных задачах структура файла бывает разной. Но стоит лишь немного изменить нижеприложенные процедуры, как будет получена возможность чтения из файла.
4) ОСНОВНЫЕ АЛГОРИТМЫ
5) ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ НА ГРАФЫ 1) Дано N городов, некоторые из них соединены двусторонними дорогами. Проезда по каждой дороге имеет свою стоимость. Необходимо составить программу, которая по заданной таблице истинности находит путь от города S1 до города S2, суммарная стоимость которая будет минимальна. Формат входных данных: на вход подаётся файл, содержащий в первой строке N. S1 и S2. (1<=N<=50, 1<=S1<=N, 1<=S2<=N). Затем в следующих N строках идут числа, описывающие очередную строку матрицы смежности. Формат выходных данных: на экран вывести города, которые следуют в искомом пути. Пример:
Решение: наиболее удачным и быстродейственным способом нахождения пути от одного пункта к другому является метод Дейкстры, которая ищет минимальные расстояния от какой-то заданной точки до всех остальных. В алгоритме заведём массив предков P(N), который будет содержать минимальный путь, где P[I] - точка, от которой пришли в I по найденному минимальному пути. P[S] будет равно нулю, если S - корневая вершина (от которой и ищем пути). Код программы:
48
|
|
08.04.2010, 19:30 | |
Чем определяется одинаковость урлов /page?FAQ и /page.php?FAQ Книги по графам книги по графам Задание по графам |
|
1915 / 1065 / 383
Регистрация: 06.12.2008
Сообщений: 2,802
|
||||||
15.04.2010, 19:58 | 2 | |||||
Поиск в глубину нерекурсивный методом.
21
|
4337 / 1469 / 680
Регистрация: 12.03.2009
Сообщений: 5,310
|
||||||||||||||||
19.04.2010, 20:30 [ТС] | 3 | |||||||||||||||
2) В некотором городе Н-ске имеется свой метрополитен. Администрация города решила построить новую кольцевую линию. "Центром" этого кольца должна стать одна станций, при этом "радиус" такого кольца - минимальное кол-во станций, которое надо проехать, чтобы достичь кольцевой линии. То есть если радиус равен R - то кольцевая линия должна строиться на тех станциях, до которых можно добраться как минимум через R станций. Кольцо должно иметь как минимум две станции. Программа должна вывести все станции, через которые надо провести новую линию, или 0, если кольцо нельзя постоить.
Формат входных данных: Первая строка содержит число N - количество станций метро (1<=N<=150) и число K. В следующих K строках содержится информация, описывающая схему. Сначала в строке идёт D - номер станции, затем число M, а далее - M чисел, которые показывают, с какими станциями соединена станция D. В предпоследней строке - станция, которая будет "центром" станции, а в последней - радиус кольца. Формат выходных данных: На экран вывести номера искомых станций (в любом порядке). Если кольцо нельзя построить - вывести 0. Пример:
Решение: при помощи поиска в ширину (BFS) на k-ой итерации цикла мы будем находить все станции, до которых можно добраться как минимум через k станций. Сделав ограничение по R и записывая "уровень" каждой станции, мы определим все такие станции. Код программы:
25
|
06.12.2012, 17:29 | 4 | |||||||||||||||||||||||||
1) рекурсия в процедуре DFS передается неправильно. 3 Варианта: либо сделать матрицу смежной глобальной, например, так:
2) Алгоритм Дейкстры можно ускорить. Если на текущем шаге вершину для посещения алгоритм не нашел, то полезнее будет завершить цикл, чем проверять каждый раз найдена ли вершина.
4
|
7 / 7 / 3
Регистрация: 07.04.2013
Сообщений: 85
|
|
12.04.2013, 18:27 | 5 |
Подскажите, за что отвечает переменная inf в алгоритме Дейкстры?
0
|
0 / 0 / 0
Регистрация: 20.04.2013
Сообщений: 12
|
|
02.05.2013, 19:37 | 7 |
подскажите пожалуйста, как сделать так, чтобы программа с графами выполняла задачу Эйлера (там где нужно пройтись по всем островам, побывав на каждом мосту по разу)
сделала возможность ставить графы в поле Image, а как дальше быть - не знаю ![]()
0
|
10 / 0 / 1
Регистрация: 27.11.2013
Сообщений: 8
|
|
27.11.2013, 21:30 | 8 |
0
|
10 / 0 / 1
Регистрация: 27.11.2013
Сообщений: 8
|
|
05.12.2013, 22:35 | 10 |
Я не про это. Если нужно использовать бесконечность для программы то maxlongint подходит в самый раз. Но если хочешь maxlongint div 2.
0
|
0 / 0 / 2
Регистрация: 25.04.2012
Сообщений: 29
|
|
08.12.2013, 16:12 | 12 |
Добрый день! Огромное спасибо за информацию, есть одно "но",здесь описаны разные алгоритмы,а не могли бы вы написать алгоритм "Форда-Беллмана" для неориентированного графа с учетом отрицательных весов ? Заранее благодарен!
0
|
1 / 1 / 1
Регистрация: 29.10.2013
Сообщений: 69
|
|
20.12.2013, 20:37 | 13 |
Объясни, будь добр, как хранить графы на списке смежных вершин? У меня в задачах кол-во ребер\вершин доходит до 200000, и ни матрица смежности, ни список ребер не подходят.
0
|
13 / 5 / 0
Регистрация: 15.11.2015
Сообщений: 57
|
|
15.11.2015, 14:20 | 15 |
yanyk1n,
Уважаемый форумчанин "yanyk1n", большое спасибо за страничку: FAQ по графам узнал много полезного! Поскольку программистом не являюсь - убедительная просьба: как можно подробнее расписать процесс решения популярной игры - головоломки "15" (Пятнашки) в упрощенном варианте с полем 3х3. Она ведь тоже попадает в раздел "алгоритмы на графах" и, видимо относится к алгоритмам рекурсивного "поиска в глубину"... Интересует буквально все: постановка задачи, представление исходных данных в программе, выбор наиболее подходящего алгоритма решения. Заранее благодарю, Евгений
0
|
13 / 5 / 0
Регистрация: 15.11.2015
Сообщений: 57
|
|
15.11.2015, 14:50 | 17 |
Хорошо, что есть живые души :-)
Хотел поздравить Кирилла Дмитриевич личным сообщением, но не знаю как это делается :-( Подскажите, пожалуйста!
0
|
magirus
|
15.11.2015, 18:12
#18
|
Не по теме: это вам пока не доступно.
0
|
13 / 5 / 0
Регистрация: 15.11.2015
Сообщений: 57
|
|
16.11.2015, 08:57 | 19 |
...наверное мордой лица не вышел :-) или "все должно дать сок"!
Уважаемый "magirus", если не трудно, передайте Кириллу Дмитриевичу поздравление с Днем Рождения и пожелайте, пожалуйста, больших успехов в трудовой и боевой... Понимаю, это опять не по теме, но касается автора темы - простите и пропустите... Спасибо! А кто поможет?
0
|
19.11.2015, 22:02 | 20 |
Почему?
Я дык сходу не знаю чем из графов эту задачку можно решить. Только если один раз посчитать все пути. А дальше их "пересчитывать". Можно еще подумать над bfs, dfs - только это будет иметь больше общего с тупым рекурсивным перебором, нежели с графами
0
|
19.11.2015, 22:02 | |
Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь. алгоритм по графам Задачка по графам задача по графам Задача по Графам Задачи по графам Haskell 2 задачи по графам и доказательство. Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |