24.11.2017, 17:59 [+3 UTC]
в нашей команде: 2 287 чел. | участники онлайн: 12 (рекорд: 21)

:: РЕГИСТРАЦИЯ

:: консультации

:: задать вопрос

:: все разделы

:: правила

:: новости

:: участники

:: доска почёта

:: форум

:: блоги

:: поиск

:: статистика

:: наш журнал

:: наши встречи

:: наша галерея

:: отзывы о нас

:: поддержка

:: руководство

Версия системы:
7.41 (25.02.2017)

Общие новости:
23.02.2017, 09:51

Форум:
24.11.2017, 15:19

Последний вопрос:
24.11.2017, 17:25

Последний ответ:
24.11.2017, 08:36

Последняя рассылка:
24.11.2017, 12:15

Писем в очереди:
0

Мы в соцсетях:

Наша кнопка:

RFpro.ru - здесь вам помогут!

Отзывы о нас:
02.12.2009, 05:46 »
Brutuss
Спасибо за подробный ответ! [вопрос № 174730, ответ № 257162]
21.05.2016, 04:12 »
Usagisan
Раз за разом выручаете! Большое спасибо! [вопрос № 189450, ответ № 273851]

РАЗДЕЛ • С / С++

Создание программ на языках C и C++.

[администратор рассылки: Андрей Кузнецов aka Dr_Andrew (Старший модератор)]

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

Коцюрбенко Алексей aka Жерар
Статус: Мастер-Эксперт
Рейтинг: 320
Лысков Игорь Витальевич
Статус: Старший модератор
Рейтинг: 151
CradleA
Статус: Профессионал
Рейтинг: 80

Перейти к консультации №:
 

Консультация онлайн # 191080
Раздел: • С / С++
Автор вопроса: pNod (1-й класс)
Отправлена: 30.05.2017, 19:53
Поступило ответов: 1

Здравствуйте! Прошу помощи в следующем вопросе:
задача найти и вывести Эйлеров путь. Граф неориентированный. Задан списками смежности в текстовом файле. Начальную вершину для обхода задать с клавиатуры. На Си или С++.
Додумалась до отдельных (к сожалению, не самых важных) фрагментов, не могу их связать и дополнить до рабочего состояния:
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) запросить вершину тоже понятно как:
int firstNode;
printf("Введите номер вершины с нечетной степенью, с которой будет начат обход:\n");
scahf("%d", &First);
6)...до поиска Эйлерова пути даже не дошла.
Простите, если сумбурно))
Пожалуйста, помогите заполнить пробелы и объединить все в программу!

Состояние: Консультация закрыта

Ответ # 275050 от Лысков Игорь Витальевич (Старший модератор)

Здравствуйте, 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

[подробно]

Сообщение
модераторам

Отправлять сообщения
модераторам могут
только участники портала.
ВОЙТИ НА ПОРТАЛ »
регистрация »

Мини-форум консультации № 191080

Лысков Игорь Витальевич
Старший модератор

ID: 7438

# 1

= общий = | 31.05.2017, 19:42 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
pNod:

Прошу прощения, работает неправильно.
Завтра исправлю... smile

=====
Каждый выбирает по себе -
Щит и латы, посох и заплаты.
Меру окончательной расплаты
Каждый выбирает для себя.

pNod
1-й класс

ID: 401172

# 2

= общий = | 31.05.2017, 20:06 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

Игорь Витальевич, спасибо за ответ! smile
Получается граф как открытый конверт почтовый, да?
Если начинаю обход с вершины №3 получается следующий путь: 3 4 1 2 5
Проблема в том, что для Эйлерова пути надо пройти все ребра ровно по одному разу smile ...
При обходе 3 4 1 2 5 остаются не пройденными три ребра и их не пройти так, чтобы не пройти повторно по уже указанным.
Насколько я поняла, если в графе больше двух вершин с нечетной степенью, то в нем Эйлерова пути уже не будет.
Получается, что вершины повторно посещать можно, а ребра нет. smile

pNod
1-й класс

ID: 401172

# 3

= общий = | 31.05.2017, 20:07 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

Хорошо, только сейчас новое сообщение увидела! smile

Лысков Игорь Витальевич
Старший модератор

ID: 7438

# 4

 +1 
 
= общий = | 01.06.2017, 18:37 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
pNod:

Программа исправлена. smile

=====
Каждый выбирает по себе -
Щит и латы, посох и заплаты.
Меру окончательной расплаты
Каждый выбирает для себя.

pNod
1-й класс

ID: 401172

# 5

= общий = | 01.06.2017, 19:22 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

Спасибо!!! Все работает как надо!!! Вы - гений! smile
Я пока полностью код не поняла, но очень интересно и буду разбираться с каждой строчкой.
Игорь Витальевич, смогу я задать вопросы по коду, если возникнут?

Лысков Игорь Витальевич
Старший модератор

ID: 7438

# 6

= общий = | 01.06.2017, 19:30 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
pNod:

Разумеется... smile

=====
Каждый выбирает по себе -
Щит и латы, посох и заплаты.
Меру окончательной расплаты
Каждый выбирает для себя.

pNod
1-й класс

ID: 401172

# 7

= общий = | 02.06.2017, 20:23 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

Код изучила и поняла две вещи, во-первых, что указатели - это сила, во-вторых - сразу отвергнуть идею использования массивов было ошибкой.
Вопрос у меня скорее по синтаксису в следующем фрагменте, который начинается со строки 102:

if (f) //что это означает дословно? Если файл не пуст?
{
for(i=0; ; i++) //цикл для i, а i реально нет в теле цикла, для чего так делается?
{
if (EOF == fscanf(f, "%d", &k)) //'самое непонятное: если конец файла равен считывать из файла в адрес переменной K.
//Не понимаю почему в выражении признак окончания файла приравнивается к
// действию...


break; //это означает выйти из цикла когда будет конец файла?

Буду благодарна, если объясните эти моменты smile

Лысков Игорь Витальевич
Старший модератор

ID: 7438

# 8

 +1 
 
= общий = | 02.06.2017, 20:48 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
pNod:

© Цитата:
if (f) //что это означает дословно? Если файл не пуст?

Предыдущей строкой мы открываем файл
И если файл открылся, то величина (FILE*) f будет отлична от нуля.
Если не открылся, то будет равна нулю
Вот мы и проверяем f на 0
© Цитата:
for(i=0; ; i++) //цикл для i, а i реально нет в теле цикла, для чего так делается?

можно было написать и while(true)
Это один из вариантов задать бесконечный цикл. Выход по break
© Цитата:
if (EOF == fscanf(f, "%d", &k)) //'самое непонятное: если конец файла равен считывать из файла в адрес переменной K.
//Не понимаю почему в выражении признак окончания файла приравнивается к
// действию...
Величина EOF, равная -1 или 0xffffffff вернется в случае, когда файл будет весь прочитан
Таким образом мы контролируем конец файла. По которому и делаем выход из бесконечного цикла по break
Что и есть ответ на последний вопрос smile
© Цитата:
break; //это означает выйти из цикла когда будет конец файла?

=====
Каждый выбирает по себе -
Щит и латы, посох и заплаты.
Меру окончательной расплаты
Каждый выбирает для себя.

Лысков Игорь Витальевич
Старший модератор

ID: 7438

# 9

 +1 
 
= общий = | 02.06.2017, 20:58 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
pNod:

Об функциях fscanf и fwscanf

© Цитата: MSDN
Each of these functions returns the number of fields successfully converted and assigned; the return value does not include fields that were read but not assigned. A return value of 0 indicates that no fields were assigned. If an error occurs, or if the end of the file stream is reached before the first conversion, the return value is EOF for fscanf or WEOF for fwscanf.


Дословно smile
© Цитата:
Каждая из этих функций возвращает количество полей удачно конвертированных и присвоенных; возвращаемое значение не включает поля, которые прочитаны, но не присвоены. Возвращенное значение 0 показывает, что присвоенные поля отсутствуют. Если случилась ошибка или случился конец потока данных до первой конверсии, то возвращается значение EOF для fscanf или FEOF для fwscanf.

=====
Каждый выбирает по себе -
Щит и латы, посох и заплаты.
Меру окончательной расплаты
Каждый выбирает для себя.

• Отредактировал: Лысков Игорь Витальевич (Старший модератор)
• Дата редактирования: 02.06.2017, 20:59

Лысков Игорь Витальевич
Старший модератор

ID: 7438

# 10

 +1 
 
= общий = | 02.06.2017, 21:01 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
pNod:

При выполнении чтения по одному числу будет возвращаться число 1 (одно поле), при невозможности прочитать - EOF smile smile

=====
Каждый выбирает по себе -
Щит и латы, посох и заплаты.
Меру окончательной расплаты
Каждый выбирает для себя.

Лысков Игорь Витальевич
Старший модератор

ID: 7438

# 11

 +1 
 
= общий = | 02.06.2017, 21:06 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
pNod:

Будут вопросы, пишите, с удовольствием отвечу, только завтра smile

=====
Каждый выбирает по себе -
Щит и латы, посох и заплаты.
Меру окончательной расплаты
Каждый выбирает для себя.

pNod
1-й класс

ID: 401172

# 12

= общий = | 02.06.2017, 22:00 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

К сожалению, по этой теме вопросов больше нет smile
Однако, я только в начале изучения Си/С++, так что думаю появятся другие вопросы, и я знаю где мне окажут профессиональную помощь.
Спасибо за такие подробные ответы, узнала полезные возможности, буду использовать! smile

 

Возможность оставлять сообщения в мини-форумах консультаций доступна только после входа в систему.
Воспользуйтесь кнопкой входа вверху страницы, если Вы зарегистрированы или пройдите простую процедуру регистрации на Портале.

Яндекс Rambler's Top100

главная страница | поддержка | задать вопрос

Время генерирования страницы: 0.24455 сек.

© 2001-2017, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Калашников О.А.  |  Гладенюк А.Г.
Версия системы: 7.41 от 25.02.2017
Бесплатные консультации онлайн