Задача използваща алгоритъм на Дейкстра
Задача използваща Ойлеров цикъл
Изтегляне 73 Kb.
|
| Задача използваща Ойлеров цикъл
/*
------
Даден е неориентиран мултиграф G. Ойлеров цикъл наричаме цикъл, който обхожда всяко ребро точно по веднъж. Да се провери да ли G съдържа Ойлеров цикъл и ако да - да се намери.
----
брой върхове в графа брой ребра (неориентирани) начален връх списък на ребрата Изход -----
Последователност от номера на върхове описваща намерения Ойлеров цикъл. Решение -------
НДУ G да съдържа Ойлеров цикъл е всеки връх да е от четна степен. Избираме начален връх и обхождаме ребрата в дълбочина: - търсим необходено ребро от текущия връх - ако има - тръгваме по него, маркираме го за обходено - ако няма - текущия връх е началния и сме намерили цикъл. Възможно е обаче не всички ребра да са включени в този цикъл. Търсим връх от цикъла, от който да излизат необходени ребра, повтаряме горното обхождане и намираме друг цикъл, с който разширяваме предишния. Когато няма необходени ребра -> край.
------
1 3 / \ / \
0 2 4 \ / \ /
6 5 и нека началния връх е 0. Реброто (0 1) е необходено -> обхождаме го и новият текущ връх е 1. (1 2) е обходено -> обхождаме го и новият текущ връх е 2. (2 6) е обходено -> обхождаме го и новият текущ връх е 6. (6 0) е обходено -> обхождаме го и новият текущ връх е 0. Намерихме цикъл 0 1 2 6 0, но ребрата (2 3), (3 4), (4 5) и (5 2) не участват в него. Виждаме обаче, че от 2 излизат необходени ребра. Тръгвайки от 2 намираме цикъла 2 3 4 5 2. Нека да разширим с него предишния: 0 1 | 2 3 4 5 2 | 6 0 Този алгоритъм ще свърши работа, но ще трябва да съчетаваме цикли и това вдига порядъка на сложност на алгоритъма. Ще направим лека модификация, така че алгоритъма да остане линеен по броя на ребрата в графа. Нека в стъпка 3 от алгоритъма (когато няма необходени ребра излизащи от текущия връх) да не спираме обхождането в дълбочина, ами да се върнем на предходния връх и да продължим търсенето на необходени ребра. Текущият път в обхождането в дълбочина, на съответната стъпка би изглеждал така: 1) 0 2) 0 1
3) 0 1 2 4) 0 1 2 6 5) 0 1 2 6 0 6) 0 1 2 6 7) 0 1 2 8) 0 1 2 3 9) 0 1 2 3 4 10) 0 1 2 3 4 5 11) 0 1 2 3 4 5 2 12) 0 1 2 3 4 5 13) 0 1 2 3 4 14) 0 1 2 3 15) 0 1 2 16) 0 1
17) 0 И нека след като установим, че от даден връх няма необходени ребра да отпечатаме номера му. Печатаме: - 0, на стъпка 5 - 6, на стъпка 6 - 2, на стъпка 11 - 5, на стъпка 12 - 4, на стъпка 13 - 3, на стъпка 14 - 2, на стъпка 15 - 1, на стъпка 16 - 0, на стъпка 17 Получихме Ойлеров цикъл в дадения граф. Разширяването на намерените цикли стана реално на връщане от рекурсията и неявно използвахме стек.
------------------------ Ще използваме представяне на графа чрез списъци на съседите. Нека n - брой върхове в графа, m - брой ребра. Номерираме всеки връх с число от 0 до n - 1. За всяко ребро пазим номерата на върховете, които свързва и дали е посетено. За всеки връх пазим в списък номерата на съседните върхове и номерата на съответните ребра по които се достига до тях - списък от наредени двойки <съсед,ребро>. Тръгваме от началния връх и вървим в дълбочина по необходените ребра. На връщане от рекурсията строим ойлеровия цикъл.
маркираме реброто като обходено (изполваме номера на реброто като индекс в масива E). Друг вариант би бил да изтрием номера на текущия връх от списъка на съседите на другия, но това би отнело линейно O(m), а не константно O(1) време. Забележка --------- Входните данни четем от файла input.txt, който за разгледания по-горе пример изглежда така: 7 8 0 0 1
0 6 1 2
2 6 2 3
2 5 3 4
4 5 Забележка 2 ----------- На края на файла можете да намерите закоментирано решение използващо матрица на съседство (A[i][j] - брой на ребрата от i до j). В общия случай това решение би било O(n^2) заради търсенето на съседни върхове и като цяло е на порядък по-бавно от това използващо списъци на съседите. */ #include #include #include using namespace std; struct Edge { int begin, end; bool visited; };
> NeighList; int n, m, start; // За всяко ребро пазим начален и краен връх, и дали е посетено. Edge * E; // За всеки връх пазим списък от двойки от вида <съсед,ребро>. NeighList * neigh; void euler( int v ) { NeighList& neighbours = neigh[v]; // Търсим необходено ребро и тръгваме по него for ( int j = 0; j < neighbours.size(); j++ ) { pair int next_v = p.first; int edgeNum = p.second; if ( !E[ edgeNum ].visited ) { // Като маркираме в масива E реброто edgeNum, че е обходено, // при опит за минаване по същото ребро в другата посока, // от next_v към v ще видим, че реброто е обходено. E[ edgeNum ].visited = true; euler( next_v ); } }
} int main() { ifstream f( "input.txt" ); f >> n >> m >> start; neigh = new NeighList[n]; E = new Edge[m];
{ f >> E[ edgeNum ].begin >> E[edgeNum].end; E[ edgeNum ].visited = false; // Всяко ребро участва по веднъж в списъка на съседите на всеки от // двата си края. neigh[ E[ edgeNum ].begin ].push_back( pair neigh[ E[ edgeNum ].end ].push_back( pair }
for ( int i = 0; ( i < n ) && eulerGraph; i++ ) if ( ( neigh[i].size() % 2 ) != 0 ) eulerGraph = false; if ( !eulerGraph ) cout << "The given graph doesn't have an euler cycle.\n"; else {
euler( start ); cout << endl; }
delete[] E; return 0; }
#include #include #include int A[MAX_N][MAX_N]; void euler( int v ) { for ( int next_v = 0; next_v < n; ) { if ( A[v][next_v] > 0 ) { --A[v][next_v]; --A[next_v][v]; euler( next_v ); } else next_v++; }
}
{ ifstream f( "input.txt" ); f >> n >> m >> start; for ( int edgeNum = 0; edgeNum < m; edgeNum++ ) { int begin, end; f >> begin >> end; ++A[begin][end]; ++A[end][begin]; }
{ int neighCount = 0; for ( int j = 0; j < n; j++ ) neighCount += A[i][j]; if ( ( neighCount % 2 ) != 0 ) eulerGraph = false; }
cout << "The given graph doesn't have an euler cycle.\n"; else {
euler( start ); cout << endl; }
} */ Изтегляне 73 Kb. Сподели с приятели:
|