Статья Автор: Лебедев Дмитрий Алексеевич

Обработка графов - Копия

Попробуем "причесать" некоторые алгоритмы под практические задачи.
Вначале введем обозначения, которых будем стараться придерживаться:
  1. Компоненты связанности вершин Adj. 
    Adj[u] - набор вершин, с которыми вершина u соединена
    Adj = словарь <вершина, множество/словарь смежных вершин>
    получаем из входных данных (списка ребер, матрицы смежности)
  2. Множество всех вершин Vertices 
    Vertices[u] - значимые (для данной задачи) характеристики вершины
    Обычно Vertices = словарь <вершина. "значение">
    Vertшсes = dict.fromkeys(Adj, -1) - это "стандартный" способ получения 
    словаря вершин для задач, в которых надо "зачем-то обойти граф"
  3. Множество ребер/путей Edges
    Edges[(u,v)] - содержит значение, характеризующие вершины графа u, v
    (длины ребра или длину пути, весть требуемый путь и т.п.)
    Edges = словарь <пара ребер, значение>
  4. Возможно еще использование
    - множество компонент смежности (сильной связанности)
    - топологической сортироваки и др.
Для практического применения все имена сокращают до заглавной буквы, а сам граф описывают с помощью кортежа, например G(V,E) или G(A. V)
Постораемся придерживаться этого при решении задач.

В примерах, вначале будем описывать используемые объекты,
Затем в программе start - создание/инициализацию этих объёктов
Для стандартных алгоритмов DFS и BFS будем использовать расширенные названия 
типа dfs_color, bfs_dist - чтобы они были разными (в программировании принято использовать
просто dfs и bfs)



Пример 1. 
Необходимо найти компоненты связанности для неориентированного графа.
Способ задания может быть как матрицей смежности, так и списком ребер.
Входные данные 
Файл A - матрица смежности (содержит 0 - если пути нет, 1 - если путь есть)
Файл В - список ребер.
Вершинами являются 
Attached files
23.txt
23_31588_10000.txt
Печать