Представление графа в компьютере

Граф - это некая модель, схема, которая описывает некоторую задачу. Например, схема дорог между городами, связи между компьютерами и т. д. Важным элементом является информация о том, есть или нет связи между парой объектов (называемые вершинам графа), и если есть, то вводится дополнительная информация о связи (называемые ребрами графа): протяженность дороги, стоимость проезда, пропускная способность канала и т. д.

На рисунке представлен граф без стрелочек (называемый неориентированным графом). Если указать стрелочки, т. е. направление, то это будет ориентированный граф:

Чтобы описать граф обычно используют двумерный массив (матрица) или связный список.
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	-1	0	1	-1	0	0	0	0
3	0	0	0	1	0	-1	1	0
4	0	0	-1	0	1	0	0	1
5	0	1	0	0	1	1	0	0
6	0	0	0	0	0	0	1	-1

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
 |
V
2->1->3->4
 |
V
3->2->4->5->6
 |
V
4->2->3->6
 |
V
5->1->3
 |
V
6->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
    ptrspisok=^spisok;
    spisok=record
       info: integer;
       left: ptrspisok;
       right:ptrspisok;
     end;
var root:ptrspisok; - указатель на корень дерева;
      s:ptrspisok; - указатель на текущий элемент списка.

И для списка ребер (вершин):
type
    ptrspisok1=^spisok1;
    spisok1=record
       info: integer;
       ves: real;
       next:ptrspisok;
   end;

    ptrspisok=^spisok;
    spisok=record
       info: integer;
       curr:ptrspisok1;
       next:ptrspisok;
    end;
var root:ptrspisok; - указатель на начало списка;
      s:ptrspisok; - указатель на текущий элемент списка.

Как работать со списком - это тема другого сообщения.