Количество путей в графе
Количество путей в графе — это общее число маршрутов, которые приводят из одной вершины графа к другой его вершине.
Введение
Определение 2
Под путём в графе понимают последовательный набор его вершин, в котором все вершины соединяются со следующей за ней вершиной посредством ребра.
Если G является неориентированным графом, то путём в графе G будет такой конечный или бесконечный набор последовательных рёбер и вершин S = (…, a0, E0, a1, E1, …, En-1, an), для которого пара соседних рёбер Ei и Ei-1 обладают общей вершиной ai. То есть справедливы следующие выражения E0 = (a0, a1), E1 = (a1, a2), …, En = (an, an+1)
Статья: Количество путей в графе
Поможем написать реферат за 48 часов
Следует заметить, что возможна неоднократная встреча с одним и тем же ребром при прохождении путевого маршрута. В случае, когда нет рёбер, которые предшествуют E0, то a0 считается исходной вершиной S. А когда не существует рёбер, которые идут за E(n-1), то an считается последней вершиной S. Все вершины, которые принадлежат паре соседних рёбер, считаются внутренними.
Следует заметить, что поскольку возможно повторение рёбер и вершин при прохождении путевого маршрута, то внутренняя вершина может быть, как начальной, так и конечной вершиной.
При совпадении начальной и конечной вершин, путь считается циклическим. В случае, когда каждое ребро графа при обходе путевого маршрута, попадается всего один раз (повтор вершин допускается), такой путь считается цепью, а циклический путь считается циклом.
Путь, при котором нет рёбер графа, соединяющих две вершины пути, носит название индуцированного пути. Пара путей считается независимой в смысле вершин, когда у них нет одинаковых внутренних вершин. И по аналогии пара путей считается независимой в плане рёбер, когда у них нет общих внутренних рёбер.
«Количество путей в графе» ��
Готовые курсовые работы и рефераты
Решение задач по учебе за 24 часа
Реферат по этой теме за 48 часов
Количество путей в графе
В случае, когда в город S возможно доехать лишь из городов X, Y, и Z, то количество разнообразных путевых маршрутов из города А в город S равняется суммарному количеству разных путей движения из А в Х, из А в Y и из А в Z, что можно выразить следующей формулой:
$N_S = N_X + N_Y + N_Z$
Обозначим как NM количество путевых маршрутов из вершины А в некую вершину М. Количество путей будет конечным, если в графе отсутствуют замкнутые пути, то есть циклы. Рассмотрим конкретный пример. Имеется структурная схема дорог, которые соединяют города А, Б, В, Г, Д, Е, Ж, И, К, Л. Передвижение по всем дорогам возможно только в одну сторону, в которую указывает стрелка. Необходимо определить количество возможных путей из города А в город Л.
Рисунок 1. Путевые маршруты. Автор24 — интернет-биржа студенческих работ
Обозначим как $N_X$ число разных маршрутов из города А в город Х. Считаем, что город А является исходным пунктом путевого маршрута, и, следовательно, NA = 1. А для произвольно выбранного города Х число путей $N_X$ возможно определить по формуле:
$N_X = N_Y + … + N_Z$.
Здесь суммарный путь принят по всем вершинам, имеющим прямую связь с вершиной Х, то есть, к примеру:
$N_Л = N_Д + N_И + N_Ж + N_К$
Сформируем таблицу, где каждому городу сопоставлено общее число прямых маршрутов в этот город. Вычислим общее число путей из начальной точки маршрута, города А.
В пункты Б и В ведут единственные дороги из А. В пункт В можно попасть из пунктов А, Б, и Г, т.е. $N_В = N_А + N_Б + N_Г = 3$.
Рисунок 2. Таблица. Автор24 — интернет-биржа студенческих работ
В пункт Е можно попасть только из Г, количество путей равно количеству путей в пункт Г. В пункт Ж ведут прямые пути из пунктов Е и В, т.е. $N_Ж = N_В + N_Е = 4$. В пункт Д ведут прямые пути из пунктов Б и В, т.е. $N_Д = N_В + N_Б = 4$.
Рисунок 3. Таблица. Автор24 — интернет-биржа студенческих работ
В пункт И можно попасть только из Д, количество путей равно количеству путей в пункт Д = 4. В пункт К ведет путь только из пункта Е, т.е. $N_К = N_Е = 1$. В пункт Л ведут прямые пути из пунктов Д, И, Ж и К, т.е. $N_Л = N_Д + N_И + N_Ж + N_К = 13$.
Рисунок 4. Таблица. Автор24 — интернет-биржа студенческих работ
Итоговый результат тринадцать путей.
Задача о числе путей в ациклическом графе
Небольшая модификация алгоритма обхода в глубину. Запустим обход в глубину от вершины [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,950 4 4 золотых знака 21 21 серебряный знак 41 41 бронзовый знак
Вопрос не до конца ясен, есть стартовая вершина и конечная для обхода?
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.
Дизайн сайта / логотип © 2023 Stack Exchange Inc; пользовательские материалы лицензированы в соответствии с CC BY-SA . rev 2023.10.27.43697
Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.
Количество путей в графе
Дан ориентированный связанный граф без циклов.
Как найти количество различных путей от вершины 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