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