Шаг 177.
Основы языка Haskell. Программное представление графов в языке Haskell: матрица смежности, матрица инцидентности. Демонстрационный пример

    На этом шаге мы приведем пример, использующий матрицу смежности.

    Приведем демонстрационный пример, иллюстрирующий использование матрицы смежности при создании Haskell-приложения.

   -- Демонстрация работы с представлением графа
   -- с помощью матрицы смежности
   ---------------------------------------------------
   -- Функция находит в неориентированном графе graph,
   -- заданном с помощью матрицы смежности, список со-
   -- седей вершины x (вершин, соединённых с ней  хотя
   -- бы одним ребром)
   ------------------------------------------------
   neighbour1:: Integer -> [[Integer]] -> [Integer]
   neighbour1 x graph | x<=0 = error "Ошибка!"
                      | True = vspom 1 (graph !! 
                                        fromInteger (x-1))
   -------------------------------------------------------
   vspom:: Integer -> [Integer] -> [Integer]
   vspom i lst | null lst    = []
               | head lst==1 = i : vspom (i+1) (tail lst)
               | True        = vspom (i+1) (tail lst)
   --------------------------------------------------
   -- Неудачные тестовые примеры:
   -------------------------------
   test = neighbour1 1 [[0,1,1,0],
                        [0,0,1,0],
                        [0,0,0,1],
                        [1,0,0,0]] == [2,3]
       && neighbour1 2 [[0,1,1,0],
                        [0,0,1,0],
                        [0,0,0,1],
                        [1,0,0,0]] == [3]
       && neighbour1 3 [[0,1,1,0],
                        [0,0,1,0],
                        [1,0,1,1],
                        [1,0,0,0]] == [1,3,4]
       && neighbour1 4 [[0,1,1,0],
                        [0,0,1,0],
                        [1,0,1,1],
                        [1,0,0,0]] == [1]
Файл с примером можно взять здесь.

    На следующем шаге мы рассмотрим матрицу инцидентности.




Предыдущий шаг Содержание Следующий шаг