Задача
В неориентированном графе найти компоненту связности заданной вершины.
В графе могут быть петли и кратные ребра.
Входные данные: В первой строке записаны сначала два числа N, M и start, задающие соответственно количество вершин, количество ребер и стартовую вершину ( вершины нумеруются от 0 до N-1), а затем перечисляются ребра. Каждое ребро задается двумя номерами вершин, которые оно соединяет.
Выходные данные: Состав компоненты связности (в произвольном порядке)
Ниже приведено возможное решение (Программа BFS-01) этой задачи. Граф задан списком ребер, поэтому при решении используется словарь.
Использование словаря позволяет решать задачу для "нечисловых" графов и "сильно разряженных" графов.
Замечание: для que можно использовать структуру Queue (очередь) модуля queue (экономии памяти), Это будет сделано в следующем примере
Проверьте это решение на следующием наборе данных.
8 7 1
1 2
2 3
3 4
4 1
5 6
6 7
0 7