Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<vector>
- #include <fstream>
- #define NODE 10
- using namespace std;
- ofstream fout;
- ifstream fin;
- int graph[NODE][NODE] = {
- {0, 1, 1, 1, 0, 0, 0, 0, 1, 0},
- {1, 0, 1, 0, 0, 0, 0, 0, 0, 0},
- {1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
- {1, 0, 0, 0, 1, 0, 0, 0, 0, 0},
- {0, 0, 0, 1, 0, 1, 0, 1, 0, 1},
- {0, 0, 0, 0, 1, 0, 1, 0, 0, 0},
- {0, 0, 0, 0, 0, 1, 0, 1, 0, 0},
- {0, 0, 0, 0, 1, 0, 1, 0, 0, 0},
- {1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
- {0, 0, 0, 0, 1, 0, 0, 0, 0, 0}
- };
- int tempGraph[NODE][NODE];
- int findStartVert() {
- for (int i = 0; i < NODE; i++) {
- int deg = 0;
- for (int j = 0; j < NODE; j++) {
- if (tempGraph[i][j])
- deg++; //степень увеличивается, когда обнаружен соединенный граф
- }
- if (deg % 2 != 0) //когда степень вершин нечетна
- return i; //i - узел с нечетной степенью
- }
- return 0; //когда все вершины имеют четную степень, начинайте с 0
- }
- bool isBridge(int u, int v) {
- int deg = 0;
- for (int i = 0; i < NODE; i++)
- if (tempGraph[v][i])
- deg++;
- if (deg > 1) {
- return false; //край не образует перемычки
- }
- return true; //кромка, образующая перемычку
- }
- int edgeCount() {
- int count = 0;
- for (int i = 0; i < NODE; i++)
- for (int j = i; j < NODE; j++)
- if (tempGraph[i][j])
- count++;
- return count; //подсчитываем количество ребер в графе
- }
- void fleuryAlgorithm(int start) {
- static int edge = edgeCount();
- for (int v = 0; v < NODE; v++) {
- if (tempGraph[start][v]) { //когда (u, v) ребро присутствует и не образует перемычку
- if (edge <= 1 || !isBridge(start, v)) {
- fout << start << "--" << v << " ";
- cout << start << "--" << v << " ";
- tempGraph[start][v] = tempGraph[v][start] = 0; //удаляем ребро из графика
- edge--; //уменьшаем ребро
- fleuryAlgorithm(v);
- }
- }
- }
- }
- int main() {
- fout.open("output.txt");
- for (int i = 0; i < NODE; i++) //копируем основной график во временный график
- for (int j = 0; j < NODE; j++)
- tempGraph[i][j] = graph[i][j];
- cout << "Cep` Eylera: ";
- fleuryAlgorithm(findStartVert());
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement