PDF Drukuj Email

Grafy

1. Graf - Macierz sąsiedztwa

Napisz program umożliwiający wprowadzenie do pamięci komputera grafu prostego w postaci macierzy sąsiedztwa oraz wyświetlający informację o stopniu każdego wierzchołka we wprowadzonym grafie. Program zabezpieczyć przed możliwością dokonania wprowadzenia błędnych danych. Napisać prosty edytor w trybie tekstowym umożliwiający wprowadzenie danych w postaci graficznej.

- Pascal

 

2. Graf - Macierz sąsiedztwa + Macierz incydencji

Wzbogać program z zadania 1 o dodatkowe funkcje umożliwiające konwersję macierzy sąsiedztwa do macierzy incydencji.

- Pascal

 

3. Graf - Rysowanie

Na podstawie wprowadzonej do pamięci komputera reprezentacji grafu, wykorzystując tryb graficzny narysuj graf na ekranie monitora

(kolejne rozwinięcie programu z poprzednich zadań).

- Pascal

 

4. Graf - Przeszukiwanie

Zaimplementować procedurę przeszukiwania grafów w głąb metodą DFS (depth - first search). Metoda polega na rozpoczęciu przechodzenia od odwiedzenia węzła, a następnie rekurencyjnym odwiedzeniu wszystkich nie odwiedzonych dotychczas sąsiadów tego węzła. Po odwiedzeniu wszystkich węzłów osiągalnych z węzła startowego, wybieramy kolejny węzeł. Przez osiągalność rozumiemy istnienie ścieżki od węzła początkowego do danego. Jeżeli nie był dotychczas odwiedzony, to odwiedzamy go, a potem rekurencyjnie odwiedzamy jego są siadów i tak dalej dopóki nie odwiedzimy wszystkich węzłów

(dalsze rozwinięcie powyższego programu).

- Pascal

 
Joomla themes, affordable business hosting.