На заре третьего курса приспичило мне решить задачу, которую дают курсу первому. Звучала они именно так, как описано в заголовке, но с небольшой правкой — удалить нужно одну вершину.
Как задаётся дерево, как задаётся граф, как всё это выводится — не сказано.
Цель заметки — бери код, что я написал, если тебе нужно решить данную задачу. Я вот его в сети не нашёл, и пришлось писать. А так, может, кому-то и поможет. Пока гуглил, пришёл к выводу, что во многих университетах это задание есть на курсовую работу.
Интро.
Определение дерева я помню хорошо, с ним связана одна весёлая история на далёком экзамене по дискретной математике. Так что раздумывая, как решить задачу, я отчего-то решил сразу решать это дело без рекурсии. Ну вот так вот, почему бы и нет.
Так же решено было использовать списки смежности, а не матрицы смежности, т.к. преподавателя я помнил хорошо, и за матрицы он мог скинуть приличное количество баллов, приговорив «путь в бесконечную память вы открыли, студент».
Структура у меня выглядит следующим образом:
struct list {
int numberOfVertex; /*номер текущей вершины*/
list * nextTop;
list * prev;
list * nextAjacent;
int status = 0;
};
За пару часов под пару кружек кофе и четверть плейлиста я вспомнил и прошёл заново все шишки работы с динамической памятью в контексте данной задачи, и набросал (с костылями, но рабочее) класс (классы ребятам использовать ещё нельзя) функции, реализующие вставку, удаление и прочие элементарные функции для работы со списком смежности.
Почему так долго? Потому что большее время я продумывал, как это всё будет решаться без рекурсии, приходил к выводу, что двунаправленный список лучше, чем однонаправленный, потом наоборот и думал, как я это буду делать без рекурсии.
Придя к выводу, что к чёрту всё — буду рекурсивно перебирать граф, удалять вершину, проверять — дерево(?), и исходя из ответа: если да — то задача выполнена, если нет — то ставим вершину на место и идём дальше. Это, конечно, затратно, но писать это без рекурсии у меня не было желания.
Как проверять, дерево ли граф на текущий момент? А легко и просто — есть теорема, которая утверждает, что граф является деревом, если он связен и количество вершин в нём на одну больше, чем количество ребер.
Исходя из этого были написаны небольшие функции: первая считала количество вершин, вторая считала количество ребер. А к слову, что такое ребро, а вернее как его обнаружить, если мы используем список смежности?
Легко и просто: нам нужны 3 цикла. Первый берёт, допустим, список смежности первой вершины. Зафиксировали вершину, нашли её список смежности и взяли первый элемент там. Далее нашли список смежности этого элемента и перебираем его до тех пор, пока не найдём там вершину, совпадающую с самой первой зафиксированной вершиной. Если совпадение есть — мы нашли ребро. И так перебираем циклично все вершины.
Вообще, по-сложности, алгоритм очень затратен. Где-то есть моменты, которые можно назвать костылями, оправдаюсь тем, что давным-давно не работал с динамической памятью.
Входные данные задаются следующим образом:
- Во-первых, в файле и по-парно — «основная вершина и вершина смежная ей»: 0 1 или 1 2. В этом случае 0 будет основной, а 1 — смежной. Или же 1 — основная, а 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;
}
Если кому-то помог — я рад 🙂
