Исходник поиска фундаментальных графов
Код на C++ #include <conio.h> #include <stdio.h> #include <iostream.h> #include <stdlib.h> #define SIZE1 8 #define SIZE2 5 #define FILENAME "result.txt" FILE *out; int index, // индекс в стеке Stack[SIZE1], // Стек Number, // Количество выводимых строк WGN[SIZE1], // массив закраски Record[SIZE1][SIZE2] = {{1, 3, 6, -1, -1}, // Граф, заданный списком {0, 3, 4, 6, -1}, // инцендентности {5, 7, -1, -1, -1}, {0, 1, 6, -1, -1}, {1, 6, 7, -1, -1}, {2, 7, -1, -1, -1}, {0, 1, 3, 4, -1}, {2, 4, 5, -1, -1}}, Styag[7][2] = {{0, 1}, // Ребра стягивающего дерева {1, 3}, {1, 4}, {4, 6}, {4, 7}, {7, 2}, {2, 5}}; //Функция поиска фундаментальнх графов void Search(int v) { int u, // содержит значение u flag; // Флаг отсеивания лишнего Stack[index] = v; // Помещаем в стек значение WGN[v] = 1; // закрашиваем вершину index++; // увеличиваем индекс стека // проходим по всем вершинам связанным с вершиной v for(int i = 0; i < SIZE2 && Record[v][i] != -1; i++) { u = Record[v][i]; // получаем вершину u из строки if (WGN[u] == -1) // Если вершина не использовалась Search(u); // переходим на строку u в списке инцендентности else { // 1-е: в цикле минимум 3 вершины должно быть // 2-е: новый элемент должен быть началом цикла // тогда цикл найден if ((index - 3 >= 0) && (u == Stack[0])) { flag = 0; for(int c = 1; c < index; c++) for(int w = 0; w < 7; w++) if((Stack[c-1] == Styag[w][0] && Stack[c] == Styag[w][1]) || (Stack[c] == Styag[w][0] && Stack[c-1] == Styag[w][1])) flag++; for(int w = 0; w < 7; w++) if((Stack[0] == Styag[w][0] && Stack[index-1] == Styag[w][1]) || (Stack[index-1] == Styag[w][0] && Stack[0] == Styag[w][1])) flag++; if(index - 1 != flag) break; // выводим содержимое стека fprintf(out, "Ребро: "); cout<<endl<<"Ребро: "; for(int j = 0; j < index; j++) { cout<<Stack[j]<<" "; fprintf(out, "%i ", Stack[j]); } fprintf(out, "\n"); Number++; if(Number == 22) { cout<<endl<<endl<<"Нажмите кнопку для продолжения."; getch(); Number = 0; clrscr(); } // отсечение не фундаментальных циклов break; } } } index--; // очищение стека путем уменьшения индекса WGN[v] = -1; // высвобождение вершины от краски } void main(void) { int i, j; clrscr(); out = fopen(FILENAME, "wt"); // инициализация и обнуление данных for(i = 0; i < SIZE1; i++) { index = 0; Stack[i] = WGN[i] = -1; } Number = 0; // начало поиска for(i = 0; i < SIZE1; i++) if (WGN[i] == -1) Search(i); getch(); fclose(out); }
|