Написать алгоритм обхода графа
Привет,
Нужен алгоритм на Java.
Есть направленный граф, представленный в виде совокупности номеров вершин (1,2) (2,5) (3,6) и т.д. Первый элемент - начало, второй - конец. Вершина в себя же (1,1) идти не может.
Граф строится постепенно. Нужна функция, при каждом добавлении пары проверяющая, не приведет ли это к кольцу (возврат false) или true, если не приведет.
Пример: уже есть (1,2)(2,3), пытаемся добавить (3,1) - результат false. Если (1,3) - то true.
Граф может содержать до 2 тыс вершин, поэтому рекурсию использовать не надо :) Критерий выполнения работы - отработка алгоритма на графе с 2 тысячами вершин.
Заполнение графа происходит последовательно в 1 потоке.
Нужен алгоритм на Java.
Есть направленный граф, представленный в виде совокупности номеров вершин (1,2) (2,5) (3,6) и т.д. Первый элемент - начало, второй - конец. Вершина в себя же (1,1) идти не может.
Граф строится постепенно. Нужна функция, при каждом добавлении пары проверяющая, не приведет ли это к кольцу (возврат false) или true, если не приведет.
Пример: уже есть (1,2)(2,3), пытаемся добавить (3,1) - результат false. Если (1,3) - то true.
Граф может содержать до 2 тыс вершин, поэтому рекурсию использовать не надо :) Критерий выполнения работы - отработка алгоритма на графе с 2 тысячами вершин.
Заполнение графа происходит последовательно в 1 потоке.