Количество всех возможных путей орграфа

@VistaSV30 · Регистрация: 10.04.2012

Студворк — интернет-сервис помощи студентам

Вывести список всех возможных путей следующего орграфа:

Матрица смежности: graph.xlsx

Мой вариант поиска в ширину:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import pandas as pd
df = pd.read_excel('graph.xlsx', index_col=0)
sz = df.shape[0]
pt = [[df.index[i]+df.index[j] for j in range(sz) if df.iat[i,j]== 1] for i in range(sz)]
edg = dict(zip(range(1, len(pt)), pt))  # ребра графа
 
P = edg[1].copy()
def bfs(x):
    x0 = x[0][0]  # Начало добавляемого ребра
    ac = [i for i in P if i[-1]==x0]
    P1 = list(set(P) - set(ac))
    for i in ac:
        for j in x:
            P1.append(i + j[1])
    return P1
        
for i in range(2, 12):
    P = bfs(edg[i])
    
print(P)

В дальнейшем код нужен будет для поиска всех путей в деревьях или орграфах без петель и только с одинарными ребрами между вершинами.
Посмотрите, пожалуйста, всё ли правильно я сделал.

Спасибо!

@VistaSV30 · 13.06.2022, 18:34 **[ТС]**

Алгоритм не находит путь АГВЕ... Видимо надо как-то поиск еще раз запустить в обратную сторону

Так тоже не получается

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import pandas as pd
df = pd.read_excel('graph.xlsx', index_col=0)
sz = df.shape[0]
edg = []
for i in range(sz):
    edg += [df.index[i]+df.index[j] for j in range(sz) if df.iat[i,j]== 1]
    
a = ''.join(df.index)  # Список вершин графа
P = [i for i in edg if i[0]== a[0]]  # Начало пути
 
def add_edg(b):
    dn = [i for i in edg if i[0] == b]
    ac = [i for i in P if i[-1] == b]
    P1 = list(set(P) - set(ac))
    for i in dn:
        for j in ac:
            P1.append(j + i[1])
    return P1
    
for i in a[1:-2]:
    P = add_edg(i)
print(sorted(P))

@idealist · 13.06.2022, 20:55

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
m = [
    [0, 1,  1,  1,  1,  0,  0,  0,  0,  0,  0,  0],
    [0, 0,  1,  0,  0,  1,  0,  0,  0,  0,  0,  0],
    [0, 0,  0,  0,  0,  1,  1,  0,  0,  0,  0,  0],
    [0, 0,  1,  0,  0,  0,  1,  0,  0,  0,  0,  0],
    [0, 0,  0,  1,  0,  0,  1,  1,  0,  0,  0,  0],
    [0, 0,  0,  0,  0,  0,  1,  0,  1,  0,  0,  0],
    [0, 0,  0,  0,  0,  0,  0,  0,  1,  0,  0,  0],
    [0, 0,  0,  0,  0,  0,  1,  0,  1,  0,  0,  0],
    [0, 0,  0,  0,  0,  0,  0,  0,  0,  1,  1,  0],
    [0, 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1],
    [0, 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1],
    [0, 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]
]
res = []
st  = []
st.append( [0] )
while st:
    lis_cur = st.pop(0)
    i_cur   = lis_cur[-1]
    if i_cur == len(m)-1:
        res.append( lis_cur )
    for j in range( len(m) ):
        if m[i_cur][j]:
            st.append( lis_cur + [j] )
for i in range(len(res)):
    print( f"{i+1}) { ''.join( list( map( lambda x: chr(ord('А')+x), res[i] ) ) ) }" )

@VistaSV30 · 14.06.2022, 23:06 **[ТС]**

Если в графе есть пути, не заканчивающиеся в вершине с максимальным индексом (длинные), то получается найти только длинные пути.

Например, в таком графе

Получается найти только путь [0, 1, 3]
А остальные [0,1,2] и [0,2] - не получается найти

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
m = [[0, 1, 1, 0], [0, 0, 1, 1], [0, 0, 0, 0], [0, 0, 0, 0]]
res, st = [], [[0]]
 
while st:
    lis_cur = st.pop(0)
    i_cur   = lis_cur[-1]
    if i_cur == len(m)-1:
        res.append( lis_cur )
    for j in range( len(m) ):
        if m[i_cur][j]:
            st.append( lis_cur + [j] )
for i in range(len(res)):
    print( f"{i+1}) { ''.join( list(str(res[i] ) ) ) }" )

@VistaSV30 · 14.06.2022, 23:14 **[ТС]**

Так получилось найти все пути, но только в этом графе

Кликните здесь для просмотра всего текста

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import pandas as pd
# df = pd.read_excel('graph.xlsx', sheet_name='4',  index_col=0)
df = pd.DataFrame([[0, 1, 1, 0], [0, 0, 1, 1], [0, 0, 0, 0], [0, 0, 0, 0]])
sz = df.shape[0]
edg = []
for i in range(sz):
    edg += [[df.index[i],df.index[j]] for j in range(sz) if df.iat[i,j]== 1]
    
P = [i for i in edg if i[0]==0]  # Начало путей
 
def bfs(v):
    inc = [i for i in edg if i[0]==v]   # Удлинители
    ex = [i for i in P if i[1]==v] * len(inc) # Удлинняемые ребра
 
    P1 = []
    for i in range(len(ex)):
        P1.append(ex[i] + [inc[i][1]])
    return P1 + [i for i in P if i[1]!=v]
 
print(bfs(1))

@idealist · 14.06.2022, 23:20

Сообщение от VistaSV30

Например, в таком графе

вот так можно:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
m = [
    [0, 1, 1, 0],
    [0, 0, 1, 1],
    [0, 0, 0, 0],
    [0, 0, 0, 0]
]
res, st = [], [[0]]
while st:
    lis_cur = st.pop(0)
    i_cur   = lis_cur[-1]
    if any( m[i_cur] ):
        for j in range(len(m)):
            if m[i_cur][j]:
                st.append(lis_cur + [j])
    else:
        res.append(lis_cur)
for i in range(len(res)):
    print(f"{i + 1}) {''.join(list(str(res[i])))}")

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

Количество всех возможных путей орграфа

Решение

Решение