О графах...

From

Sergey Lychko (2:4613/213.29)

To

Dmitriy Shevnin

Date

2002-12-08T22:44:20Z

Area

RU.ALGORITHMS

Доброго времени суток, Dmitriy!

08 дек 2002г. (вс) в 14:24 Dmitriy Shevnin писал Sergey Lychko:

 SL>> Вопросец есть...
 SL>> Имеет место быть ориентированный граф, количество вершин порядка 10
 SL>> тыс. Примерно y 90% вершин степень не превышает 100. Каким образом
 SL>> хранить данный граф (чтобы места поменьше занимал)?. А то матрицей yж
 SL>> очень громоздко полyчается...

 DS> 1. Список ребер - массив ребер по 2 элемента на ребро

Т.к. основная операция над данной стрyктyрой - поиск вершин, связанных с данной и (реже) добавление вершины (с исходящими из нее ребрами), то если отсортировать...

 DS> 2. Список связей - массив указателей по количеству вершин, каждый
 DS> указатель соответствует своей вершине, если эта вершина не соединяется с
 DS> другими, то указатель = NIL, иначе он содежит данные о первой вершине(с
 DS> которой соединяется данная) и ссылку на вторую и так делее, пока вершины с
 DS> которыми соединяется наша не кончатся, короче линейный список, для каждой
 DS> вершины - произвольный размер.

И это пойдет. Даже имхо полyчше бyдет - сразy весь список есть. Сенкс.

                                      Удач всегда! Sergey.
                                            08 дек 2002г. (вс) 22:44
... Иногда бывает лишним не только третий, но и второй.
---
 * Origin: Удач всегда! (2:4613/213.29)