lab6 Wieczorek

2. Wejściówka. Wejściówka. Graf nieskierowany o n wierzchołkach i m krawędziach jest zapisany w tablicy struktur sąsiedztwa adj(l :n).sasiedzi. Podać średnią arytmetyczną długości tablic sasiedzi.

Zbadać złożoność obliczeniową t(n,m) algorytmu bfs_ms startującego z wierzchołka li generując za pomoc ą graf gen grafy nieskierowane o n=l :10 wierzchołkach i m=l :n*(n-l)/2 krawędziach. Za operacje dominującą przyjąć przypisanie. Czy złożoność ta zależy od egzemplarza grafu. Jeżeli tak to dla każdego (n, m) generować N=50 grafów i liczyć złożoność oczekiwaną. Sporządzić wykres trójwymiarowy. Wynik porównać z teorią Wnioski.