Пример 8.1.

Представление графов

Рассмотрим наиболее распространенные формы представления графов.

1. Последовательность ребер (дуг), перед которой указывается количество вершин графа. Каждое ребро (дуга) задается парой смежных вершин. Такая форма удобна для внешнего представления графа при его вводе.

Пример для рис. 8.1.в:

5 - число вершин

0 1

1 2

2 3

2 4

3 4

4 0

4 2

Если в таком виде хранить граф в памяти, нужно описать два параллельных массива для хранения смежных вершин.

#define NMAX 10 /* макс. число вершин */

#define RMAX 55 /* макс. число ребер */

/* RMAX = NMAX * (NMAX - 1) / 2 + NMAX; */

int v1 [RMAX]; /* массивы смежных */

int v2 [RMAX]; /* вершин */

int n; /* число вершин графа */

int r; /* число ребер графа */

2. Матрица смежности – это квадратная матрица размерности n*n (n – число вершин), в которой элемент

1, ли есть дуга i –> j ,

ms[i][j] =

0 в противном случае.

Пример матрицы смежности для графа, представленного на рис. 13.1.а:

| 0 1 2 3 4 5

----------------------------

0 | 0 1 0 0 0 1 Для неориентированного графа матрица

1 | 1 0 1 1 1 0 смежности симметрична относительно

2 | 0 1 0 0 0 0 главной диагонали.

3 | 0 1 0 0 1 1

4 | 0 1 0 1 0 0

5 | 1 0 0 1 0 0

Пример 8.2. Ввод с клавиатуры неориентированного графа в виде последовательности ребер и формирование матрицы смежности. Конец ввода ребер отмечается нажатием клавиш Ctrl – Z (конец файла).

#define NMAX 10 /* макс. число вершин */

/* Функция ввода графа */

int VvodGraf ( int ms [NMAX] [NMAX] )

/* ms – матрица смежности */

/* Возвращаемое значение – число вершин графа */

{ int n; /* число вершин графа */

int i, j; /* номера вершин */

puts (“\nВведите число вершин графа (<=10)”);

scanf (“%d”, &n);

/* Обнуление матрицы смежности */

for (i=0; i<n; i++)

for (j=0; j<n; j++) ms[i][j] = 0;

puts (“Введите последовательность ребер, завершив ввод ”);

puts (“нажатием Ctrl-Z”);

while (scanf(“%d %d”, &i,&j) !=EOF)

ms[i][j] = ms[j][i] = 1;

return n;

}

/* Главная функция */

void main()

{ int g[NMAX][ NMAX] ; /* матрица смежности */

int n; /* число вершин графа */

…

n = VvodGraf (g); /* вызов функции ввода графа */

…

}

3. Матрица весов – квадратная матрица размерности n*n (n – число вершин), в которой элемент

mw [i][j] = вес дуги i –> j

Например, дана система дорог: вершины – города, ребра – дороги. Вес ребра – длина дороги.

50 45 | 0 1 2 3 4 5

------------------------

30 60 0 | 0 50 0 0 0 100

30 1 | 50 0 45 60 30 0

100 mw = 2 | 0 45 0 0 0 0

60 3 | 0 60 0 0 30 60

4 | 0 30 0 30 0 0

5 | 100 0 0 60 0 0

Рис. 8.2. Пример системы дорог и матрицы весов.

Описание на языке С:

#define NMAX 10 /* макс. число вершин */

int mw[NMAX][ NMAX] ; /* матрица весов */

int n; /* число вершин */

4. Матрица инцидентности – это прямоугольная матрица размерности n*r ( n – число вершин, r – число ребер).

Для неориентированного графа элемент матрицы:

1, если i-я вершина инцидентна j-му ребру,

mi[i][j] = 2, если j-е ребро – петля i-й вершины,

0, если i-я вершина не инцидентна j-му ребру.

| 0 1 2 3 4 5 6

1 ----------------------------------

0 2 6 0 | 1 0 0 0 0 1 0

4 1 | 1 1 1 0 1 0 0

mi = 2 | 0 1 0 0 0 0 2

3 3 | 0 0 1 1 0 0 0

5 4 | 0 0 0 1 1 1 0

Рис. 8.3. Пример графа и матрицы инцидентности.

Для орграфа элемент матрицы инцидентности:

-1, если j-я дуга выходит из i-й вершины j

mi[i][j] = 1, если j-я дуга входит в i-ю вершину j

2, если j-я дуга – петля i-й вершины,

0, если i-я вершина не инцидентна j-й дуге.

| 0 1 2 3 4 5

0 1 -------------------------------

0 | -1 0 0 1 0 0

4 mi = 1 | 1 -1 0 0 1 0

3 2 2 | 0 1 1 0 0 0

3 | 0 0 -1 -1 -1 2

Рис. 8.4. Пример орграфа и матрицы инцидентности.

Описание на языке С:

#define NMAX 10 /* макс. число вершин */

#define RMAX 100 /* макс. число ребер (дуг) */

int mi[NMAX][ RMAX] ; /* матрица инцидентности */

int n; /* число вершин */

int r; /*число ребер */