Алгоритмы и структуры данных на Python с примерами кода + видео

[GuDron]

Алгоритмы и структуры данных на Python с примерами кода + видео


Ниже, в каждом отдельном посте, представлены следующие материалы:
Алгоритм Кнута-Морриса-Пратта (КМП-алгоритм)
Алгоритм Бойера-Мура-Хорспула
Алгоритм Дейкстры (Dijkstra’s algorithm)
Алгоритм Флойда (Floyd’s algorithm)
Алгоритм Форда-Фалкерсона
Алгоритм Краскала (Kruskal’s algorithm)
Алгоритм Прима (ближайшего соседа)
Сортировка выбором
Сортировка вставками
Сортировка пузырьком (метод всплывающего пузырька)
Слияние двух упорядоченных списков
Быстрая сортировка слиянием (merge sort)
Быстрая сортировка Хоара
Стек типа LIFO (Last-In-First-Out)
Делаем очередь (queue)

Алгоритм Кнута-Морриса-Пратта (КМП-алгоритм) | Алгоритмы на Python​

t = "лилила"

p = [0]*len(t)
j = 0
i = 1

while i < len(t):
if t[j] == t[i]:
p[i] = j+1
i += 1
j += 1
else:
if j == 0:
p[i] = 0;
i += 1
else:
j = p[j-1]

print(p)

a = "лилилось лилилась"
m = len(t)
n = len(a)

i = 0
j = 0
while i < n:
if a[i] == t[j]:
i += 1
j += 1
if j == m:
print("образ найден")
break
else:
if j > 0:
j = p[j-1]
else:
i += 1

if i == n and j != m:
print("образ не найден")

 

[GuDron]

Алгоритм Бойера-Мура-Хорспула | Алгоритмы на Python​

t = "данные"

# Этап 1: формирование таблицы смещений

S = set() # уникальные символы в образе
M = len(t) # число символов в образе
d = {} # словарь смещений

for i in range(M-2, -1, -1): # итерации с предпоследнего символа
if t[i] not in S: # если символ еще не добавлен в таблицу
d[t[i]] = M-i-1
S.add(t[i])

if t[M-1] not in S: # отдельно формируем последний символ
d[t[M-1]] = M

d['*'] = M # смещения для прочих символов

print(d)

# Этап 2: поиск образа в строке

a = "метеоданные"
N = len(a)

if N >= M:
i = M-1 # счетчик проверяемого символа в строке

while(i < N):
k = 0
j = 0
flBreak = False
for j in range(M-1, -1, -1):
if a[i-k] != t[j]:
if j == M-1:
off = d[a[i]] if d.get(a[i], False) else d['*'] # смещение, если не равен последний символ образа
else:
off = d[t[j]] # смещение, если не равен не последний символ образа

i += off # смещение счетчика строки
flBreak = True # если несовпадение символа, то flBreak = True
break

k += 1 # смещение для сравниваемого символа в строке

if not flBreak: # если дошли до начала образа, значит, все его символы совпали
print(f"образ найден по индексу {i-k+1}")
break
else:
print("образ не найден")
else:
print("образ не найден")

 

[GuDron]

Алгоритм Дейкстры (Dijkstra’s algorithm) | Алгоритмы на Python​

import math


def arg_min(T, S):
amin = -1
m = math.inf # максимальное значение
for i, t in enumerate(T):
if t < m and i not in S:
m = t
amin = i

return amin


D = ((0, 3, 1, 3, math.inf, math.inf),
(3, 0, 4, math.inf, math.inf, math.inf),
(1, 4, 0, math.inf, 7, 5),
(3, math.inf, math.inf, 0, math.inf, 2),
(math.inf, math.inf, 7, math.inf, 0, 4),
(math.inf, math.inf, 5, 2, 4, 0))

N = len(D) # число вершин в графе
T = [math.inf]*N # последняя строка таблицы

v = 0 # стартовая вершина (нумерация с нуля)
S = {v} # просмотренные вершины
T[v] = 0 # нулевой вес для стартовой вершины
M = [0]*N # оптимальные связи между вершинами

while v != -1: # цикл, пока не просмотрим все вершины
for j, dw in enumerate(D[v]): # перебираем все связанные вершины с вершиной v
if j not in S: # если вершина еще не просмотрена
w = T[v] + dw
if w < T[j]:
T[j] = w
M[j] = v # связываем вершину j с вершиной v

v = arg_min(T, S) # выбираем следующий узел с наименьшим весом
if v >= 0: # выбрана очередная вершина
S.add(v) # добавляем новую вершину в рассмотрение

#print(T, M, sep="\n")

# формирование оптимального маршрута:
start = 0
end = 4
P = [end]
while end != start:
end = M[P[-1]]
P.append(end)

print(P)

 

[GuDron]

Алгоритм Флойда (Floyd’s algorithm) | Алгоритмы на Python​

import math


def get_path(P, u, v):
path = [u]
while u != v:
u = P[u][v]
path.append(u)

return path


V = [[0, 2, math.inf, 3, 1, math.inf, math.inf, 10],
[2, 0, 4, math.inf, math.inf, math.inf, math.inf, math.inf],
[math.inf, 4, 0, math.inf, math.inf, math.inf, math.inf, 3],
[3, math.inf, math.inf, 0, math.inf, math.inf, math.inf, 8],
[1, math.inf, math.inf, math.inf, 0, 2, math.inf, math.inf],
[math.inf, math.inf, math.inf, math.inf, 2, 0, 3, math.inf],
[math.inf, math.inf, math.inf, math.inf, math.inf, 3, 0, 1],
[10, math.inf, 3, 8, math.inf, math.inf, 1, 0],
]

N = len(V) # число вершин в графе
P = [[v for v in range(N)] for u in range(N)] # начальный список предыдущих вершин для поиска кратчайших маршрутов

for k in range(N):
for i in range(N):
for j in range(N):
d = V[i][k] + V[k][j]
if V[i][j] > d:
V[i][j] = d
P[i][j] = k # номер промежуточной вершины при движении от i к j

# нумерацця вершин начинается с нуля
start = 1
end = 4
print(get_path(P, end, start))

 

[GuDron]

Алгоритм Форда-Фалкерсона | Алгоритмы на Python​

import math


def get_max_vertex(k, V, S):
m = 0 # наименьшее допустимое значение
v = -1
for i, w in enumerate(V[k]):
if i in S:
continue

if w[2] == 1: # движение по стрелке
if m < w[0]:
m = w[0]
v = i
else: # движение против стрелки
if m < w[1]:
m = w[1]
v = i

return v


def get_max_flow(T):
w = [x[0] for x in T]
return min(*w)


def updateV(V, T, f):
for t in T:
if t[1] == -1: # это исток
continue

sgn = V[t[2]][t[1]][2] # направление движения

# меняем веса в таблице для (i,j) и (j,i)
V[t[1]][t[2]][0] -= f * sgn
V[t[1]][t[2]][1] += f * sgn

V[t[2]][t[1]][0] -= f * sgn
V[t[2]][t[1]][1] += f * sgn


V = [[[0,0,1], [20,0,1], [30,0,1], [10,0,1], [0,0,1]],
[[20,0,-1], [0,0,1], [40,0,1], [0,0,1], [30,0,1]],
[[30,0,-1], [40,0,-1], [0,0,1], [10,0,1], [20,0,1]],
[[10,0,-1], [0,0,1], [10,0,-1], [0,0,1], [20,0,1]],
[[0,0,1], [30,0,-1], [20,0,-1], [20,0,-1], [0,0,1]],
]

N = len(V) # число вершин в графе
init = 0 # вершина истока (нумерация с нуля)
end = 4 # вершина стока
Tinit = (math.inf, -1, init) # первая метка маршруто (a, from, vertex)
f = [] # максимальные потоки найденных маршрутов

j = init
while j != -1:
k = init # стартовая вершина (нумерация с нуля)
T = [Tinit] # метки маршрута
S = {init} # множество просмотренных вершин

while k != end: # пока не дошли до стока
j = get_max_vertex(k, V, S) # выбираем вершину с наибольшей пропускной способностью
if j == -1: # если следующих вершин нет
if k == init: # и мы на истоке, то
break # завершаем поиск маршрутов
else: # иначе, переходим к предыдущей вершине
k = T.pop()[2]
continue

c = V[k][j][0] if V[k][j][2] == 1 else V[k][j][1] # определяем текущий поток
T.append((c, j, k)) # добавляем метку маршрута
S.add(j) # запоминаем вершину как просмотренную

if j == end: # если дошди до стока
f.append(get_max_flow(T)) # находим максимальную пропускную способность маршрута
updateV(V, T, f[-1]) # обновляем веса дуг
break

k = j

F = sum(f)
print(f"Максимальный поток равен: {F}")

 

[GuDron]

Алгоритм Краскала (Kruskal’s algorithm) | Алгоритмы на Python

#-------------------------------------------------
# Алгоритм Краскала поиска минимального остова графа
#-------------------------------------------------

# список ребер графа (длина, вершина 1, вершина 2)
R = [(13, 1, 2), (18, 1, 3), (17, 1, 4), (14, 1, 5), (22, 1, 6),
(26, 2, 3), (22, 2, 5), (3, 3, 4), (19, 4, 6)]

Rs = sorted(R, key=lambda x: x[0])
U = set() # список соединенных вершин
D = {} # словарь списка изолированных групп вершин
T = [] # список ребер остова

for r in Rs:
if r[1] not in U or r[2] not in U: # проверка для исключения циклов в остове
if r[1] not in U and r[2] not in U: # если обе вершины не соединены, то
D[r[1]] = [r[1], r[2]] # формируем в словаре ключ с номерами вершин
D[r[2]] = D[r[1]] # и связываем их с одним и тем же списком вершин
else: # иначе
if not D.get(r[1]): # если в словаре нет первой вершины, то
D[r[2]].append(r[1]) # добавляем в список первую вершину
D[r[1]] = D[r[2]] # и добавляем ключ с номером первой вершины
else:
D[r[1]].append(r[2]) # иначе, все то же самое делаем со второй вершиной
D[r[2]] = D[r[1]]

T.append(r) # добавляем ребро в остов
U.add(r[1]) # добавляем вершины в множество U
U.add(r[2])

for r in Rs: # проходим по ребрам второй раз и объединяем разрозненные группы вершин
if r[2] not in D[r[1]]: # если вершины принадлежат разным группам, то объединяем
T.append(r) # добавляем ребро в остов
gr1 = D[r[1]]
D[r[1]] += D[r[2]] # объединем списки двух групп вершин
D[r[2]] += gr1

print(T)

 

[GuDron]

Алгоритм Прима (ближайшего соседа) | Алгоритмы на Python​

#-------------------------------------------------
# Алгоритм Прима поиска минимального остова графа
#-------------------------------------------------
import math


def get_min(R, U):
rm = (math.inf, -1, -1)
for v in U:
rr = min(R, key=lambda x: x[0] if (x[1] == v or x[2] == v) and (x[1] not in U or x[2] not in U) else math.inf)
if rm[0] > rr[0]:
rm = rr

return rm


# список ребер графа (длина, вершина 1, вершина 2)
# первое значение возвращается, если нет минимальных ребер
R = [(math.inf, -1, -1), (13, 1, 2), (18, 1, 3), (17, 1, 4), (14, 1, 5), (22, 1, 6),
(26, 2, 3), (19, 2, 5), (30, 3, 4), (22, 4, 6)]

N = 6 # число вершин в графе
U = {1} # множество соединенных вершин
T = [] # список ребер остова

while len(U) < N:
r = get_min(R, U) # ребро с минимальным весом
if r[0] == math.inf: # если ребер нет, то остов построен
break

T.append(r) # добавляем ребро в остов
U.add(r[1]) # добавляем вершины в множество U
U.add(r[2])

print(T)

 

[GuDron]

Сортировка выбором | Алгоритмы на Python​

#-------------------------------------------------
# Алгоритм сортировки выбором
#-------------------------------------------------

a = [-3, 5, 0, -8, 1, 10]
N = len(a) # число элементов в списке

for i in range(N-1):
m = a[i] # запоминаем минимальное значение
p = i # запоминаем индекс минимального значения
for j in range(i+1, N): # поиск миимального среди оставшихся элементов
if m > a[j]:
m = a[j]
p = j

if p != i: # обмен значениями, если был найден минимальный не в i-й позиции
t = a[i]
a[i] = a[p]
a[p] = t

print(a)

 

[GuDron]

Сортировка вставками | Алгоритмы на Python

#-------------------------------------------------
# Алгоритм сортировки вставками
#-------------------------------------------------

a = [-3, 5, 0, -8, 1, 10]
N = len(a) # число элементов в списке

for i in range(1, N):
for j in range(i, 0, -1):
if a[j] < a[j-1]:
a[j], a[j-1] = a[j-1], a[j]
else:
break

print(a)

 

[GuDron]

Сортировка пузырьком (метод всплывающего пузырька) | Алгоритмы на Python​

#-------------------------------------------------
# Алгоритм сортировки пузырьком
#-------------------------------------------------

a = [7, 5, -8, 0, 10, 1]
N = len(a) # число элементов в списке

for i in range(0, N-1): # N-1 итераций работы алгоритма
for j in range(0, N-1-i): # проход по оставшимся не отсортированным парам массива
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]

print(a)

 

[GuDron]

Слияние двух упорядоченных списков | Алгоритмы на Python​

#-------------------------------------------------
# Метод слияния двух списков
#-------------------------------------------------

a = [1, 4, 10, 11]
b = [2, 3, 3, 4, 8]
c = []

N = len(a)
M = len(b)

i = 0
j = 0
while i < N and j < M:
if a[i] <= b[j]:
c.append(a[i])
i += 1
else:
c.append(b[j])
j += 1

c += a[i:] + b[j:]

# if i < N:
# for k in range(i, N):
# c.append(a[k])
# elif j < M:
# for k in range(j, M):
# c.append(b[k])

print(c)

 

[GuDron]

Быстрая сортировка слиянием (merge sort) | Алгоритмы на Python​

#-------------------------------------------------
# Сортировка слиянием
#-------------------------------------------------

# функция слияния двух отсортированных списков
def merge_list(a, b):
c = []
N = len(a)
M = len(b)

i = 0
j = 0
while i < N and j < M:
if a[i] <= b[j]:
c.append(a[i])
i += 1
else:
c.append(b[j])
j += 1

c += a[i:] + b[j:]
return c

# функция деления списка и слияния списков в общий отсортированный список
def split_and_merge_list(a):
N1 = len(a) // 2
a1 = a[:N1] # деление массива на два примерно равной длины
a2 = a[N1:]

if len(a1) > 1: # если длина 1-го списка больше 1, то делим дальше
a1 = split_and_merge_list(a1)
if len(a2) > 1: # если длина 2-го списка больше 1, то делим дальше
a2 = split_and_merge_list(a2)

return merge_list(a1, a2) # слияние двух отсортированных списков в один


a = [9, 5, -3, 4, 7, 8, -8]
a = split_and_merge_list(a)

print(a)

 

[GuDron]

Быстрая сортировка Хоара | Алгоритмы на Python​

#-------------------------------------------------
# Быстрая сортировка Хоара через рекурсию
#-------------------------------------------------
import random


def quick_sort(a):
if len(a) > 1:
x = a[random.randint(0, len(a)-1)] # случайное пороговое значение (для разделения на малые и большие)
low = [u for u in a if u < x]
eq = [u for u in a if u == x]
hi = [u for u in a if u > x]
a = quick_sort(low) + eq + quick_sort(hi)

return a


a = [9, 5, -3, 4, 7, 8, -8]
a = quick_sort(a)

print(a)

 

[GuDron]

Стек типа LIFO (Last-In-First-Out) | Алгоритмы на Python​

# Пример использования стека типа LIFO

a = input("Введите строку: ")
stack = []
flVerify = True

for lt in a:
if lt in "([{":
stack.append(lt)
elif lt in ")]}":
if len(stack) == 0:
flVerify = False
break

br = stack.pop()
if br == '(' and lt == ')':
continue
if br == '[' and lt == ']':
continue
if br == '{' and lt == '}':
continue

flVerify = False
break

if flVerify and len(stack) == 0: # стек по итогам проверок должен быть пустым
print("Yes")
else:
print("No")

 

[GuDron]

Делаем очередь (queue) | Алгоритмы на Python​