Графы, алгоритм посещения всех ребер в обе стороны

212

12 февраля 2019, 12:50

Никак не могу придумать адекватный алгоритм выполнения задачи, гуглил перегуглил не нашел ничего подходящего, разве что Эйлеров путь, но это немножко не то.

Суть задачи: Нужно найти такой кратчайший маршрут по графу, что бы он проходил по всем ребрам, в оба направления, сам граф задается списком ребер ( матрицей смежности тоже вариант)

Подскажите алгоритм работы

Answer 1

Эйлеров путь как раз то. Он проходит по всем рёбрам по одному разу, т.е. короче сделать нельзя.

Надо только модифицировать граф - разделить каждое ребро на две противоположно направленных дуги.

A - B     A    =>  B
|             <=
|         ^ |        
C         | v
           С

А дальше - алгоритм Хирхольцера, например. В трёх словах его описание

ПОСЛЕДНИЕ ВОПРОСЫ

Все вопросы

ТОП-10

Все популярные вопросы

Как использовать DataSource в Java

Хорошей практикой считается использовать DataSource вместо DriverManager'аВ спринге DataSource вообще используется очень часто

216

Java

Найти номер столбца и ряда элемента матрицы

Есть матрица, нужно каждый элемент вывести на экран а также вывести его ряд и столбец

151

Java

Удаленный сервер MySQL

Как сделать так, чтобы после установки на компьютер сервера MySQL 57 сделать его в виде удаленного сервера, и чтобы другие компьютеры на которых...

175

Java

Rx + Moxy + garbage collector

Всем привет!

181