Графы и алгоритмы на графах

from collections import deque

graph = {'A': ['B', 'C'], 'B': ['A', 'C', 'D'], 'C': ['A', 'B', 'D', 'E'],
         'D': ['B', 'C', 'E', 'F'], 'E': ['C', 'D', 'F'], 'F': ['D', 'E']}

def bfs(start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        v = queue.popleft()
        for w in graph[v]:
            if w not in dist:
                dist[w] = dist[v] + 1
                queue.append(w)
    return dist

def dfs(v, seen):
    seen.append(v)
    for w in graph[v]:
        if w not in seen:
            dfs(w, seen)
    return seen

print('BFS from F:', bfs('F'))
print('DFS from F:', dfs('F', []))

import heapq

edges = [('A', 'B', 4), ('A', 'C', 2), ('B', 'C', 1), ('B', 'D', 5), ('C', 'D', 8),
         ('C', 'E', 10), ('D', 'E', 2), ('D', 'F', 6), ('E', 'F', 3)]
adj = {}
for u, v, w in edges:
    adj.setdefault(u, []).append((v, w))
    adj.setdefault(v, []).append((u, w))

def dijkstra(src):
    dist, prev, pq = {src: 0}, {}, [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if d + w < dist.get(v, float('inf')):
                dist[v], prev[v] = d + w, u
                heapq.heappush(pq, (d + w, v))
    return dist, prev

dist, prev = dijkstra('A')
path = ['F']
while path[-1] != 'A':
    path.append(prev[path[-1]])
print(dict(sorted(dist.items())))
print(' -> '.join(reversed(path)), '=', dist['F'])

from collections import deque

courses = {'Programming': ['DataStructures', 'Databases'], 'Math': ['Algorithms'],
           'DataStructures': ['Algorithms'], 'Databases': ['AI'],
           'Algorithms': ['AI'], 'AI': []}

def topo_sort(g):
    indeg = {v: 0 for v in g}
    for v in g:
        for w in g[v]:
            indeg[w] += 1
    queue = deque(v for v in g if indeg[v] == 0)
    order = []
    while queue:
        v = queue.popleft()
        order.append(v)
        for w in g[v]:
            indeg[w] -= 1
            if indeg[w] == 0:
                queue.append(w)
    return order if len(order) == len(g) else None

print(topo_sort(courses))
print(topo_sort({'X': ['Y'], 'Y': ['Z'], 'Z': ['X']}))

edges = [('A', 'B', 4), ('A', 'C', 2), ('B', 'C', 1), ('B', 'D', 5), ('C', 'D', 8),
         ('C', 'E', 10), ('D', 'E', 2), ('D', 'F', 6), ('E', 'F', 3)]
parent = {v: v for v in 'ABCDEF'}

def find(v):
    while parent[v] != v:
        v = parent[v]
    return v

mst = []
for u, v, w in sorted(edges, key=lambda e: e[2]):
    ru, rv = find(u), find(v)
    if ru != rv:
        parent[ru] = rv
        mst.append((u, v, w))
print(mst)
print('total weight:', sum(w for _, _, w in mst))