хранение адресов на элементы графа (дуг)

теперь то же, но по-русски

Граф:

1 -- 2 -- 4
|    |
3    5--6

Матрица:
  1 2 3 4 5 6
1 0 1 1 0 0 0
2 1 0 0 1 1 0
3 1 0 0 0 0 0
4 0 1 0 0 0 0
5 0 1 0 0 0 1
6 0 0 0 0 1 0

std::vector =)

Вообще-то, ответ на вопрос зависит от алгоритмов,
 которыми ты будешь обрабатывать свой граф.


Если теоретически: смотри реализации разреженных матриц.


> хранить адреса в массиве, но при этом ограничено количесво дуг для одного элемента графа

Перенумеруй вершины -- получешь индекс i (i=1..n) массива Vertex[].
 Значения массива Vertex[i] -- ссылки на списочные структуры,
 которые есть перечисления вершин, с которыми соединяется Vertex[i].

> Граф:
>
> 1 -- 2 -- 4
> |    |
> 3    5--6
>
> Матрица:
>    1: 2: 3: 4: 5: 6:
> 1: 0  1  1  0  0  0
> 2: 1  0  0  1  1  0
> 3: 1  0  0  0  0  0
> 4: 0  1  0  0  0  0
> 5: 0  1  0  0  0  1
> 6: 0  0  0  0  1  0


Хранение в строках текстового файла:

ориентированное представление дуг (векторов):
1: 2 3
2: 1 4 5
3: 1
4: 2
5: 2 6
6: 5

неориентированное представление дуг:
1: 2 3
2: 4 5
3: 
4: 
5: 6
6: 

Который удобно парсить в массив списков и редактировать вручную редактором.
(парсинг ч/з пробельные символы до конца строки)

P.S. http://www.linux.org.ru/view-message.jsp?msgid=1848770

:-)