cykl Hamiltona - algorytm rekurencyjny

dane z pliku: grafh4.txt ten plik: grafh4.re8
v lsas sąsiedzi
1 3 2 4 5
2 5 1 3 5 4 6
3 2 2 6
4 5 1 2 5 8 7
5 6 1 2 4 8 6 9
6 5 3 2 5 8 9
7 2 4 8
8 5 9 6 5 4 7
9 3 6 8 5

przebieg obliczen - start 8

oznaczenia dla wierzchołków: * jest na stosie, + był uwzględniony

na stosie

iter

ile

wykaz wierzchołków

sąsiedzi front

v+ v-

1

1

8

9 6 5 4 7

9

2

2

8 9

6 8* 5

6

3

3

8 9 6

3 2 5 8* 9*

3

4

4

8 9 6 3

2 6*

2

5

5

8 9 6 3 2

1 3* 5 4 6*

2

6

6

8 9 6 3 2 1

2* 4 5

4

7

7

8 9 6 3 2 1 4

1* 2* 5 8* 7

5

8

8

8 9 6 3 2 1 4 5

1* 2* 4* 8* 6* 9*

5

9

7

8 9 6 3 2 1 4

1* 2* 5+ 8* 7

7

10

8

8 9 6 3 2 1 4 7

4* 8*

7

11

7

8 9 6 3 2 1 4

1* 2* 5+ 8* 7+

4

12

6

8 9 6 3 2 1

2* 4+ 5

5

13

7

8 9 6 3 2 1 5

1* 2* 4 8* 6* 9*

4

14

8

8 9 6 3 2 1 5 4

1* 2* 5* 8* 7

7

15 9

=

n 8 9 6 3 2 1 5 4 7 4* 8* = startowy

znaleziony cykl Hamiltona

8 7 4 5 1 2 3 6 9 8

1

4

7

2

5

8

3

6

9