Пример 20.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. Векторы смежности .

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

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

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

 

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

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

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

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

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

 

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

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