[Такая себе задача №1] Удали вершину и сделай из графа дерево.

На заре третьего курса приспичило мне решить задачу, которую дают курсу первому. Звучала они именно так, как описано в заголовке, но с небольшой правкой — удалить нужно одну вершину.

Как задаётся дерево, как задаётся граф, как всё это выводится — не сказано.

Цель заметки —  бери код, что я написал, если тебе нужно решить данную задачу. Я вот его в сети не нашёл, и пришлось писать. А так, может, кому-то и поможет. Пока гуглил, пришёл к выводу, что во многих университетах это задание есть на курсовую работу.

Интро.

Определение дерева я помню хорошо, с ним связана одна весёлая история на далёком экзамене по дискретной математике. Так что раздумывая, как решить задачу, я отчего-то решил сразу решать это дело без рекурсии. Ну вот так вот, почему бы и нет.

Так же решено было использовать списки смежности, а не матрицы смежности, т.к. преподавателя я помнил хорошо, и за матрицы он мог скинуть приличное количество баллов, приговорив «путь в бесконечную память вы открыли, студент».

Структура у меня выглядит следующим образом:

struct list {
	int numberOfVertex; /*номер текущей вершины*/
	list * nextTop;
	list * prev;
	list * nextAjacent;
	int status = 0;
};

 

За пару часов под пару кружек кофе и четверть плейлиста я вспомнил и прошёл заново все шишки работы с динамической памятью в контексте данной задачи, и набросал (с костылями, но рабочее) класс (классы ребятам использовать ещё нельзя) функции, реализующие вставку, удаление и прочие элементарные функции для работы со списком смежности.

Почему так долго? Потому что большее время я продумывал, как это всё будет решаться без рекурсии, приходил к выводу, что двунаправленный список лучше, чем однонаправленный, потом наоборот и думал, как я это буду делать без рекурсии.

Придя к выводу, что к чёрту всё — буду рекурсивно перебирать граф, удалять вершину, проверять — дерево(?), и исходя из ответа: если да — то задача выполнена, если нет — то ставим вершину на место и идём дальше. Это, конечно, затратно, но писать это без рекурсии у меня не было желания.

Как проверять, дерево ли граф на текущий момент? А легко и просто — есть теорема, которая утверждает, что граф является деревом, если он связен и количество вершин в нём на одну больше, чем количество ребер.

Исходя из этого были написаны небольшие функции: первая считала количество вершин, вторая считала количество ребер. А к слову, что такое ребро, а вернее как его обнаружить, если мы используем список смежности?

Легко и просто: нам нужны 3 цикла. Первый берёт, допустим, список смежности первой вершины. Зафиксировали вершину, нашли её список смежности и взяли первый элемент там. Далее нашли список смежности этого элемента и перебираем его до тех пор, пока не найдём там вершину, совпадающую с самой первой зафиксированной вершиной. Если совпадение есть — мы нашли ребро. И так перебираем циклично все вершины.

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

 

Входные данные задаются следующим образом:

  1. Во-первых, в файле и по-парно —  «основная вершина и вершина смежная ей»: 0 1 или 1 2. В этом случае 0 будет основной, а 1 — смежной. Или же 1 — основная, а 2 — смежная.
  2. Во-вторых, основные вершины задаются отдельно. Чтобы задать основную вершину, нужно ввести данные вида 0 -1. «-1» означает, что смежной вершины нет и нужно записать только 0.

К слову, алгоритм на этом и заканчивается. Код прикладываю ниже.

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>



/*====================================Секция структур данных====================================*/
/*список смежности*/
struct list {
	int numberOfVertex; /*номер текущей вершины*/
	list * nextTop;
	list * prev;
	list * nextAjacent;
	int status = 0;
};

/*список "цветов"*/
struct color {
	int numberOfVertex;
	int status;
	color * next;
};
/*====================================Секция структур данных====================================*/



/*====================================Прототипы функций====================================*/
int insertTopVertex(int top, int numberOfVertex, list ** myList);
/*====================================Прототипы функций====================================*/



/*====================================Секция функций, осуществляющих ввод-ввывод====================================*/
/*ввод графа из файла*/
list * inputGraphDataFromFile(char * filename) {

	list * tempList = new list;
	tempList = NULL;

	int bufferTopNode = 0, bufferAjacentNode = 0;
	FILE * file = fopen("dataGraph.txt", "r");
	if (file == NULL) {
		printf("Ошибка чтения файла!\n");
		return NULL;
	}
	else {
		printf_s("%s\n", "Данные, считанные из файла:");
		while (fscanf_s(file, "%d %d", &bufferTopNode, &bufferAjacentNode) != EOF) {
			insertTopVertex(bufferTopNode, bufferAjacentNode, &tempList);
			printf_s("%i %i\n", bufferTopNode, bufferAjacentNode);
		}
		return tempList;
	}

}
/*====================================Секция функций, осуществляющих ввод-ввывод====================================*/



/*====================================Секция основных функций списка смежности и списка "цветов"====================================*/
/*вставка вершин*/
int insertTopVertex(int top, int numberOfVertex, list ** myList) {
	if (numberOfVertex == -1) {
		if ((*myList) == NULL) { /*если список пустой, т.е. мы добавляем вершину в список первый раз*/
			(*myList) = new list;
			(*myList)->nextTop = NULL;
			(*myList)->prev = NULL;
			(*myList)->nextAjacent = NULL;
			(*myList)->numberOfVertex = top; /*добавили первую вершину в список*/
			return 0;
		}
		else {
			list * buffer = new list;
			list * temp = new list;
			buffer = (*myList);
			/*ищем свободное место под вершину*/
			while (buffer != NULL) {
				temp = buffer;
				buffer = buffer->nextTop;
			}
			if (temp->nextTop == NULL) { /*нашли конец списка*/

				list * newPoint = new list;
				newPoint->numberOfVertex = top;
				newPoint->nextTop = NULL;
				newPoint->prev = temp;
				newPoint->nextAjacent = NULL;

				temp->nextTop = new list;
				temp->nextTop = newPoint;
				return 0;
			}
			return 1;
		}
	}
	else { /*если добавляем смежную вершину*/
		list * buffer = new list;
		buffer = (*myList);
		/*ищем место под вершину*/
		while (buffer != NULL) {
			if (buffer->numberOfVertex == top) /*нашли список, в который надо вставлять*/
				if (buffer->nextAjacent == NULL) { /*если первое вхождение, т.е. у нас есть только top вершина*/
					list * tempAjacent = new list;
					tempAjacent->numberOfVertex = numberOfVertex;
					tempAjacent->nextAjacent = NULL;
					tempAjacent->nextTop = NULL;
					tempAjacent->prev = NULL;
					buffer->nextAjacent = tempAjacent;
					return 0;
				}
				else { /*если список смежности уже содержит вершины*/
					list * bufferAjacent = new list;
					list * tempDataAjacent = new list;
					bufferAjacent = buffer;
					while (bufferAjacent != NULL) {
						tempDataAjacent = bufferAjacent;
						bufferAjacent = bufferAjacent->nextAjacent;
					}
					if (tempDataAjacent->nextAjacent == NULL) { /*пришли в конец списка смежных вершин*/
						list * newNode = new list;
						newNode->numberOfVertex = numberOfVertex;
						newNode->nextAjacent = NULL;
						newNode->nextTop = NULL;
						newNode->prev = tempDataAjacent;
						tempDataAjacent->nextAjacent = newNode;
						return 0;
					}
				}
				buffer = buffer->nextTop;
		}
	}
	return 1;
}
/*удаление вершин*/
list * removeNode(int numberOfVertex, list ** myList) {
	list * buffer = new list;
	buffer = (*myList);

	while (buffer != NULL) {

		list * ajCur = new list;
		ajCur = buffer->nextAjacent;

		while (ajCur != NULL) { /*пробегаемся по списку смежности, ищем совпадения на эту вершину, и ежели нашли - бахаем удаление*/
			if (ajCur->numberOfVertex == numberOfVertex) {
				
				list * temp = new list;
				temp = ajCur;

				if (ajCur->prev == NULL) { /*первый*/
					ajCur = ajCur->nextAjacent;
					if (ajCur != NULL) ajCur->prev = NULL; /*бага инициализации*/
					buffer->nextAjacent = ajCur;
					delete temp;
				}
				else
					if (ajCur->nextAjacent == NULL) { /*последний*/
						ajCur->prev->nextAjacent = NULL;
						ajCur = ajCur->prev;
						delete temp;
					}
					else { /*в середине*/
						ajCur->prev->nextAjacent = ajCur->nextAjacent;
						ajCur->nextAjacent->prev = ajCur->prev;
						ajCur = ajCur->nextAjacent;
						delete temp;
					}
			}
			if (ajCur != NULL) ajCur = ajCur->nextAjacent;
		}	
		buffer = buffer->nextTop;
	}

	/*удаляем сам список смежности*/
	buffer = (*myList);
	while (buffer != NULL) {
		if (buffer->numberOfVertex == numberOfVertex) { /*теперь удаляем сам список смежности*/

			list * temp = new list;
			temp = buffer;

			if (buffer->prev == NULL) { /*первый*/
				buffer = buffer->nextTop;
				if (buffer != NULL) buffer->prev = NULL;
				delete temp;
				(*myList) = buffer;
			}
			else
				if (buffer->nextTop == NULL) { /*последний*/
					buffer->prev->nextTop = NULL;
					buffer = buffer->prev;
					delete temp;
					(*myList) = buffer;
									}
				else { /*в середине*/
					buffer->prev->nextTop = buffer->nextTop;
					buffer->nextTop->prev = buffer->prev;
					buffer = buffer->nextTop;
					delete temp;
					(*myList) = buffer;
				}
		}
		buffer = buffer->nextTop;
	}
	return (*myList);
}
/*удаление элемента из списка "цветов"*/
int removeNodeColorList(int numberOfVertex, color ** colorList) {
	color * temp = new color;
	temp = (*colorList);
	int status;

	int count = 0;
	while (temp != NULL) {
		if (temp->numberOfVertex == numberOfVertex) {
			status = temp->status;
			if (count == 1) {
				/*первый элемент*/
				color * deleteBuffer = new color;
				deleteBuffer = temp;
				(*colorList)->next = (*colorList)->next->next;
				delete(deleteBuffer);
				return status;
			}
		}
		count++;
		temp = temp->next;
	}
	return 0;
}
/*добавление элемента в список "цветов"*/
void addNodeColorList(int nubmerOfVertex, color ** colorList, int status) {
	color * temp = new color;
	temp->next = NULL;
	temp->numberOfVertex = nubmerOfVertex;
	temp->status = status;
	
	color * buf = new color;
	buf = (*colorList);
	while (buf->next != NULL) {
		buf = buf->next;
	}

	buf->next = temp;
}
/*инициализация списка "цветов"*/
int initColor(list ** myList ,color ** colorList) {
	(*colorList) = new color;
	(*colorList)->next = NULL;

	list * tempList = new list;
	tempList = (*myList);

	color * tempColor = new color;
	tempColor = (*colorList);

	while (tempList != NULL) {
		color * temp = new color;
		temp->numberOfVertex = tempList->numberOfVertex;
		temp->status = 0;
		temp->next = NULL;
		while (tempColor->next != NULL) 
			tempColor = tempColor->next;
		tempColor->next = temp;
		tempList = tempList->nextTop;
	}
	return 0;
}
/*====================================Секция основных функций списка смежности и списка "цветов"====================================*/



/*====================================Секция функций, осуществляющих работу с графом====================================*/
/*Проверка на связность*/
short int CheckConnectivityForVertexOfGraph(int currentVertex, list ** myList, color ** colors) {
	/*ищем текущую вершину*/
	list * temp;
	temp = new list;
	temp = (*myList);
	while (temp->numberOfVertex != currentVertex) 
		temp = temp->nextTop;

	if (temp->numberOfVertex == currentVertex) {
		/*вершина найдена*/
		color * tempColor = new color;
		tempColor = (*colors);
		while (tempColor->numberOfVertex != currentVertex)
			tempColor = tempColor->next;
		if (tempColor->status == 1)
			return 1;
		else {
			tempColor->status = 1;

			list * tempAjacent = new list;
			tempAjacent = temp->nextAjacent;

			while (tempAjacent != NULL) {
				/*поиск вершины из списка смежности в списке color*/
				CheckConnectivityForVertexOfGraph(tempAjacent->numberOfVertex, myList, colors);
				tempAjacent = tempAjacent->nextAjacent;
			}
		}
	}
	else {
		return 1;
	}
	return 0;
}
/*считаем количество рёбер*/
int countingEdges(list ** myList) {
	int countEdges = 0;

	/*считаем рёбра*/
	list * tempList = new list;
	tempList = (*myList);
	while (tempList) {

		list * tempAjList = new list;
		tempAjList = tempList->nextAjacent;

		while (tempAjList) {
			/*находим список смежности элемента tempAjList*/
			list * buffer = new list;
			buffer = (*myList);
			while (buffer->numberOfVertex != tempAjList->numberOfVertex)
				buffer = buffer->nextTop;

			if (buffer->numberOfVertex == tempAjList->numberOfVertex) {
				list * buffer2 = new list;
				buffer2 = buffer->nextAjacent;
				while (buffer2 != NULL) {
					if (buffer2->numberOfVertex == tempList->numberOfVertex) {
						/*ребро найдено*/
						countEdges++;
						break;
					}
					buffer2 = buffer2->nextAjacent;
				}
			}

			tempAjList = tempAjList->nextAjacent;
		}
		tempList = tempList->nextTop;
	}
	countEdges /= 2;
	return countEdges;
}
/*считаем количество вершин*/
int countingElements(list ** myList) {
	int countVertex = 0;
	list * temp = new list;
	temp = (*myList);
	while (temp != NULL) {
		countVertex++;
		temp = temp->nextTop;
	}
	return countVertex;
}
/*проверка на дерево*/
int checkTree(list ** myList, color ** colorList) {
	
	int checkFlag = 0;

	if (countingEdges(myList) != countingElements(myList) - 1) {
		return 1;
	}
	else {
		CheckConnectivityForVertexOfGraph((*myList)->numberOfVertex, myList, colorList);

		color * tempList = new color;
		tempList = (*colorList);
		
		while (tempList != NULL) {
			if (tempList->status == 0) {
				return 1;
			}
			tempList = tempList->next;
		}
	}
	return 0;
}
/*возвращает все вершины, к которым смежна переданная*/
list * returnAllAjacentVertex(int currentVertex, list ** myList) {

	list * returnList = new list;
	returnList = NULL;

	list * tempList = new list;
	tempList = (*myList);
	while (tempList!=NULL) {
		if (tempList->numberOfVertex == currentVertex) {
			tempList = tempList->nextTop;
			continue;
		}
		/*перебираем списки смежности*/
		list * tempAjacentList = new list;
		tempAjacentList = tempList->nextAjacent;
		while (tempAjacentList != NULL) {
			if (tempAjacentList->numberOfVertex == currentVertex) {
				list * temp = new list;
				temp->numberOfVertex = tempList->numberOfVertex;
				temp->nextTop = NULL;
				if (returnList == NULL) {
					returnList = temp;
					break;
				}
				else {
					list * temp2 = new list;
					temp2 = returnList;
					while (temp2->nextTop != NULL) {
						temp2 = temp2->nextTop;
					}
					temp2->nextTop = temp;
					break;
					
				}
			}
			tempAjacentList = tempAjacentList->nextAjacent;
		}

		tempList = tempList->nextTop;
	}
	return returnList;
}
/*====================================Секция функций, осуществляющих работу с графом====================================*/



/*основной цикл программы*/
int mainLoop(list ** myList) {

	color * colorList;
	initColor(myList, &colorList);

	list * mainList = new list;
	mainList = (*myList);

	while (mainList != NULL) {

		/*проверка, если мы прошли уже все вершины и граф при этом не связный*/
		list * coherentOrNot = new list;
		coherentOrNot = mainList;

		int statusCount = 0;
		while (coherentOrNot != NULL) {
			if (coherentOrNot->status == 1)
				statusCount += 1;
			coherentOrNot = coherentOrNot->nextTop;
		}

		if (statusCount == countingElements(&mainList)) {
			printf_s("%s\n", "Вершины, которую можно удалить - нет.");
			break;
		}

		if (mainList->status != 1) {
			/*удаляем в буффер вершину
			проверяем
			если граф стал деревом - задача выполнена.
			иначе - возвращаем вершину на место, и продолжаем
			если мы перебрали все вершины и граф не дерево - задачу решить нельзя
			*/

			list * saverList = new list; /*список для сохранения удаляемой вершины*/
			saverList = NULL;

			list * tempList = new list;
			tempList = mainList;

			while (tempList != NULL) {

				list * temp = new list;
				temp->numberOfVertex = tempList->numberOfVertex;
				temp->nextTop = tempList->nextTop;
				temp->nextAjacent = NULL;
				temp->prev = tempList->prev;

				if (saverList == NULL)
					saverList = temp;
				else {
					list * bufferSaverList = new list;
					bufferSaverList = saverList;
					while (bufferSaverList->nextAjacent != NULL)
						bufferSaverList = bufferSaverList->nextAjacent;
					bufferSaverList->nextAjacent = temp;
				}
				tempList = tempList->nextAjacent;
			}

			int deleteVertex = mainList->numberOfVertex;
			list * ajacentAllVertex = returnAllAjacentVertex(deleteVertex, myList);
			list * nextNode = removeNode(deleteVertex, myList);
			int deleteColorNodeStatus = removeNodeColorList(deleteVertex, &colorList);

			/*проверяем:*/
			if (checkTree(myList, &colorList) == 0) {
				printf_s("%s\n", "Задача выполнена!");
				printf_s("%s%d\n", "Номер вершины, которую удалили: ", saverList->numberOfVertex);
				_getch();
				return 0;
			}
			else {
				insertTopVertex(saverList->numberOfVertex, -1, myList);

				list * buffer = new list;
				buffer = saverList->nextAjacent;
				while (buffer != NULL) {
					insertTopVertex(saverList->numberOfVertex, buffer->numberOfVertex, myList);
					if (buffer->nextAjacent != NULL)
						buffer = buffer->nextAjacent;
					else break;
				}
				/*меняем статус вершины*/
				list *newList = new list;
				newList = (*myList);
				while (newList->numberOfVertex != saverList->numberOfVertex)
					newList = newList->nextTop;
				if (newList->numberOfVertex == saverList->numberOfVertex)
					newList->status = 1; /*вершину в выбор удаляемых больше не брать*/

				/*вставляем вершину назад в colorList*/
				addNodeColorList(saverList->numberOfVertex, &colorList, deleteColorNodeStatus);

				/*вставляем вершину во все списки смежности, где она была*/
				list * tempList = new list;
				tempList = ajacentAllVertex;
				while (tempList != NULL) {

					list * tempMainList = new list;
					tempMainList = (*myList);

					while (tempMainList->numberOfVertex != tempList->numberOfVertex)
						tempMainList = tempMainList->nextTop;

					if (tempMainList->numberOfVertex == tempList->numberOfVertex) {
						list * tempMainListAj = new list;
						tempMainListAj = tempMainList;

						while (tempMainListAj->nextAjacent != NULL)
							tempMainListAj = tempMainListAj->nextAjacent;
						if (tempMainListAj->nextAjacent == NULL) {
							list * newListAj = new list;
							newListAj->numberOfVertex = deleteVertex;
							newListAj->nextAjacent = NULL;
							tempMainListAj->nextAjacent = newListAj;
						}
					}
					tempList = tempList->nextTop;
				}
			}

			mainList = nextNode;
		}
		else continue;
	}
	/*если дошли до этого момента, значит такой вершины нет*/
	printf_s("%s\n", "Задача не имеет решений.");
	_getch();
	return 1;
}

Соответственно, main.cpp выглядит следующим образом:

#include <locale.h>
#include "graph.h"


int main() {
	setlocale(LC_ALL, "Russian");

	list * tempList = new list;
	tempList = NULL;

	/*читаем данные из файла:*/
	tempList = inputGraphDataFromFile("dataGraph.txt");
	/*основной цикл программы:*/
	mainLoop(&tempList);

	_getch();
	return 0;
}

Если кому-то помог — я рад 🙂

 

 

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *