1 Лекция 6 Графы

2 Граф – это множество вершин и соединяющих их ребер. Примеры графов:

3 Схема алгоритма – размеченный орграф, где вершинами являются блоки алгоритма, а дугами – линии передачи управления. Система дорог – взвешенный размеченный граф, где вершины – города, а ребра – дороги между городами. Вес ребра – длина дороги, метка вершины – название города. Если дороги односторонние, то граф – ориентированный.

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

5 Если в таком виде хранить граф в памяти, нужно описать два параллельных массива для хранения смежных вершин. Например: #defineNMAX10/* макс. число вершин */ #defineRMAX100/* макс. число ребер */ int v1 [RMAX];/* массивы смежных */ int v2 [RMAX];/* вершин*/ int n;/* число вершин графа */ int r;/* число ребер графа */

6 2. Матрица смежности – это квадратная матрица размерности n*n (n – число вершин), в которой элемент ms[i][j] = 1, ли есть дуга i –> j, и = 0 в противном случае. Пример матрицы смежности для графа, представленного на рис. а): | | Для неориентированного графа матрица 1 | смежности симметрична относительно 2 | главной диагонали. 3 | | |

7 Пример ввода неориентированного графа в виде последовательности ребер и формирования матрицы смежности. #defineNMAX10/* макс. число вершин */ /* Функция ввода графа */ int VvodGraf ( int ms [NMAX] [NMAX] ) /* ms – матрица смежности */ /* Возвращаемое значение – число вершин графа */ { int n;/* число вершин графа */ int i, j;/* номера вершин */ puts (\nВведите число вершин графа (

8 /* Обнуление матрицы смежности */ for (i=0; i

9 3. Матрица весов – квадратная матрица размерности n*n (n – число вершин), в которой элемент mw [i][j] = вес дуги i –> j Например, дана система дорог: вершины – города, ребра – дороги. Вес ребра – длина дороги.

10 Описание на языке С: #defineNMAX10 /* макс. число вершин */ int mw[NMAX][ NMAX] ; /* матрица весов */ int n; /* число вершин */

11 4. Матрица инцидентности – это прямоугольная матрица размерности n*r (n – число вершин, r – число ребер). Для неориентированного графа элемент матрицы: 1, если i-я вершина инцидентна j-му ребру, mi[i][j] = 2, если j-е ребро – петля i-й вершины, 0, если i-я вершина не инцидентна j-му ребру.

12 Для орграфа элемент матрицы инцидентности: -1, если j-я дуга выходит из i-й вершины mi[i][j] = 1, если j-я дуга входит в i-ю вершину 2, если j-я дуга – петля i-й вершины, 0, если i-я вершина не инцидентна j-й дуге.

13 Описание на языке С: #defineNMAX 10/* макс. число вершин */ #defineRMAX 100/* макс. число ребер (дуг) */ int mi[NMAX][ RMAX]; /* м-ца инцидентности */ int n; /* число вершин */ int r; /*число ребер */

14 5. Векторы смежности. Для каждой вершины в векторе хранятся номера смежных с ней вершин. Векторы смежности:

15 Описание на языке С: #defineNMAX10 /* макс. число вершин */ int vsm[NMAX][ NMAX+1]; /* векторы смежности */ int n; /* число вершин */ Число столбцов матрицы vsm равно NMAX+1, так как последовательность смежных вершин в каждой строке матрицы удобно хранить с признаком конца, например -1. vsm[i] – вектор смежности для i-й вершины.

16 Эта форма представления графа может быть использована и для ввода графа. Пример. Введите число вершин: 4 Введите номера смежных вершин 0: : : :

17 6. Списки смежности. Для каждой вершины хранится список смежных с ней вершин.

18 Описание на языке С: #defineNMAX10/* макс. число вершин */ /* тип элемента списка */ struct LIST { int v; /* вершина */ struct LIST *next; /* ссылка на следующий элемент */ } struct LIST *p [NMAX];/* массив указателей списков смежности */ int n; /* число вершин */