PICT0017

3. Wygenerować N^50 grafów skierowanych o n wierzchołkach i m^0.6*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 - operacje na kolejce); b) wartość oczekiwana liczby przetworzonych wierzchołków. Sporządzić 2 wykresy. Wyjaśnić ich przebieg w oparciu o teorię. Czy złożoność zależy od charakteru danych? Wnioski.