<jupyter_start><jupyter_text>Базовые обходы  Обход в глубину (Depth first search, dfs)Суть обхода в глубину заключается в следующей задаче: в связном неориентированном графе найти такой цикл (возможно с повторением вершин), который проходит через все вершины. При условии отсутствия повторений эта задача становится гораздо более сложной (поиск гамильтонова цикла), но без этого ограничения оказывается, что решить довольно просто с помощью рекурсивной логики. Допустим мы хотим реализовать функцию $dfs(v)$ строит нам такой цикл, начиная с вершины $v$. Тогда рекуррентное правило для такой функции можно выразить как-то так: если $u_1, \ldots, u_k$ -- соседи $v$, то $dfs(v)=v, dfs(u_1), v, dfs(u_2), v, \ldots, v, dfs(u_k), v$. Иначе говоря, мы просто обходим по очереди каждого соседа, добавляя к получившемуся циклу переходы $v\rightarrow u_i$ вначале и $u_i\rightarrow v$ вконце. Если никак не ограничить возможность переходов, то описанное выше правило создает бесконечную рекурсию. Обычно это решается довольно простым способом: прерывать повторные вызовы $dfs(v)$ для одних и тех же вершин. В итоге алгоритм выглядит следующим образом (все функции выше $dfs$ используются только для визуализации).<jupyter_code>def enter_node(node):
    node.SetColor('blue')
    
def enter_arc(node, arc):
    node.SetColor('green')
    arc.attributes['style'] = 'dashed'
    arc.attributes['color'] = 'green'
    
def return_from_arc(node, arc):
    arc.attributes['style'] = 'solid'
    arc.attributes['color'] = 'red'
    node.SetColor('blue')
    
def ignore_arc(arc):
    arc.attributes['color'] = 'blue'
    
def leave_node(node):
    node.SetColor('red')
    
def dfs(graph, node_id, visited, outlist, path):
    visited.add(node_id)
    path.append(node_id)
    enter_node(graph.nodes[node_id])
    outlist.append(graph.Visualize())
    for arc in graph.nodes[node_id].arcs:
        if arc.end not in visited:
            enter_arc(graph.nodes[node_id], arc)
            dfs(graph, arc.end, visited, outlist, path) 
            return_from_arc(graph.nodes[node_id], arc)
            path.append(node_id)
        else:
            ignore_arc(arc)
        outlist.append(graph.Visualize())      
    leave_node(graph.nodes[node_id])
graph = Graph(arcs)
visited = set()
dfs_outlist = []
path = []
dfs_outlist.append(graph.Visualize())
dfs(graph, 0, visited, dfs_outlist, path)
dfs_outlist.append(graph.Visualize())
print(path)
animate_list(dfs_outlist);<jupyter_output><empty_output><jupyter_text>Примеры Выделение компонент связностиКомпонента связности в неориентированном графе -- это множество вершин, в котором каждая пара вершин соединена путем, и при этом нет пути из вершины из этого множества в вершину не из этого множества. $dfs$ (ровно как и $bfs$, описанный далее) обходит ровно одну компоненту связности, при этом в $visited$ запоминаются вершины, которые посетил наш обход. Если запустить $dfs$ с сохранением $visited$ из каждой вершины, то в результате можно получить разбиение графа на компоненты связности<jupyter_code>graph = Graph([
    Arc(0, 1),
    Arc(1, 0),
    Arc(1, 2),
    Arc(2, 1),
    Arc(3, 4),
    Arc(4, 3),
    Arc(3, 5),
    Arc(5, 3)
])
visited = set()
components_outlist = []
print("Components:")
for node_id in graph.nodes:
    if node_id in visited:
        continue
    path = []
    components_outlist.append(graph.Visualize())
    dfs(graph, node_id, visited, components_outlist, path)
    components_outlist.append(graph.Visualize())
    print(set(path))
animate_list(components_outlist);<jupyter_output>Components:
{0, 1, 2}
{3, 4, 5}<jupyter_text>Топологическая сортировка и поиск цикловВ ориентированном графе всегда выполняется одно из двух: 1) вершины графа могут быть пронумерованы так, что ребра идут из вершины с меньшим номером в вершину с большим номером; 2) В графе есть цикл. Довольно очевидно, что при выполнении 2) невозможно 1). Чуть менее очевидно, что если 2) не выполняется, то обязательно выполняется 1). Сортировка вершин согласно 1) обычно называется топологической сортировкой. В визуализации $dfs$ использовались три цвета: черный для вершин, которые еще не посетили; зеленый для вершин, в которые вошли, но еще не вышли; красный для вершин, из которых уже вышли. Оказывается, что если в графе есть цикл, в $dfs$ обязательно в какой-то момент мы будем обрабатывать ребро, ведущее в зеленую вершину. С помощью $dfs$ также довольно легко получить топологический порядок: если из $v$ есть переходы в $u_1, \ldots, u_k$, то нужно сначала обойти и пронумеровать все $u_i$, а потом уже пронумеровать $v$ номером, меньшим, чем пронумерованные ранее. Обычно это удобно делать задом наперед.<jupyter_code>def top_sort(graph, node_id, visited, stack, reversed_top_order):
    visited[node_id] = 'green'
    stack.append(node_id)
    for arc in graph.nodes[node_id].arcs:
        if arc.end in visited:
            if visited[arc.end] == 'green':
                for i, v in enumerate(stack):
                    if v == arc.end:
                        return stack[i:]
        else:
            result = top_sort(graph, arc.end, visited, stack, reversed_top_order)
            if result is not None:
                return result
    reversed_top_order.append(node_id)
    stack = stack[:-1]
    visited[node_id] = 'blue'
    return None

def try_top_sort(graph):
    visited = dict()
    stack = []
    reversed_top_order = []
    for node_id in graph.nodes:
        if node_id in visited:
            continue
        has_cycle = top_sort(graph, node_id, visited, stack, reversed_top_order)
        if has_cycle is not None:
            print ("Cycle detecetd:", has_cycle)
            return
    result = list(reversed(reversed_top_order))
    print("No cycles, proper ordering:", result)
    return result
graph = Graph([
    Arc(3, 1),
    Arc(1, 2), 
    Arc(3, 0),
    Arc(0, 5),
    Arc(5, 6),
    Arc(7, 8)
])
order = try_top_sort(graph)
inv_order = dict()
for i, value in enumerate(order):
    inv_order[value] = i
graph.Visualize()
arcs_ordered = []
for node in graph.nodes.values():
    arcs_ordered.extend([Arc(inv_order[arc.beginning], inv_order[arc.end]) for arc in node.arcs])
graph_ordered = Graph(arcs_ordered)
graph_ordered.Visualize()
graph = Graph([
    Arc(3, 1),
    Arc(1, 2), 
    Arc(3, 0),
    Arc(0, 5),
    Arc(6, 3),
    Arc(7, 8),
    Arc(2, 6)
])
try_top_sort(graph)
graph.Visualize()<jupyter_output>Cycle detecetd: [3, 1, 2, 6]<jupyter_text>Топологическая сортировка графа, если она возможна, помогает во многих друих задачах, например нахождении кратчайших расстояний в графе. Вычислительные графы, использующиеся в pytorch, tensorflow и т.п., также ацикличны, топологическая сортировка для них выдает порядок, в котором должны быть произведены вычисления. Мы также сталкивались с довольно интересной ситуацией: в конфигурационных файлах вычислительных графов для нейронных сетей в калди могут быть циклы из-за особенностей реализации реккурентных связей. Для дого, чтобы проанализировать граф из калди и перевести его в другой формат (cntk) необходимо было выделить компоненты сильной связности, для чего обычно используется более хитрый [алгоритм Тарьяна](https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A2%D0%B0%D1%80%D1%8C%D1%8F%D0%BD%D0%B0), основанный на идеях, использующихся в топологической сортировке.  АнализВо всез указанных выше примерах просмотр исходящих из вершины ребер осуществляется только один раз. `path` пополняется при входе в вершину и при просмотре ребра, ведущего в еще не посещенную вершину. Общий размер `path` -- это $2N-C$, где $N$ -- количество вершин, $C$ -- количество компонент связности  Обход в ширину (breadth first search, bfs)Основная задача для обхода в ширину: дана вершина $s$, для всех остальных вершин посчитать, какое минимальное количество переходов по ребрам нужно сделать, чтобы добраться из $s$ в эту вершину? По сути это самая простая разновидность задачи о кратчайших путях, где все ребра имеют одинаковую длину. Идея довольно проста: последовательно находим множества вершин, для которых расстояние $0, 1, 2, \ldots$. Если обозначить за $V_d$ -- множество вершин на расстояние $d$, то оно состоит из соседей вериш из $V_{d-1}$, которые не содержатся в $V_1\cup \ldots \cup V_{d-1}$. Несмотря на схожую с $dfs$ рекуррентную структуру из-за необходимости работы с множествами для эффективной реализации подсчета всех этих расстояний используют механизм с очередью. Изачально в очереди находится единственный элемент -- $s$, т.е. очередь содержит множество $V_0$. Одна итерация алгоритма заключается в вытаскивании из очереди вершины, просматриванию её соседей, и добавлении в очередь этого соседа, если ранее эта вершина не была обработана. Если мы достаем вершину с расстоянием $d$, то её соседи будут иметь расстояние $d+1$ или меньше, при этом положим мы в очередь соседа только если расстояние $d+1$. Таким образом на каждой итерации алгоритма соблюдается инвариант, что сначала в очереди идут несколько вершин с растоеним $d$, а потом с расстоянием $d+1$, другими словами мы в процессе вычисления $V_{d+1}$. В какие-то моменты у нас остается только вершины с одинаковым расстоянием, это означает, что мы только что закончили просматривать вершины из $V_d$ для формирования $V_{d+1}$<jupyter_code>import queue
def process_arc(arc):
    arc.attributes['color'] = 'blue'

def put_node_in_queue(node):
    node.SetColor('green')
    
def process_node(node):
    node.SetColor('blue')

def ignore_arc(arc):
    arc.attributes['color'] = 'red'

def bfs(graph, s, outlist):
    dist = dict()
    q = queue.Queue()
    q.put(s)
    dist[s] = 0
    while not q.empty():
        cur = q.get()
        v = graph.nodes[cur]
        d = dist[cur]
        process_node(v)
        outlist.append(graph.Visualize())
        for arc in v.arcs:
            process_arc(arc)
            if arc.end not in dist:
                put_node_in_queue(graph.nodes[arc.end])
                dist[arc.end] = d + 1
                q.put(arc.end)
            else:
                ignore_arc(arc)
                
        outlist.append(graph.Visualize())       
    return dist          
graph = Graph([
    Arc(1, 3),
    Arc(1, 4),
    Arc(4, 3),
    Arc(4, 5),
    Arc(1, 5),
    Arc(6, 4),
    Arc(5, 6),
    Arc(6, 7),
    Arc(7, 2),
    Arc(4, 2),
    Arc(3, 2)
])
bfs_outlist = []
bfs_outlist.append(graph.Visualize())
dist = bfs(graph, 1, bfs_outlist)
print(dist)
animate_list(bfs_outlist);<jupyter_output>{1: 0, 3: 1, 4: 1, 5: 1, 2: 2, 6: 2, 7: 3}
{'fraction_non_alphanumeric': 0.09907680593889788, 'fraction_numerical': 0.013990672884743505, 'mean_word_length': 3.8157653528872593, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 14, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '484119', 'license': 'MIT', 'n_tokens_mistral': 4137, 'n_tokens_neox': 4601, 'n_words': 1140, 'path': 'examples/basic_searches.ipynb', 'repo_name': 'ivanoleinik/interactive-visualization', 'size': '10507'}