Модели и структуры данных





Матричное представление орграфов.



МАТРИЧНОЕ ПРЕДСТАВЛЕНИЕ ОРГРАФОВ.

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

Например, для простого ориентированного графа, изображенного на рис.6.2 массив определяется как:

mas:array[1..4,1..4]=((0,1,0,0),(0,0,1,1),(0,0,0,1),(1,0,1,0))

Матрицы смежности применяются, когда в графе много связей и матрица хорошо заполнена.









Содержание    Назад    Вперед