ZASTOSOWANIE GRAFÓW
Cykl Eulera
Głogów
Lubin
Legnica
Wrocław
Jel. Góra
Świdnica
Wałbrzych
Definicja problemu
1
Głogów 1
J. Góra 2
Legnica 3
4
Lubin 4
Świdnica 5
3
Wałbrzych 6
Wrocław 7
7
2
5
6
1-2, 1-4, 2-3, 2-5, 2-6, 3-4, 3-5, 3-7, 5-6, 5-7
Znalez
ć drogę przez wszystkie miasta, która zawiera każdą krawędz
dokładnie raz
Rozwiązanie problemu
Definicja danych:
struct el { int V; el *nast; } *stos = NULL;
int push(int id);
int pop();
int graf[2][10] = {{1,1,2,2,2,3,3,3,5,5},{2,4,3,5,6,4,5,7,6,7}};
int start = 1; // bieżący wierzchołek
int i,k=0,n; // licznik krawędzi, licznik wierzchołków, numer kolumny w graf
Algorytm postępowania:
1. Przeszukać pierwszą kolumnę (n=0) w poszukiwaniu wartości start
2. Przeszukać drugą kolumnę (n=1), jeżeli niema w pierwszej
3. Jeżeli wartość start znaleziono (i<10), odłożyć start na stos (push(start)), przejść do
następnego wierzchołka (start = graf[(!n)][i]), usunąć łączącą krawędz
(graf[0][i] = 0;
graf[1][i] = 0;). Przejść do kroku 5
4. Wydrukować wartość start. Odczytać ze stosu pierwszy element (start = pop()). Zwiększyć
licznik k (k++).
5. Dopóki istnieją wierzchołki na stosie (k<10) przejść do kroku 1.
WYNIKI
Początek Trasa
Głogów 1-4-3-7-5-2-6-5-3-2-1
J. Góra 2-6-5-3-7-5-2-1-4-3-2
Legnica 3-7-5-2-6-5-3-2-1-4-3
Lubin 4-3-7-5-2-6-5-3-2-1-4
Świdnica 5-3-7-5-2-1-4-3-2-6-5
Wałbrzych 6-5-3-7-5-2-1-4-3-2-6
Wrocław 7-5-2-6-5-3-2-1-4-3-7