Количество путей в графе
Дан ориентированный связанный граф без циклов.
Как найти количество различных путей от вершины s в вершину t? и вывести их(все пути).
например дан граф:
4 — вершины
5 — ребер
Пусть s = 1, а t = 4, тогда кол-во путей различных будет 3и, это:
1 — 2 — 4
1 — 4
1 — 3 — 4
Пытался обходом в ширину найти, когда из любой другой вершины выходим на t тогда выписываем путь, но в этом случае может оказаться что смежные вершины могут уже быть помеченными, а если вообще не помечать то плохо получается((
2 Ответ от KADR 2009-10-18 13:17:54
Re: Количество путей в графе
Раз нужно вывести все пути, проще всего запустить поиск в глубину из S. Помечать, использована ли данная вершина, не требуется, т.к. нам важно вывести все пути. Т.е. просто из текущей вершины запускаем поиск в глубину из всех смежных. Т.к в графе нету циклов, количество путей конечно и мы найдем все.
3 Ответ от manof 2009-10-18 13:21:33
Re: Количество путей в графе
4 Ответ от ivank 2009-10-18 22:03:06
Re: Количество путей в графе
Если просто сосчитать — то динамическим программированием.
Если же вывести — то перебором. Не забывайте отсекать перебор, как только из текущей вершины нельзя попасть в конечную — тогда сложность перебора будет O(nk), где k = число путей (может быть экспоненциально большим)
5 Ответ от manof 2009-10-19 00:36:32
Re: Количество путей в графе
ivank пишет:
Если просто сосчитать — то динамическим программированием.
Если же вывести — то перебором. Не забывайте отсекать перебор, как только из текущей вершины нельзя попасть в конечную — тогда сложность перебора будет O(nk), где k = число путей (может быть экспоненциально большим)
А как ДП прикрутить для подсчета путей?
Вывод всех путей уже реализовал с помощью одного запуска DFS без пометок.
6 Ответ от ivank 2009-10-19 05:20:01 Отредактировано ivank (2009-10-19 05:20:31)
Re: Количество путей в графе
Ну, пусть f(u) = число путей из вершины u в t. Рекуррентное соотношение: f(u) = сумма f(v), по всем рёбрам (u, v) в графе. Всё будет хорошо, если граф ациклический.
7 Ответ от Fdg 2011-05-11 19:04:37
Re: Количество путей в графе
Как найти количество путей в ориентированном графе (к-во вершин <=50) от s до t длины не более k<=10?
8 Ответ от KADR 2011-05-11 21:16:32
Re: Количество путей в графе
Как найти количество путей в ориентированном графе (к-во вершин <=50) от s до t длины не более k<=10?
Динамикой по вершине и длине пути. Пусть f(i,j) — количество путей из вершины s в вершину i длины j. Тогда f(i,j)=сумма f(w,j-1) по всем w из которых есть ребро в i.
9 Ответ от Fdg 2011-05-11 21:27:25
Re: Количество путей в графе
А если нужно найти количество путей без циклов?
10 Ответ от KADR 2011-05-11 22:00:29
Re: Количество путей в графе
Ну, если тайм лимит не сильно маленький, то вроде бы можно так. Добавим ребро из t в t и теперь будем искать количество путей длины ровно k.
Пусть f(i,mask) это количество простых путей из s в i, в которых мы посетили только вершины из mask. Посчитаем эту динамику для всех путей длины k/2. Состояний должно быть не сильно много.
Посчитаем еще одну динамику g(i,mask) — количество простых путей из i в t, в которых мы посетили только вершины из mask. Опять же, посчитаем ее для путей длины k-k/2.
Теперь переберем центральную вершину v в пути длины k и нам надо для всех пар (mask1,mask2), которые имеют общий элемент только v посчитать сумму произведений f(v,mask1)*g(v,mask2). Для этого переберем v и mask1 и найдем сумму всех g(v,mask2), которые нам подходят.
Можно по включению-исключению: возьмем сумму всех g(v,mask2), отнимем сумму таких, которые имеют 1 общий элемент с mask1 (кроме v), затем прибавим те, которые имеют 2 и т.д. Для этого, разумеется, надо в начале сделать предподсчет по g(v,mask2).
Сообщений [ 10 ]
Страницы 1
Количество путей в графе: основные понятия и методы подсчета
Эта статья рассказывает о путях в графах и способах их подсчета, а также о свойствах количества путей.
Количество путей в графе: основные понятия и методы подсчета обновлено: 17 сентября, 2023 автором: Научные Статьи.Ру
Помощь в написании работы
Введение
В данной лекции мы будем изучать графы и пути в них. Графы – это абстрактные структуры данных, которые состоят из вершин и ребер, соединяющих эти вершины. Пути в графе представляют собой последовательности вершин, которые связаны ребрами. Мы рассмотрим определение графа, пути в графе, а также способы подсчета количества путей в графе. Также мы изучим некоторые свойства количества путей в графе. Давайте начнем!
Нужна помощь в написании работы?
Мы — биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.
Определение графа
Граф – это абстрактная математическая структура, которая состоит из набора вершин и ребер, соединяющих эти вершины. Вершины представляют собой отдельные объекты, а ребра – связи между этими объектами.
Графы широко используются для моделирования и анализа различных ситуаций и явлений. Они могут представлять сети связей, отношения между объектами, дорожные сети, социальные сети и многое другое.
Графы могут быть направленными или ненаправленными. В направленном графе ребра имеют определенное направление, тогда как в ненаправленном графе ребра не имеют направления.
Графы также могут быть взвешенными или невзвешенными. Взвешенный граф имеет числовые значения, называемые весами, присвоенные каждому ребру. Невзвешенный граф не имеет весов.
Графы могут быть представлены в виде матрицы смежности или списка смежности. Матрица смежности представляет собой квадратную матрицу, где элементы указывают наличие или отсутствие ребра между вершинами. Список смежности представляет собой список, где каждая вершина имеет список смежных с ней вершин.
Определение пути в графе
Путь в графе – это последовательность вершин, которые соединены ребрами. Путь может быть прямым или косвенным, в зависимости от того, есть ли промежуточные вершины между начальной и конечной вершинами.
Прямой путь – это путь, в котором нет повторяющихся вершин. То есть, каждая вершина встречается только один раз.
Косвенный путь – это путь, в котором могут быть повторяющиеся вершины. Такой путь может проходить через одну или несколько вершин несколько раз.
Длина пути – это количество ребер, которые нужно пройти, чтобы перейти от начальной вершины к конечной вершине. Длина пути может быть равна нулю, если начальная и конечная вершины совпадают.
Путь может быть направленным или ненаправленным, в зависимости от того, есть ли у ребер графа определенное направление. В направленном пути нужно двигаться только в одном направлении по ребрам, а в ненаправленном пути можно двигаться в обоих направлениях.
Количество путей в графе
Количество путей в графе – это количество различных способов перемещения от одной вершины к другой в графе. Путь может быть прямым или косвенным, и может содержать любое количество вершин и ребер.
Для подсчета количества путей в графе можно использовать различные методы, в зависимости от его структуры и свойств. Некоторые из них включают:
Матрица смежности
Матрица смежности – это квадратная матрица, в которой строки и столбцы соответствуют вершинам графа, а элементы матрицы указывают наличие или отсутствие ребра между вершинами. Для подсчета количества путей между двумя вершинами можно возвести матрицу смежности в степень и проверить значение в соответствующей ячейке.
Алгоритмы обхода графа
Алгоритмы обхода графа, такие как поиск в глубину (DFS) и поиск в ширину (BFS), могут использоваться для подсчета количества путей. При обходе графа, каждый раз, когда достигается конечная вершина, увеличивается счетчик путей.
Рекурсивные алгоритмы
Рекурсивные алгоритмы могут быть использованы для подсчета количества путей в графе. Один из таких алгоритмов – это рекурсивный обход графа, где каждый раз, когда достигается конечная вершина, вызывается рекурсивная функция для каждого соседнего узла.
Важно отметить, что количество путей в графе может быть ограничено или бесконечным, в зависимости от его структуры и свойств. Поэтому при подсчете количества путей необходимо учитывать возможные ограничения и условия задачи.
Способы подсчета количества путей
Существует несколько способов подсчета количества путей в графе. Рассмотрим некоторые из них:
Матрица смежности
Один из способов подсчета количества путей в графе – это использование матрицы смежности. Матрица смежности представляет собой квадратную матрицу, где каждый элемент указывает наличие или отсутствие ребра между двумя вершинами. Для подсчета количества путей между двумя вершинами можно возвести матрицу смежности в степень n, где n – количество шагов или длина пути. Значение в ячейке (i, j) результирующей матрицы будет указывать количество путей между вершинами i и j.
Алгоритм обхода графа
Другой способ подсчета количества путей – это использование алгоритма обхода графа. Один из таких алгоритмов – это рекурсивный обход графа, где каждый раз, когда достигается конечная вершина, вызывается рекурсивная функция для каждого соседнего узла. В процессе обхода графа подсчитывается количество путей, и в конце получается общее количество путей между начальной и конечной вершинами.
Динамическое программирование
Третий способ подсчета количества путей – это использование динамического программирования. Динамическое программирование позволяет решать задачу путей в графе, разбивая ее на более простые подзадачи и сохраняя результаты этих подзадач для последующего использования. Например, можно использовать рекуррентное соотношение, где количество путей между двумя вершинами зависит от количества путей между их соседними вершинами.
Это лишь некоторые из способов подсчета количества путей в графе. Выбор конкретного способа зависит от структуры и свойств графа, а также от условий задачи.
Примеры подсчета количества путей
Пример 1:
Рассмотрим простой ориентированный граф с 3 вершинами: A, B и C. Вершина A соединена с вершиной B, вершина B соединена с вершиной C, и вершина C соединена с вершиной A. Нам нужно посчитать количество путей от вершины A до вершины C.
Мы можем использовать рекуррентное соотношение для подсчета количества путей. Пусть P(A, C) обозначает количество путей от вершины A до вершины C. Тогда мы можем записать:
P(A, C) = P(A, B) * P(B, C)
Так как у нас есть только один путь от вершины A до вершины B и только один путь от вершины B до вершины C, мы можем записать:
Таким образом, количество путей от вершины A до вершины C равно 1.
Пример 2:
Рассмотрим граф с 4 вершинами: A, B, C и D. Вершина A соединена с вершиной B, вершина B соединена с вершиной C, вершина C соединена с вершиной D, и вершина D соединена с вершиной A. Нам нужно посчитать количество путей от вершины A до вершины D.
Мы можем использовать рекуррентное соотношение для подсчета количества путей. Пусть P(A, D) обозначает количество путей от вершины A до вершины D. Тогда мы можем записать:
P(A, D) = P(A, B) * P(B, C) * P(C, D)
Так как у нас есть только один путь от вершины A до вершины B, только один путь от вершины B до вершины C и только один путь от вершины C до вершины D, мы можем записать:
P(A, D) = 1 * 1 * 1 = 1
Таким образом, количество путей от вершины A до вершины D равно 1.
Это лишь два примера подсчета количества путей в графе. В каждом конкретном случае необходимо анализировать структуру и свойства графа, а также условия задачи, чтобы выбрать подходящий метод подсчета.
Свойства количества путей в графе
Коммутативность
Количество путей от вершины A до вершины B в графе может быть равно количеству путей от вершины B до вершины A. Это свойство называется коммутативностью количества путей.
Ассоциативность
Количество путей от вершины A до вершины C, проходящих через вершину B, может быть равно произведению количества путей от вершины A до вершины B и количества путей от вершины B до вершины C. Это свойство называется ассоциативностью количества путей.
Нулевой путь
Если вершины A и B не связаны ни одним путем, то количество путей от вершины A до вершины B равно 0.
Единичный путь
Если вершина A и вершина B совпадают, то количество путей от вершины A до вершины B равно 1.
Сложение путей
Если в графе существуют два пути от вершины A до вершины B, то количество путей от вершины A до вершины B равно сумме количеств путей по каждому из путей.
Умножение путей
Если в графе существуют два пути от вершины A до вершины B и два пути от вершины B до вершины C, то количество путей от вершины A до вершины C равно произведению количеств путей от вершины A до вершины B и количеств путей от вершины B до вершины C.
Эти свойства помогают нам анализировать и вычислять количество путей в графе, что является важным инструментом при решении задач, связанных с графами.
Таблица сравнения количества путей в графе
- Простота реализации
- Быстрый доступ к информации о смежности вершин
- Занимает больше памяти для хранения матрицы
- Неэффективен для больших графов
- Эффективен для больших графов
- Не требует дополнительной памяти для хранения матрицы
- Сложность реализации
- Может зациклиться на графах с циклами
- Эффективен для графов с большим количеством вершин и ребер
- Позволяет решать более сложные задачи, связанные с графами
- Более сложная реализация
- Требует больше вычислительных ресурсов
Заключение
В этой лекции мы рассмотрели основные понятия и свойства графов. Граф – это абстрактная структура данных, состоящая из вершин и ребер, которые соединяют эти вершины. Мы изучили определение пути в графе и способы подсчета количества путей. Также мы рассмотрели некоторые свойства количества путей в графе. Графы являются важным инструментом в информатике и находят применение в различных областях, таких как сети, логистика, социальные сети и многое другое.
Количество путей в графе: основные понятия и методы подсчета обновлено: 17 сентября, 2023 автором: Научные Статьи.Ру
Задача о числе путей в ациклическом графе
Небольшая модификация алгоритма обхода в глубину. Запустим обход в глубину от вершины [math]s[/math] . При каждом посещении вершины [math]v[/math] проверим, не является ли она искомой вершиной [math]t[/math] . Если это так, то ответ увеличивается на единицу и обход прекращается. В противном случае производится запуск обхода в глубину для всех вершин, в которые есть ребро из [math]v[/math] , причем он производится независимо от того, были эти вершины посещены ранее, или нет.
Функция [math]\mathrm
countPaths(g, v, t) if v == t return 1 else s = 0 for to in g[v] s += countPaths(g, to, t) return s
Время работы данного алгоритма в худшем случае [math]O(Ans)[/math] , где [math]Ans[/math] — число путей в графе из [math]s[/math] в [math]t[/math] . Например, на следующем графе данный алгоритм будет иметь время работы [math]O(2^)[/math] . Если же использовать метод динамического программирования, речь о котором пойдет ниже, то асимптотику можно улучшить до [math]O(n)[/math] .
Метод динамического программирования
Пусть [math]P(v)[/math] — число путей от вершины [math] s [/math] до вершины [math] v [/math] . Тогда [math]P(v)[/math] зависит только от вершин, ребра из которых входят в [math]v[/math] . Тогда [math]P(v) = \sum\limits_P(c)[/math] таких [math]c[/math] , что есть ребро из [math]c[/math] в [math]v[/math] . Мы свели нашу задачу к меньшим подзадачам, причем мы также знаем, что [math]P(s) = 1[/math] . Это позволяет решить задачу методом динамического программирования.
Псевдокод
Пусть [math]s[/math] — стартовая вершина, а [math]t[/math] — конечная, для нее и посчитаем ответ. Будем поддерживать массив [math]d[/math] , где [math]d[v][/math] — число путей из вершины [math] s [/math] до вершины [math]v[/math] и массив [math]w[/math] , где [math]w[v] = true[/math] , если ответ для вершины [math]v[/math] уже посчитан, и [math]w[v] = false[/math] в противном случае. Изначально [math]w[i] = false[/math] для всех вершин [math]i[/math] , кроме [math]s[/math] , а [math]d[s] = 1[/math] . Функция [math]\mathrm[/math] будет возвращать ответ для вершины [math]v[/math] . Удобнее всего это реализовать в виде рекурсивной функции с запоминанием. В этом случае значения массива [math]d[/math] будут вычисляться по мере необходимости и не будут считаться лишний раз:
[math] count(v) = \left \< \begin d[v], & w[v]=true \\ \sum\limits_count(c), & w[v]=false \end \right. [/math]
count(g, v) if w[v] return d[v] else sum = 0 w[v] = true for c in g[v] sum += count(g, c) d[v] = sum return sum countPaths(g, s, t) d[s] = 1 w[s] = true answer = count(t) return answer
Значение функции [math]\mathrm[/math] считается для каждой вершины один раз, а внутри нее рассматриваются все такие ребра [math]\[/math] . Всего таких ребер для всех вершин в графе [math]O(E)[/math] , следовательно, время работы алгоритма в худшем случае оценивается как [math]O(V+E)[/math] , где [math]V[/math] — число вершин графа, [math]E[/math] — число ребер.
Пример работы
Рассмотрим пример работы алгоритма на следующем графе:
Изначально массивы [math]d[/math] и [math]w[/math] инициализированы следующим образом:
| вершина | S | 1 | 2 | 3 | 4 | T |
| w | true | false | false | false | false | false |
| d | 1 | 0 | 0 | 0 | 0 | 0 |
Сначала функция [math]\mathrm[/math] будет вызвана от вершины [math]T[/math] . Ответ для нее еще не посчитан ( [math]w[T] = false[/math] ), следовательно [math]\mathrm[/math] будет вызвана от вершин [math]3[/math] и [math]4[/math] . Для вершины [math]3[/math] ответ также не посчитан ( [math]w[3] = false[/math] ), следовательно [math]\mathrm[/math] будет вызвана уже для вершин [math]2[/math] и [math]S[/math] . А вот для них ответ мы уже можем узнать: для [math]2[/math] он равен [math]d[S][/math] , так как это [math]S[/math] — единственная вершина, ребро из которой входит в нее. Непосредственно для [math]S[/math] ответ нам также известен. На текущий момент таблица будет выглядеть следующим образом:
| вершина | S | 1 | 2 | 3 | 4 | T |
| w | true | false | true | false | false | false |
| d | 1 | 0 | 1 | 0 | 0 | 0 |
Теперь мы знаем значения для вершин [math]2[/math] и [math]S[/math] , что позволяет вычислить [math]d[3] = d[2] + d[S] = 2[/math] . Также обновим значения в массиве [math]w[/math] : [math]w[3] = true[/math] .
| вершина | S | 1 | 2 | 3 | 4 | T |
| w | true | false | true | true | false | false |
| d | 1 | 0 | 1 | 2 | 0 | 0 |
В самом начале для вычисления [math]d[T][/math] нам требовались значения [math]d[3][/math] и [math]d[4][/math] . Теперь нам известно значение [math]d[3][/math] , поэтому проследим за тем, как будет вычисляться [math]d[4][/math] . [math]\mathrm[/math] , но [math]w[3] = true, w[2] = true[/math] , следовательно значения [math]d[3][/math] и [math]d[2][/math] мы уже знаем, и нам необходимо вызвать [math]\mathrm[/math] . Ответ для этой вершины равен [math]d[S][/math] , так как это единственная вершина, ребро из которой входит в [math]1[/math] . Обновим соответствующие значения массивов [math]d[/math] и [math]w[/math] :
| вершина | S | 1 | 2 | 3 | 4 | T |
| w | true | true | true | true | false | false |
| d | 1 | 1 | 1 | 2 | 0 | 0 |
Теперь нам известны все три значения, требующиеся для вычисления ответа для вершины [math]4[/math] . [math]d[4] = d[3] + d[2] + d[1] = 2 + 1 + 1 = 4[/math] :
| вершина | S | 1 | 2 | 3 | 4 | T |
| w | true | true | true | true | true | false |
| d | 1 | 1 | 1 | 2 | 4 | 0 |
Наконец, вычислим [math]d[T] = d[3] + d[4] = 2 + 4 = 6[/math] и обновим таблицы [math]d[/math] и [math]w[/math] :
| вершина | S | 1 | 2 | 3 | 4 | T |
| w | true | true | true | true | true | true |
| d | 1 | 1 | 1 | 2 | 4 | 6 |
Этот алгоритм позволяет вычислить количество путей от какой-либо вершины [math]S[/math] не только до [math]T[/math] , но и для любой вершины, лежащей на любом из путей от [math]S[/math] до [math]T[/math] . Для этого достаточно взять значение в соответствующей ячейке [math]d[/math] .
См. также
- Динамическое программирование
- Кратчайший путь в ациклическом графе
- Задача о расстановке знаков в выражении
- Задача о порядке перемножения матриц
Источники информации
- Акулич И.Л. Глава 4. Задачи динамического программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9..
- Дискретная математика и алгоритмы
- Динамическое программирование
Как посчитать все возможные пути в графе
Есть граф с N ребер и V вершин. Есть стартовая S и конечная F вершины. Как посчитать максимальное количество путей длины Long, по которым его можно обойти?
Отслеживать
pra_soul_owl
задан 8 сен 2019 в 17:47
pra_soul_owl pra_soul_owl
1,964 4 4 золотых знака 21 21 серебряный знак 43 43 бронзовых знака
Вопрос не до конца ясен, есть стартовая вершина и конечная для обхода?
8 сен 2019 в 18:15
да верно. я поправил вопрос. через матрицы смежности не вариант очень не эффективно получается.
8 сен 2019 в 18:22
Решение на c++, java, python: geeksforgeeks.org/count-possible-paths-two-vertices. По поводу длины Long. В ходе поиска пути можно считать число ребер, через которые уже прошли и не учитывать пути, для которых пройденное число ребер > Long.
8 сен 2019 в 18:29
0
Сортировка: Сброс на вариант по умолчанию
Знаете кого-то, кто может ответить? Поделитесь ссылкой на этот вопрос по почте, через Твиттер или Facebook.
- java
- алгоритм
- графы
- структуры-данных
-
Важное на Мете
Похожие
Подписаться на ленту
Лента вопроса
Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.
Дизайн сайта / логотип © 2024 Stack Exchange Inc; пользовательские материалы лицензированы в соответствии с CC BY-SA . rev 2024.1.8.3130
Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.