#pragma css /css/2010.css
<<BI>>

= Графы =
Баллы за задачи суммируются.

 1. ''(0.5)'' Дан граф (см. пример графов 1). Напишите для этого графа представление в виде матрицы смежности, списка смежных вершин, в виде таблицы соседей.
 2. ''(0.5)'' Для графа из примера 1 продемонстрируйте поиск пути от вершины `d` до вершины `l` с помощью поиска вглубь. Выбирать очередного соседа нужно в лексикографическом порядке.
 3. ''(0.5)''Для графа из примера 1 продемонстрируйте поиск кратчайшего пути от вершины `k` до вершины `e`.
 4. ''(2)'' Напишите программу, которая получает на вход описание графа в виде списка смежности (файл, в котором на каждой строке через пробел написаны два имени вершины: вершина, из которой исходит ребро, и вершина, в которую входит ребро), получает с командной строки имена вершины отправления и вершины назначения, и выписывает какой-либо путь от вершины отправления в вершину назначения с помощью поиска вглубь.
 5. ''(2)'' Напишите программу, которая получает на вход описание графа в виде списка смежности (см. выше), получает с командной строки имена вершины отправления и вершины назначения, и выписывает кратчайший путь от вершины отправления в вершину назначения с помощью поиска вширь.

== Примеры графов ==
 1. Ориентированный граф:
  {{{#!GraphViz
digraph {
 a -> b -> c -> d;
 a -> d -> c -> b;
 f -> e -> b -> a;
 e -> g -> h -> c;
 c -> h -> g -> b;
 i -> j -> b -> e -> f -> j -> p -> c;
 k -> l -> a;
 i -> b;
 k -> b;
 j -> m -> n -> o -> c;
 m -> o;
}
}}}