Поиск Эйлерового цикла в ориентированном графе

В заданном графе необходимо определить, существует ли цикл, проходящий по каждому ребру графа ровно один раз. Задача № 13 на графы (см. "Сборник задач по графам").

Немного теории:
Связный ориентированный граф содержит Эйлеров цикл тогда и только тогда, когда для каждой вершины графа её полустепень захода равна её полустепени исхода, то есть в вершину входит столько же ребер, сколько из нее выходит.

Алгоритм:
1)Считываем количество ребер и вершин.
2)Заполняем матрицу смежности.
3)Описываем процедуру, которая занимается поиском Эйлерового цикла:
а)создаем матрицу inout, в которую будем записывать, сколько ребер входит и выходит из данной вершины.
номер столбца -- вершина
0-я строка -- количество входных ребер
1-я строка -- количество выходных ребер
б)проходим по матрице смежности и заполняем матрицу inout.
в)проходим по матрице inout и сравниваем первую и вторую строку в каждом столбце. Если найдется хотя бы одно несовпадение, то Эйлерового цикла нет.
4)По результатам работы процедуры делаем вывод о существовании цикла в данном графе.

#include <stdafx.h>
#include <conio.h>
 
int matrica_smeznosti[ 50 ][ 50 ];
int top[ 50 ];
int inout[ 50 ][ 2 ];
 
int poisk_cikla( int size )
{
	int count_1, count_2;
	int id = 0;
	for( count_1 = 0; count_1 < size; count_1++ )                      //проходим по всей матрице
	{                                                                  //и считаем, сколько ребер
		for( count_2 = 0; count_2 < size; count_2++ )              //входят и выходят из каждой
		{                                                          //вершины
			if( matrica_smeznosti[ count_1 ][ count_2 ] == 1 )
			{
				inout[ count_1 ][ 0 ] += 1;                //то что получили заносим в
			}                                                  //матрицу inout, где номер
			if( matrica_smeznosti[ count_2 ][ count_1 ] == 1)  //слолбца совпадает с номером
			{                                                  //вершины
				inout[ count_1 ][ 1 ] += 1;
			}
		}
	}
	for( count_1 = 0; count_1 < size; count_1++ )                      //проходим по матрице inout
	{                                                                  //и сравниваем числа в каждом
		if( inout[ count_1 ][ 0 ] != inout[ count_1 ][ 1 ] )       //столбце, если найдется 
		{                                                          //хотя бы одно несовпадение
			id += 1;		                           //то Эйлерового цикла нет
		}
	}
	if(id == 0) return 0;
	else return 1;
}
 
int main()
{
	int versini, rebra;
	int count_1, count_2, i, j;
	printf( "VVedite kol-vo versin  i reber v grafe\n" );
	scanf( "%d %d", &versini, &rebra );
	printf( "Vvodite rebra\n" );
	for( i = 0; i < rebra; i++ )                                         //считываем колличество ребер
	{
		scanf( "%d %d", &count_1, &count_2 );                        //считываем ребра
		matrica_smeznosti[ count_1 ][ count_2 ] = 1;
	}
	if( poisk_cikla( versini ) == 0 )                                    //ищем Эйлеров путь в графе
	{
		printf( "Ailerov cikl est'\n" );
	}
	else
	{
		printf( "Cikla net\n" );
	}
	getch();
	return 0;
}

Ключевые слова: 
граф, эйлеров цикл, ребра графа
ВложениеРазмер
GRAF_13.rar8.83 кб