Обход графа или как проехать из ... в ... на php

Здравствуйте, уважаемый разработчики. Пишу эту заметку после длительной паузы: как всегда нехватка времени или попросту неумение им распоряжаться. Но главное я опять с вами и сегодня я расскажу вам немного о графах, а точнее о поиске кратчайшего маршрута. Будем разбирать на примере поиска маршрута между станциями метро Московского метрополитена. И в конце заметки вас будет ждать маленький пример, наглядно демонстрирующий решение.

Итак, поехали. У нас имеется неориентированный граф (в метро можно проехать как от станции-источник до станции-назначение, так и наоборот). Описывать мы его будем совсем просто и очень понятно: массив, ключи которого – это станции-источник, а значения для этого ключа – станции, в которые из источника мы можем попасть. К примеру,

<?php
$graph = array(
    'Севастопольская' => array('Чертановская', 'Нахимовский проспект', 'Каховская')
);
?>

Из станции Севастопольская мы можем попасть в Чертановскую, Нахимовский проспект и в Каховскую. Единственный недостаток подобного метода описания неориентированного графа – это избыточность, но она с лихвой нивелируется простотой и наглядностью записи.

Давайте я для нетерпеливых приведу пример кода, а потом прокомментирую некоторые моменты.

<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>Графы - станции метро</title>
  </head>
  <body>
    <?php
    function find_path($graph, $start, $end, $path)
    {
      $path[] = $start;

      if ($start == $end)
         return $path;

      if (!isset($graph[$start]))
         return false;

      $shortest = array();

      foreach($graph[$start] as $node) {
   if (!in_array($node, $path)) {
     $newpath = find_path($graph, $node, $end, $path);
     if ($newpath) {
       if (!$shortest || (count($newpath) < count($shortest)))
         $shortest = $newpath;
     }
   }
      }
      return $shortest;
    }
    // определяем граф
    $graph = array(
      'Бульвар Дм. Донского' => array('Аннино'),
      'Аннино' => array('Бульвар Дм. Донского', 'Ул. ак. Янгеля'),
      'Ул. ак. Янгеля' => array('Аннино', 'Пражская'),
      'Пражская' => array('Ул. ак. Янгеля', 'Южная'),
      'Южная' => array('Пражская', 'Чертановская'),
      'Чертановская' => array('Южная', 'Севастопольская'),
      'Севастопольская' => array('Чертановская', 'Нахимовский проспект', 'Каховская'),
      'Нахимовский проспект' => array('Севастопольская', 'Нагорная'),
      'Нагорная' => array('Нахимовский проспект', 'Нагатинская'),
      'Нагатинская' => array('Нагорная', 'Тульская'),
      'Тульская' => array('Нагатинская', 'Серпуховская'),
      'Серпуховская' => array('Тульская', 'Добрынинская'),
      'Добрынинская' => array('Серпуховская', 'Полянка', 'Октябрьская', 'Павелецкая'),
      'Каховская' => array('Севастопольская', 'Варшавская'),
      'Варшавская' => array('Каховская', 'Каширская'),
      'Каширская' => array('Варшавская', 'Коломенская', 'Кантемировская'),
      'Кантемировская' => array('Каширская', 'Царицыно'),
      'Царицыно' => array('Кантемировская', 'Орехово'),
      'Орехово' => array('Царицыно', 'Домодедовская'),
      'Домодедовская' => array('Орехово', 'Красногвардейская'),
      'Красногвардейская' => array('Домодедовская')
    );
    ?>

    <?php if (isset($_POST['source']) && isset($_POST['destination'])) {
      if (in_array($_POST['source'], array_keys($graph)) &&
     in_array($_POST['destination'], array_keys($graph))) {
     $shortestPath = find_path($graph, $_POST['source'], $_POST['destination']);
     $shortestPath[0] = '<strong>' . $shortestPath[0] . '</strong>';
     $shortestPath[count($shortestPath) - 1] = '<strong>' . $shortestPath[count($shortestPath) - 1] . '</strong>';
     echo '<ul class="path">';
     foreach($shortestPath as $station) {
       echo "<li>{$station}</li>";
     }
     echo '</ul>';
      } else { ?>
      <p>Что-то пошло не так :(</p>
      <?php } ?>
    <?php } ?>
    <form method="post" action="">
      <select name="source">
   Откуда едем:
   <?php foreach(array_keys($graph) as $station) { ?>
     <option name="<?php echo $station; ?>">
       <?php echo $station; ?>
     </option>
   <?php } ?>
      </select>
      <select name="destination">
   Куда едем:
   <?php foreach(array_keys($graph) as $station) { ?>
     <option name="<?php echo $station; ?>">
       <?php echo $station; ?>
     </option>
   <?php } ?>
      </select>
      <input type="submit" value="Поехали!">
    </form>
  </body>
</html>

Строки 9-31, содержащие функцию, самые интересные и в них заключается всю изюминка алгоритма по поиску в глубину. Алгоритмы можно вкратце описать так: для вершины, которую мы еще не посетили, нужно отыскать все еще не посещенные смежные вершины и повторить поиск для них. Данная реализация взята из документации к Python, который я понемногу изучаю, и немного изменена.

Строки 33-53 описывают граф, в котором мы и будем искать кратчайший путь (я не стал описывать все станции метро, коих больше двухсот – для наглядного примера подобного участка должно хватить).

Строки 58-72 проверяют были ли переданы данные через форму, проверяют их корректность (значения, полученные из формы, должны содержаться в нашем графе) и выводят результат в виде ненумерованного списка с подсвеченными первой и последней вершинами.

В довершении мы выводим форму, состоящую из двух select-ов, содержащих станции метро и кнопки “Поехали!”, после нажатии на которую и происходит поиск по графу.

Вместо заключения хочется отметить, что графы очень интересная тема дискретной математики, позволяющая решать большое множество сложных и не очень задач.

Поменьше багов вам в коде и удачи :)

Записки Вредного программиста

enjoy, motherfuckers ;)

Комментарии