Меню сайта
Наш опрос
Оцените мой сайт
Всего ответов: 6
Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0
Главная » 2014 » Июль » 22 » Представление графа в компьютере
15:26
Представление графа в компьютере
Граф - это некая модель, схема, которая описывает некоторую задачу. Например, схема дорог между городами, связи между компьютерами и т. д. Важным элементом является информация о том, есть или нет связи между парой объектов (называемые вершинам графа), и если есть, то вводится дополнительная информация о связи (называемые ребрами графа): протяженность дороги, стоимость проезда, пропускная способность канала и т. д.На рисунке представлен граф без стрелочек (называемый неориентированным графом). Если указать стрелочки, т. е. направление, то это будет ориентированный граф:Чтобы описать граф обычно используют двумерный массив (матрица) или связный список.1) Матрица инциденций:строки-номера вершин; столбцы-номера ребер; если от вершины i идет ребро j, то на пересечении i-ой строки с j-ым столбцом стоит ее вес или 1, все остальные значения равны 0. 1 2 3 4 5 6 7 8 1 1 1 0 0 0 0 0 0 2 0 0 1 0 0 0 0 0 3 0 0 0 1 1 0 1 0 4 0 0 0 0 0 0 0 1 5 0 1 0 0 0 1 0 0 6 0 0 0 0 0 0 0 0 2) Матрица смежности:строки и столбцы -номера вершин; если из вершины i в вершину j есть ребро, то на пересечении i-ой строки с j-ым столбцом стоит ее вес или 1, все остальные значения равны 0. 1 2 3 4 5 6 1 0 1 0 0 1 0 2 0 0 0 1 0 0 3 0 0 0 0 0 1 4 0 0 1 0 0 1 5 1 0 1 0 0 0 6 0 0 0 0 0 0 Эти два способа занимают много места из-за их разреженности (много нулей).3) Матрица списка ребер:в 1-ой строке - номера вершин, из которых есть ребро; во 2-й строке - номера вершин, в которую это ребро направлено; в 3-ей строке - вес ребра. 1 2 3 4 5 6 7 1 1 1 2 2 3 3 3 2 2 5 3 4 4 5 6 Если вес не указан, то 3-я строчка не используется. 4) Другой список: 0 1 2 3 4 5 6 1 2 2 5 0 0 0 0 2 3 1 3 4 0 0 0 3 4 2 4 5 6 0 0 4 3 2 3 6 0 0 0 5 2 1 3 0 0 0 0 6 2 3 4 0 0 0 0 В каждой I-ой строке сначала записывается количество ребер, которые выходят из i-ой вершины, а затем перечисления номеров вершин, к которым эти ребра направлены. Можно и без нулевого столбца.5) Связный список обычно используется для хранения большего количества информации об объекте или весе. Поле next направляет к следующей вершине, не обязательно соединенной с предыдущей. В поле info - информация о начале списка вершин, к которым есть ребра из данной вершины. Кроме этого в этом списке можно хранить информацию о весе ребер и другую информацию:1->2->5 | V2->1->3->4 | V3->2->4->5->6 | V4->2->3->6 | V5->1->3 | V6->3->4Это похоже на предыдущий список без нулевого столбца и без лишних нулевых элементов. Такой способ наиболее экономичен.Кроме обычных графов в задачах используют бинарные деревья (ориентированный граф):Здесь вершина 1 называется корнем, от которого выходят две ветви: левая 2 и правая 3. Вершина 2 является листом дерева, т.к. из него нет ребер, а вершина 3 - подкорнем, у которого тоже есть листья 4 (левое) и 5 (правое).Такое дерево тоже можно описать в виде матрицы списка ребер: 1 2 3 1 1 2 3 2 2 0 0 3 3 4 5 4 4 0 0 5 5 0 0 где1-й столбец - номера вершин, первый в списке - это корень дерева;2-й столбец - номера левых вершин;3-й столбец - номера правых вершин.Если есть веса ребер, то можно добавить еще 2 столбца. Или в виде связного списка, у которого вместо поля next есть два поля left и right - указатели на левую и правую вершину.Немного о типе "связный список" для бинарного дерева:type   
Просмотров: 165 | Добавил: admin | Рейтинг: 0.0/0
Всего комментариев: 0
avatar
Форма входа
Календарь
«  Июль 2014  »
ПнВтСрЧтПтСбВс
 123456
78910111213
14151617181920
21222324252627
28293031
Архив записей