ZASTOSOWANIE GRAFÓW

Cykl Eulera

Legnica

Głogów

Lubin

Jel. Góra

Wałbrzych

Wrocław

Świdnica

Definicja problemu

Głogów

1

J. Góra

2

Legnica

3

Lubin

4

Świdnica

5

Wałbrzych

6

Wrocław

7

1-2, 1-4, 2-3, 2-5, 2-6, 3-4, 3-5, 3-7, 5-6, 5-7

Znaleźć drogę przez wszystkie miasta, która zawiera każdą krawędź dokładnie raz

3

1

4

2

6

7

5

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ędź (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