Графы - Python

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

Поиск в Ширину (без рекурсии)

from collections import deque

graph = {
    0: [],
    1: [3, 6],
    2: [0, 1, 4],
    3: [5],
    4: [2],
    5: [7],
    6: [2],
    7: []
}

def bfs(graph, start_vertex):
    visited = [False for _ in range(len(graph))]
    parent = [None for _ in range(len(graph))]
    queue = deque()
    
    visited[start_vertex] = True
    queue.append(start_vertex)
    while queue:
        vertex = queue.popleft()
        for neighbor in graph[vertex]:
            if not visited[neighbor]:
                visited[neighbor] = True
                parent[neighbor] = vertex
                queue.append(neighbor)
    return visited, parent

print(bfs(graph, 1)) 

Ответ:

([True, True, True, True, True, True, True, True], [2, None, 6, 1, 2, 3, 1, 5])

Поиск в Глубину (без рекурсии)

from collections import deque

graph = {
    0: [],
    1: [3, 6],
    2: [0, 1, 4],
    3: [5],
    4: [2],
    5: [7],
    6: [2],
    7: []
}

def dfs(graph, start_vertex):
    visited = [False for _ in range(len(graph))]
    parent = [None for _ in range(len(graph))]
    queue = deque()
    
    visited[start_vertex] = True
    queue.append(start_vertex)
    while queue:
        vertex = queue.pop()
        for neighbor in graph[vertex]:
            if not visited[neighbor]:
                visited[neighbor] = True
                parent[neighbor] = vertex
                queue.append(neighbor)
    return visited, parent

print(dfs(graph, 1))

Ответ:

([True, True, True, True, True, True, True, True], [2, None, 6, 1, 2, 3, 1, 5])

Алгоритм Дэйкстры

Нахождения кратчайшего пути в графе, без отрицательных весов, без кучи.

def dijkstra(graph, start_node):
    dist = dict().fromkeys(graph.keys(), float('inf'))
    used = dict().fromkeys(graph.keys(), False)
    path = dict().fromkeys(graph.keys(), -1)
    
    dist[start_node] = 0
    for i in graph:
        vertex = None
        for j in graph:
            if not used[j] and (vertex is None or dist[j] < dist[vertex]):
                vertex = j
        if dist[vertex] == float('inf'):
            break
        used[vertex] = True
        
        for edge in graph[vertex].items():
            edge_to = edge[0]
            edge_len = edge[1]
            if dist[vertex] + edge_len < dist[edge_to]:
                dist[edge_to] = dist[vertex] + edge_len
                path[edge_to] = vertex
                
    return dist, path


graph = {
    0: {2: 1},
    1: {5: 2, 6: 9},
    2: {0: 1},
    3: {},
    4: {},
    5: {1: 2, 6: 9},
    6: {1: 9, 5: 9, 7: 6},
    7: {6: 6}
}

dijkstra(graph, 5)

Ответ:

({0: inf, 1: 2, 2: inf, 3: inf, 4: inf, 5: 0, 6: 9, 7: 15},
 {0: -1, 1: 5, 2: -1, 3: -1, 4: -1, 5: -1, 6: 5, 7: 6})

Алгоритм Белман-Форд

Нахождения пути в графах с отрицательным весом.

graph = {
    0: {3: 7, 4: 7},
    1: {2: 6, 3: 1},
    2: {1: 6, 5:9},
    3: {0: 7, 1: 1},
    4: {0: 7, 7: 9},
    5: {2: 9},
    6: {},
    7: {4: 9}
}


def bellman_ford(graph, source):
    dist = dict()
    path = dict()
    
    for node in graph:
        dist[node] = float('inf')
        path[node] = None
    dist[source] = 0
    
    for i in range(len(graph) - 1): 
        for vertex in graph:
            for neighbor in graph[vertex]:
                if dist[vertex] + graph[vertex][neighbor] < dist[neighbor]:
                    dist[neighbor] = dist[vertex] + graph[vertex][neighbor]
                    path[neighbor] = vertex
    
    
    for vertex in graph:
        for neighbor in graph[vertex]:
            assert dist[neighbor] <= dist[neighbor] + graph[vertex][neighbor]

    return dist, path

print(bellman_ford(graph, 0))

Ответ:

({0: 0, 1: 8, 2: 14, 3: 7, 4: 7, 5: 23, 6: inf, 7: 16}, {0: None, 1: 3, 2: 1, 3: 0, 4: 0, 5: 2, 6: None, 7: 4})a

Топологическая сортировка

Под топологической сортировкой понимается сортировка элементов, для которых определен частичный порядок, т.е. упорядочивание задано не для всех, а только для некоторых пар элементов. Задача топологической сортировки графа состоит в следующем: указать такой линейный порядок на его вершинах, чтобы любое ребро вело от вершины с меньшим номером к вершине с большим номером. Очевидно, что если в графе есть циклы, то такого порядка не существует.

from collections import deque

g = {
    0: {3: 1, 4: 1},
    1: {6: 1},
    2: {4: 1, 5: 1, 6: 1},
    3: {},
    4: {7: 1},
    5: {},
    6: {7: 1},
    7: {}
}


def dfs(graph, start, used, ans):
    parent = [None for _ in range(len(graph))]
    queue = deque()
    used[start] = True
    queue.append(start)
    buffer = list()
    while queue:
        vertex = queue.popleft()
        for neighbor in graph[vertex]:
            if not used[neighbor]:
                used[neighbor] = True
                parent[neighbor] = vertex
                queue.append(neighbor)
        buffer.append(vertex)
    return buffer + ans


def topoligcal_sort(graph):
    used = [False for _ in range(len(g))]
    ans = list()
    for i in graph:
        if not used[i]:
            ans = dfs(graph, i, used, ans)
    return ans


print(topoligcal_sort(g))

Один из вариантов ответа:

[2, 5, 1, 6, 0, 3, 4, 7]