На заре третьего курса приспичило мне решить задачу, которую дают курсу первому. Звучала они именно так, как описано в заголовке, но с небольшой правкой — удалить нужно одну вершину.
Как задаётся дерево, как задаётся граф, как всё это выводится — не сказано.
Цель заметки — бери код, что я написал, если тебе нужно решить данную задачу. Я вот его в сети не нашёл, и пришлось писать. А так, может, кому-то и поможет. Пока гуглил, пришёл к выводу, что во многих университетах это задание есть на курсовую работу.
Интро.
Определение дерева я помню хорошо, с ним связана одна весёлая история на далёком экзамене по дискретной математике. Так что раздумывая, как решить задачу, я отчего-то решил сразу решать это дело без рекурсии. Ну вот так вот, почему бы и нет.
Так же решено было использовать списки смежности, а не матрицы смежности, т.к. преподавателя я помнил хорошо, и за матрицы он мог скинуть приличное количество баллов, приговорив «путь в бесконечную память вы открыли, студент».
Структура у меня выглядит следующим образом:
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; }
Если кому-то помог — я рад 🙂