# Графы - 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]`