Добрый день. Сегодня хочу рассказать о одном из тестовых заданий на должность C# разработчика. Задача связана с работой с графами.
Задание звучит следующим образом:
В некотором городе есть метро, которое состоит из N (1 <= N <= 1000) станций и M линий, соединяющих эти станции. Каждая линия соединяет два станции, каждая линия является двунаправленной. Между двумя станциями может быть только одна соединяющая линия. Схема метро такая, что абсолютно все станции связаны (в том числе и через промежуточные станции).
По введенной информации о схеме метро необходимо найти допустимый порядок закрытия станций метро таким образом, что оставшиеся открытые станции всегда были связаны. Например, возьмем схему метро на изображении:
Станции можно закрывать, например, в следующем порядке 1, 2, 4, 3, 5. А порядок 3, 1, 2, 4, 5 – не подходит, т.к. после закрытия 3-й станции метро распадется на четыре не связанных между собой части.
Входные данные. Первая строка входного файла содержит целые числа N и M. Следующие M строк содержат информацию о линиях метро. Каждая из этих строк содержит через пробел значения Ai и Bi (Ai <> Bi) – две станции, которые соединяет i-я линия.
Выходные данные. Выходной файл содержит N строк. Каждая строка представляет собой название станции. Станции должны идти в порядке их закрытия.
Данную задачу я решал через использование матрицы соединений, размерностью N×M, где N - количество узлов, а M - количество линий.
В данном случае достаточно использовать консольное приложение. Структура логики работы приложения следующая:
Класс Program c методом Main - обычный классический класс для консольных приложений, который генерируется автоматически.
ReaderTxtFile - статический класс, который нужен только для открытия и чтения текстового документа.
Статический класс WriteTxtFile - нужен для записи результата в файл.
Также есть статический класс Wood - в нём создаётся матрица соединений и поиск решения.
Исходный код можно посмотреть тут.
Сущности с отдельными ролями созданы. Данная задача легко решается в функциональном стиле.
Алгоритм решения следующий:
- Чтение файла.
- Создание матрицы соединений.
- Обработка матрицы соединений.
- Запись результата обработки в файл.
Матрица создаётся простым способом:
Рассмотрим на примере из задания:
Первая строчка входных данных - это количество узлов и соединений. Создадим матрицу размерность 5 на 4.
Далее перебираем уже сами данные о соединении. Например 3 - 1.
Тогда матрица будет выглядеть следующим образом:
Далее 3 - 2:
Запишу сразу остальные соединения: 3-4 и 3-5.
Теперь внимательно посмотрим на матрицу:
У каждого столбца явно видно, сколько у него находится соединений.
Теперь для решения задачи необходимо выключать станции по увеличению количества соединений. В данном случае: 1,2,4,5,3.
1,2,4,5 - они крайние и имею только по одному соединению. А потом будет уже последняя станция 3.
Я сделал обработку матрицы соединений рекурсивно.
Переменная countIteration была задана до начала работы рекурсивного метода и равна 1, которая говорит- какое количество соединений мы ищем.
Сама рекурсия начинается с "пробежки" по колонкам матрица, задавая переменную локального количества найденных не нулевых значений (localCount) на каждой новой итерации. Далее открывался цикл "по строкам" и если значение не равно 0 => добавлял 1 к переменной localCount. Потом проводилась проверка с переменной countIteration и если они были равны - узел записывался в результирующий список.
На выходе из цикла "по колонкам" к переменной countIteration добавлялась 1.
А дальше была проверка - если количество записанных узлом равнялось максимальному из них по значению, то выход из метода, иначе метод вызывался снова, но уже с countIteration = 2, то есть с 2 соединениями узла и так до конца, пока не будут выключены все узлы.
Вот и всё. Данный код был написан за вечер и в нём(на момент написания статьи) есть некоторые ошибки в названиях переменных и методов, к тому же можно код оптимизировать и сделать более красивым и приятным глазу. Этим я займусь в следующей статье.
Напоминаю: код доступен на Github.
Спасибо за уделённое мне время, надеюсь статья была полезной и понятной.
