PICT0017a

5. Wygenerować N=50 grafów skierowanych o n wierzchołkach i m=0.8*n*n krawędziach za pomocą grafgen. Przyjąć 1 za wierzchołek źródłowy. Przeszukiwać te grafy algorytmem bfsjss. Zbadać w funkcji n od 1 do 100: a) złożoność oczekiwaną A przeszukiwania osiągniętego podgrafu (operacja dominująca - przypisanie); b) wartość oczekiwana liczby przetworzonych wierzchołków unormowana do n. Sporządzić 2 wykresy. Wyjaśnić ich przebieg w oparciu o teorię. Czy złożoność zależy od charakteru danych? Wnioski.