Все выпуски  

RFpro.ru: Программирование на C / C++


РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты в разделе

Коцюрбенко Алексей aka Жерар
Статус: Мастер-Эксперт
Рейтинг: 268
∙ повысить рейтинг »
mklokov
Статус: 5-й класс
Рейтинг: 104
∙ повысить рейтинг »
CradleA
Статус: Профессионал
Рейтинг: 58
∙ повысить рейтинг »

∙ С / С++

Номер выпуска:1909
Дата выхода:04.06.2017, 20:15
Администратор рассылки:Андрей Кузнецов aka Dr_Andrew (Старший модератор)
Подписчиков / экспертов:26 / 20
Вопросов / ответов:1 / 1

Консультация # 191080: Здравствуйте! Прошу помощи в следующем вопросе: задача найти и вывести Эйлеров путь. Граф неориентированный. Задан списками смежности в текстовом файле. Начальную вершину для обхода задать с клавиатуры. На Си или С++. Додумалась до отдельных (к сожалению, не самых важных) фрагментов, не могу их связать и дополнить до рабочего состояния: 1)...

Консультация # 191080:

Здравствуйте! Прошу помощи в следующем вопросе:
задача найти и вывести Эйлеров путь. Граф неориентированный. Задан списками смежности в текстовом файле. Начальную вершину для обхода задать с клавиатуры. На Си или С++.
Додумалась до отдельных (к сожалению, не самых важных) фрагментов, не могу их связать и дополнить до рабочего состояния:
1) придумала граф с двумя вершинами нечетной степени (т.к. путь, а не цикл), составила списки смежности, вот как это выглядит в файле:
3 2 3 5
2 1 3
3 1 2 4
2 3 5
2 1 4
2) понимаю, что данные в программе должны хранится в виде списка (однонаправленного?), а вершина должна быть представлена через тип данных struct, пусть вот так:
typedef struct ListNode_
{
int info; //здесь номера вершин
ListNode_* next; //здесь указатель на следующий элемент
}ListNode; //новое имя типа
3) понимаю, что надо скопировать данные в программу через два цикла:
int i, j;
FILE * f = fopen("graph. txt", "r");
for(int i = 0; !feof(f); i++)
{
int n1;
fscanf(f, "%d", &n1); //переменная для считывания количества смежных вершин
for(j = 0; j < n1; j++)
{
int a; //переменная для номеров смежных вершин
fscanf(f, "%d", &a);
//думала дальше присваивание сделать, но появилось много вопросов
//например, если начать так:
ListNode* pCur = (ListNode*)malloc(sizeof(ListNode));
pCur ->info = a; //поместить номер вершины
...
то получается, что есть несколько экземпляров обособленных значений вершин.
Не понимаю, как связать все указателями и вывести на экран, чтобы убедиться в правильном заполнении списка.
4) где-то (?) необходимо объявить указатель на начало:
ListNode* BEGIN[n];
n - можно задать через #define
5) запросить вершину тоже понятно как:
in t firstNode;
printf("Введите номер вершины с нечетной степенью, с которой будет начат обход:\n");
scahf("%d", &First);
6)...до поиска Эйлерова пути даже не дошла.
Простите, если сумбурно))
Пожалуйста, помогите заполнить пробелы и объединить все в программу!

Дата отправки: 30.05.2017, 19:53
Вопрос задал: pNod (Посетитель)
Всего ответов: 1
Страница онлайн-консультации »


Консультирует Лысков Игорь Витальевич (Старший модератор):

Здравствуйте, pNod!
У меня получилась следующая программа.
Сделана из такого понимания списка смежности:
в каждой строке задается количество и номера соседей для каждого узла графа.
Узлы объедены не в список, а в массив. Получилось что-то похожее на двумерный массив...
Введен дополнительный массив ребер. Количество ребер равно половине сумм количеств соседей всех вершин.
Программа для заданного начального узла находит только один путь.
Поиск реализован рекурсивно. Достаточно неочевидно, но, думаю, разберетесь smile smile

#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
 
typedef struct ListNode
{
	int			count;		//количество соседей текущего узла
	int			idx;		//индекс по соседям (для поиска)
	int*		node;		//массив номеров узлов соседей (как в файле)
}ListNode;

typedef struct EDGE
{
	int			a;
	int			b;
}EDGE;

//Определим некоторые переменные в глобальной памяти
// (для удобства, чтобы не передавать параметрами)

ListNode*	list = NULL;		//адрес массива узлов графа
int			edgesFullCnt;		//количество ребер графа
EDGE*		edgesPath = NULL;	//адрес массива ребер пути

//поиск ребра в массиве предыдущего пути
//параметры: номера узлов ребра и длина найденного пути
bool CmpEdge(int a1, int b1, int edgesPathCnt)
{
	int		i, a2, b2, temp;
	//отсортируем, чтобы было a1 < b1
	if (a1 > b1)
	{
		temp = a1;
		a1 = b1;
		b1 = temp;
	}

	//сравним ребро со всеми ребрами уже найденного пути
	for (i=0; i<edgesPathCnt; i++)
	{
		//получаем очередное ребро, как пару номеров вершин
		//отсортируем, чтобы было a2 < b2
		a2 = edgesPath[i].a;
		b2 = edgesPath[i].b;
		if (a2 > b2)
		{
			temp = a2;
			a2 = b2;
			b2 = temp;
		}
		//проверяем на совпадение
		if ((a1 == a2) && (b1 == b2))
			return true;				//ребро найдено
	}
	return false;						//не найдено
}

//поиск пути
//параметры:
//номер узла и длина текущего пути
//возвращается длина найденного пути
int SearchPath(int node, int edgesPathCnt)
{
	int	idxNode = node-1;		//индекс узла в массиве узлов графа list

	//цикл по всем соседям текущего узла
	for(list[idxNode].idx = 0; list[idxNode].idx<list[idxNode].count; list[idxNode].idx++)
	{
		//есть ли ребро от текущего узла до соседа в текущем пути
		if (CmpEdge(node, list[idxNode].node[list[idxNode].idx], edgesPathCnt))
			continue;		//есть - смотрим следующего соседа
		
		//нет - добавим ребро в текущий путь
		//в поле "а" текущий узел
		edgesPath[edgesPathCnt].a = node;
		//одновременно увеличиваем длину найденного пути
		edgesPath[edgesPathCnt++].b = list[idxNode].node[list[idxNode].idx];

		//если найден еще не весь путь 
		if (edgesPathCnt != edgesFullCnt)
			//продолжаем искать путь с соседа
			edgesPathCnt = SearchPath(list[idxNode].node[list[idxNode].idx], edgesPathCnt);

		//если полный путь найден, то выходим, возвращая длину найденного пути
		if (edgesPathCnt == edgesFullCnt)
			return edgesPathCnt;
		//иначе исследуем следующего соседа
	}
	return edgesPathCnt-1;	//прошли всех соседей, полный путь не нашли,
					//вернем путь на 1 короче, т.е. исключим себя
					//чтобы предок продолжил поиск со следующего соседа
}

int main() 
{
	int			cnt = 0;			//количество узлов 
	int			i, j, k, First;
	int			edgesPathCnt;		//длина найденного пути

	FILE *		f = fopen("graph.txt", "r");
	
	if (f)
	{
		for(i=0; ; i++)
		{
			if (EOF == fscanf(f, "%d", &k))	//количество соседей узла
				break;				//читаем, пока читается
			//перевыделяем память под массив структур-узлов, каждый раз на 1 больше
			list = (ListNode*)realloc(list, (cnt+1)*sizeof(ListNode));
			list[cnt].count = k;	//сохраним количество соседей для узла
			//количество ребер равно половине сумме количеств соседей всех узлов
			edgesFullCnt += k;		//накопим эту сумму
			//выделяем память под массив соседей всех узлов
			list[cnt].node = (int*)malloc(k * sizeof(int));
			for(j = 0; j < k; j++)
				fscanf(f, "%d", &list[cnt].node[j]);	//считываем соседей
			cnt++;					//считаем узлы
		}
		edgesFullCnt /= 2;	//количество ребер
		
		//выделим память под искомый путь
		edgesPath = (EDGE*)malloc(edgesFullCnt*sizeof(EDGE));	//путь

		printf("Enter node number: "); 
		scanf("%d", &First);

		if ((First>0) && (First<=cnt))	//проверим на корректность начального номера
		{
			//ищем путь, параметры: номер первого узла и длину найденного пути = 0
			//получим длину найденного пути
			edgesPathCnt = SearchPath(First, 0);
			
			if(edgesPathCnt	== edgesFullCnt)	//нашли полный путь?
			{
				//выведем
				printf("Full path found: ");
				for(i=0; i<edgesPathCnt; i++)
					printf("%d ", edgesPath[i].a);	//в поле "а" последовательность проходимых узлов
				printf("%d\n", edgesPath[i-1].b);	//выведем поле "b" последнего узла, как последний узел
			}
			else
				printf("Full path not found!\n");
		}
		else
			printf("Node number error!\n");
	}
	else
		printf("File error!\n");
	
	//освободим память
	if (list)
	{
		for(i=0; i<cnt; i++)
			free(list[i].node);
		free(list);
	}
	if(edgesPath)
		free(edgesPath);

	return 0;
}

Список смежности
3 2 4 5
3 1 4 5
2 4 5
4 1 2 3 5
4 1 2 3 4

Консультировал: Лысков Игорь Витальевич (Старший модератор)
Дата отправки: 31.05.2017, 17:52

5
Игорь Витальевич, спасибо за помощь! Профессионально, быстро, плюс ясные комментарии!
-----
Дата оценки: 01.06.2017, 19:34

Рейтинг ответа:

НЕ одобряю +1 одобряю!


Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!


В избранное