Обход деревьев

Деревья

Пример 8.4.

Пример 8.3.

/*Функция вывода матрицы инцидентности */

void VivodMatrIn (int mi[NMAX][RMAX], int n, int r)

{ int i, j;

printf (“ |”);

for (j=0; j<r; j++) printf (“%3d”, j);

printf (“\n”);

for (j=0; j<3*r +2; j++) putchar(‘–’);

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

{ printf (“\n%d|”, i);

for (j=0; j<r; j++)

printf (“%3d”, mi[i][j]);

}

printf (“\n”);

}

5. Векторы смежности .

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

Векторы смежности:

Рис. 8.5. Пример графа и векторов смежности.

Для хранения векторов смежности в программе удобно использовать двумерный массив, где i-я строка – это вектор смежности для i-й вершины.

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

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

int vsm[NMAX][ NMAX+1] ; /* векторы смежности */

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

Число столбцов матрицы vsm равно NMAX+1, так как последовательность смежных вершин в каждой строке матрицы удобно хранить с признаком конца, например -1. vsm[i] – вектор смежности для i-йвершины.

Эта форма представления графа может быть использована и для ввода графа.

/* Функция ввода графа и формирования векторов смежности */

void VectSm (int vsm[NMAX][NMAX+1], int *pn)

/* Вых. данные: vsm – векторы смежности,

*pn – число вершин графа */

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

printf (“Введите число вершин:”);

scanf(“%d”, pn);

puts (Введите номера смежных вершин);

for (i = 0; i < *pn; i++)

{ printf (“%d: ”, i);

j = -1;

do scanf(“%d”, &vsm[i][++j]);

while (vsm[i][j] != -1);

}

}

Граф, представленный на рис. 8.5, вводить следует в виде (выделено жирным шрифтом):

Введите число вершин: 4

Введите номера смежных вершин

0: 1 3 -1

1: 0 2 3 -1

2: 1 -1

3: 0 1 -1

/* Вызов функции */

int vsm[NMAX][ NMAX+1] ; /* векторы смежности */

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

VectSm ( vsm, &n);

В результате выполнения функции получится матрица:

| 0 1 2 3 4

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

0 | 1 3 -1

vsm = 1 | 0 2 3 -1

2 | 1 -1

3 | 0 1 -1

6. Списки смежности .

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

Рис. 8.6. Пример графа и списков смежности.

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

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

/* тип элемента списка */

struct LIST

{ int v; /* вершина */

struct LIST *next; /* ссылка на следующий элемент */

};

struct LIST *p [NMAX]; /* массив указателей списков смежности */

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

Дерево – связанный неорентированный граф. Связанным называют граф, в котором для любых 2-х вершин существует связывающий их путь.

Корневое дерево Бинарное дерево

Бинарное дерево – дерево, у каждой вершины которого не более 2-х «сыновей».

Особенности корневого дерева:

Доступ к любой вершине от корня – путь всегда единственный и линейный.

У исходной вершины («отец») может быть несколько порождений («сыновей»), у каждого «сына» - только 1 родитель обязательно есть.