ݺߣ

ݺߣShare a Scribd company logo

лекция 6

•Download as PPT, PDF•
•
Zhanna Kazakova
Zhanna Kazakova
1 of 18
Downloaded 12 times
Лекция 6 Графы
Граф – это множество вершин и соединяющих их ребер. Примеры графов:
Примеры графов: Схема алгоритма – размеченный орграф, где вершинами являются блоки алгоритма, а дугами – линии передачи управления. Система дорог – взвешенный размеченный граф, где вершины – города, а ребра – дороги между городами. Вес ребра – длина дороги, метка вершины – название города. Если дороги односторонние, то граф – ориентированный.
Представление графов 1. Последовательность ребер (дуг ) , перед которой указывается количество вершин графа. Каждое ребро (дуга) задается парой смежных вершин. Такая форма удобна для внешнего представления графа при его вводе. Пример: 5 - число вершин 0 1 1 2 2 3 2 4 3 4 4 0 4 2
Если в таком виде хранить граф в памяти, нужно описать два параллельных массива для хранения смежных вершин. Например: # define NMAX 10 /* макс. число вершин */ # define RMAX 100 /* макс. число ребер */ int v 1 [ RMAX ]; /* массивы смежных */ int v2 [RMAX]; /* вершин */ int n ; /* число вершин графа */ int r ; /* число ребер графа */
2. Матрица смежности – это квадратная матрица размерности n * n ( n – число вершин), в которой элемент ms [ i ][ j ] = 1, ли есть дуга i –> j , и = 0 в противном случае. Пример матрицы смежности для графа, представленного на рис. а) : | 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
Пример ввода неориентированного графа в виде последовательности ребер и формирования матрицы смежности. # 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 Например, дана система дорог: вершины – города, ребра – дороги. Вес ребра – длина дороги.
Описание на языке С: # 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 -му ребру.
Для орграфа элемент матрицы инцидентности: -1, если j -я дуга выходит из i -й вершины mi [ i ][ j ] = 1, если j -я дуга входит в i -ю вершину 2, если j -я дуга – петля i -й вершины, 0, если i -я вершина не инцидентна j -й дуге.
Описание на языке С: # define NMAX 10 /* макс. число вершин */ # define RMAX 100 /* макс. число ребер (дуг) */ int mi [ NMAX ][ RMAX ]; /* м-ца инцидентности */ int n ; /* число вершин */ int r ; /* число ребер */
5. Векторы смежности . Для каждой вершины в векторе хранятся номера смежных с ней вершин. Векторы смежности:
Описание на языке С: # define NMAX 10 /* макс. число вершин */ int vsm [ NMAX ][ NMAX +1]; /* векторы смежности */ int n ; /* число вершин */ Число столбцов матрицы vsm равно NMAX +1 , так как последовательность смежных вершин в каждой строке матрицы удобно хранить с признаком конца, например -1. vsm [ i ] – вектор смежности для i -й вершины.
Эта форма представления графа может быть использована и для ввода графа. Пример. Введите число вершин: 4 Введите номера смежных вершин 0: 1 3 -1 1: 0 2 3 -1 2: 1 -1 3: 0 1 -1
6. Списки смежности . Для каждой вершины хранится список смежных с ней вершин.
Описание на языке С: # define NMAX 10 /* макс. число вершин */ /* тип элемента списка */ struct LIST { int v; /* вершина */ struct LIST * next ; /* ссылка на следующий элемент */ } struct LIST *p [NMAX]; /* массив указателей списков смежности */ int n; /* число вершин */

More Related Content

лекция 6

  • 2. Граф – это множество вершин и соединяющих их ребер. Примеры графов:
  • 3. Примеры графов: Схема алгоритма – размеченный орграф, где вершинами являются блоки алгоритма, а дугами – линии передачи управления. Система дорог – взвешенный размеченный граф, где вершины – города, а ребра – дороги между городами. Вес ребра – длина дороги, метка вершины – название города. Если дороги односторонние, то граф – ориентированный.
  • 4. Представление графов 1. Последовательность ребер (дуг ) , перед которой указывается количество вершин графа. Каждое ребро (дуга) задается парой смежных вершин. Такая форма удобна для внешнего представления графа при его вводе. Пример: 5 - число вершин 0 1 1 2 2 3 2 4 3 4 4 0 4 2
  • 5. Если в таком виде хранить граф в памяти, нужно описать два параллельных массива для хранения смежных вершин. Например: # define NMAX 10 /* макс. число вершин */ # define RMAX 100 /* макс. число ребер */ int v 1 [ RMAX ]; /* массивы смежных */ int v2 [RMAX]; /* вершин */ int n ; /* число вершин графа */ int r ; /* число ребер графа */
  • 6. 2. Матрица смежности – это квадратная матрица размерности n * n ( n – число вершин), в которой элемент ms [ i ][ j ] = 1, ли есть дуга i –> j , и = 0 в противном случае. Пример матрицы смежности для графа, представленного на рис. а) : | 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
  • 7. Пример ввода неориентированного графа в виде последовательности ребер и формирования матрицы смежности. # define NMAX 10 /* макс. число вершин */ /* Функция ввода графа */ int VvodGraf ( int ms [NMAX] [NMAX] ) /* ms – матрица смежности */ /* Возвращаемое значение – число вершин графа */ { int n ; /* число вершин графа */ int i , j ; /* номера вершин */ puts (“n Введите число вершин графа (<=10)”); scanf (“%d”, &n);
  • 8. /* Обнуление матрицы смежности */ 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); /* вызов ф-ции ввода графа */ … }
  • 9. 3. Матрица весов – квадратная матрица размерности n * n ( n – число вершин), в которой элемент mw [i][j] = вес дуги i –> j Например, дана система дорог: вершины – города, ребра – дороги. Вес ребра – длина дороги.
  • 10. Описание на языке С: # define NMAX 10 /* макс. число вершин */ 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. Описание на языке С: # define NMAX 10 /* макс. число вершин */ # define RMAX 100 /* макс. число ребер (дуг) */ int mi [ NMAX ][ RMAX ]; /* м-ца инцидентности */ int n ; /* число вершин */ int r ; /* число ребер */
  • 14. 5. Векторы смежности . Для каждой вершины в векторе хранятся номера смежных с ней вершин. Векторы смежности:
  • 15. Описание на языке С: # define NMAX 10 /* макс. число вершин */ int vsm [ NMAX ][ NMAX +1]; /* векторы смежности */ int n ; /* число вершин */ Число столбцов матрицы vsm равно NMAX +1 , так как последовательность смежных вершин в каждой строке матрицы удобно хранить с признаком конца, например -1. vsm [ i ] – вектор смежности для i -й вершины.
  • 16. Эта форма представления графа может быть использована и для ввода графа. Пример. Введите число вершин: 4 Введите номера смежных вершин 0: 1 3 -1 1: 0 2 3 -1 2: 1 -1 3: 0 1 -1
  • 17. 6. Списки смежности . Для каждой вершины хранится список смежных с ней вершин.
  • 18. Описание на языке С: # define NMAX 10 /* макс. число вершин */ /* тип элемента списка */ struct LIST { int v; /* вершина */ struct LIST * next ; /* ссылка на следующий элемент */ } struct LIST *p [NMAX]; /* массив указателей списков смежности */ int n; /* число вершин */