Złożoność czasu BFS

BFS oznacza wyszukiwanie w oddechu. Wyszukiwanie oddechowe jest algorytmem wyszukiwania określonego węzła w drzewie. Węzeł lub wierzchołek oznacza to samo dla drzewa. Celem tego artykułu jest wyjaśnie. C ++ jest używany do kodowania.

Treść artykułu

• • Wprowadzenie - patrz wyżej
  • Wyszukiwanie oddechowe
  • Krótka uwaga na temat złożoności czasu
  • Wyszukiwanie wierzchołka przez wyszukiwanie w oddechu
  • Wniosek

Wyszukiwanie oddechowe

Drzewo
Schemat drzewa ilustrujący wyszukiwanie w oddechu jest następujące:

Aby szukać węzła, algorytm zaczyna się od węzła głównego 1, a następnie do węzła 2, węzła 3 itp. Poziom według poziomu, od góry do dołu, od lewej do prawej, dopóki nie spełni węzła, którego szuka.

Przechowywanie drzewa
Drzewo jest jak prosty wykres. W tym artykule drzewo jest przechowywane za pomocą listy sąsiedniej. Lista sąsiedniej wskazuje węzeł (wierzchołek) i wszystkie jego sąsiednie węzły (wierzchołki), jak następuje, na poprzednim schemacie:

1 przylegający do 2, 3, 4
2 przylegające do 1, 5, 6
3 w sąsiedztwie 1
4 przylegające do 1, 7, 8
5 w sąsiedztwie 2, 9, 10
6 sąsiaduje z 2
7 w sąsiedztwie 4, 11, 12
8 w sąsiedztwie 4
9 w sąsiedztwie 5
10 w sąsiedztwie 5
11 w sąsiedztwie 7
12 w sąsiedztwie 7

Krawędź
Krawędź to linia łącząca wierzchołek i sąsiedni wierzchołek. Można go również uznać za parę, złożoną z wierzchołka (węzeł) i sąsiedniego wierzchołka (sąsiedni węzeł). Tak więc poprzednie drzewo ma następujące krawędzie dla odpowiednich wierzchołków:

3 krawędzie: 1 w sąsiedztwie 2, 3, 4
3 krawędzie: 2 sąsiadujące z 1, 5, 6
1 krawędź: 3 w sąsiedztwie 1
3 krawędzie: 4 w sąsiedztwie 1, 7, 8
3 krawędzie: 5 w sąsiedztwie 2, 9, 10
1 krawędź: 6 w sąsiedztwie 2
3 krawędzie: 7 w sąsiedztwie 4, 11, 12
1 krawędź: 8 w sąsiedztwie 4
1 krawędź: 9 w sąsiedztwie 5
1 krawędź: 10 w sąsiedztwie 5
1 krawędź: 11 w sąsiedztwie 7

Struktura C ++
Poprzednie informacje można przechowywać w wektorze C ++ wektorów. Każdy wiersz zaczyna się od węzła, a następnie jego sąsiednie węzły. Wektor wektora C ++, dla poprzedniego drzewa jest następujący:

wektor vtr = 1, 2, 3, 4,
2, 1, 5, 6,
3, 1,
4, 1, 7, 8,
5, 2, 9, 10,
6, 2,
7, 4, 11, 12,
8, 4,
9, 5,
10, 5,
11, 7,
12, 7;

Krótka uwaga na temat złożoności czasu

Rozważ następujący kod:

int n = 10;
dla (int i = 0; iCout << i << ", ";

Wyjście to:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

Zakładając, że instrukcja Cout jest prostą operacją, mówi się, że złożoność czasu (prędkość) dla tej pętli jest O (n), gdzie n w tym przypadku wynosi 10. Duża O, a następnie wsporniki z N jest notacja złożoności czasu (prędkość). Rozważ następujący kod:

int n = 10;
dla (int i = 0; i<7; i++)
Cout << i << ", ";

Wyjście to:

0, 1, 2, 3, 4, 5, 6,

Chociaż N to 10, nie wydrukowano do 10 elementów (wydrukowano 7 elementów). Wciąż mówi się, że złożoność czasu jest O (n). Jest to maksymalna możliwa liczba operacji, które są brane pod uwagę.

Rozważ następujący kod:

int n = 10;
int m = 10;
dla (int i = 0; iCout << i << ", ";

Cout << endl;
dla (int i = 0; iCout << i << ", ";

Cout << endl;

Wyjście to:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

Istnieją dwa w pętli dla 10 zmiennych, dla N i M. Mówi się, że złożoność czasu (prędkość) brzmi: o (n + m). Nawet jeśli wyjście to:

0, 1, 2, 3, 4, 5, 6
0, 1, 2, 3, 4, 5, 6

Złożoność czasu jest nadal podawana jako O (N + M). Jest to maksymalna możliwa liczba operacji, które są brane pod uwagę. Ponadto, jeśli wyjście to:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

Zgodnie z konwencją złożoność czasu jest nadal podawana jako O (N + M).

Wyszukiwanie wierzchołka przez wyszukiwanie w oddechu

Wikipedia.Org podaje algorytm w następujący sposób:

• Użyj kolejki (pierwszy na pierwszym miejscu).
• Sprawdź, czy wierzchołek został zbadany przed enqueue z wierzchołkiem.

Następnie mówi, że złożoność czasu jest:

O (| v | + | e |)

Gdzie | v | to liczba wierzchołków (węzłów) i | e | to liczba krawędzi.

Jeśli struktura drzewa jest podana jako wektor wektorów, podobnie jak w poprzednim przypadku, nie będzie potrzeby używania kolejki. Po prostu zeskanuj wektor wektorów, od góry do dołu, aż zobaczy się wierzchołek, który jest szukany. Ta procedura nadal daje złożoność czasu O (| v | + | e |).

Załóżmy, że dla poprzedniego drzewa należy szukać wierzchołka 9. Z tabeli krawędzi/węzłów ponownie przesyłane w następujący sposób, dla łatwego dostępu liczba krawędzi wynosi 19, a liczba węzłów to 9:

3 krawędzie: 1 w sąsiedztwie 2, 3, 4
3 krawędzie: 2 sąsiadujące z 1, 5, 6
1 krawędź: 3 w sąsiedztwie 1
3 krawędzie: 4 w sąsiedztwie 1, 7, 8
3 krawędzie: 5 w sąsiedztwie 2, 9, 10
1 krawędź: 6 w sąsiedztwie 2
3 krawędzie: 7 w sąsiedztwie 4, 11, 12
1 krawędź: 8 w sąsiedztwie 4
1 krawędź: 9 w sąsiedztwie 5
1 krawędź: 10 w sąsiedztwie 5
1 krawędź: 11 w sąsiedztwie 7

Operacje to 9 + 19 = 28. W tej tabeli krawędzie są cytowane po lewej stronie, a wierzchołki są cytowane po prawej stronie. Ponownie, jest to maksymalna możliwa suma, która jest uwzględniona, to znaczy: 11 + 21 = 32. Oznacza to, że istnieje jedenaście wierzchołków plus 21 krawędzi, czyli O (11 + 21), napisane ogólnie jako O (| v | + | e |).

Kod C ++ do wyszukiwania Vertex 9 to:

int licznik = 0;
dla (unsigned i = 0; idla (unsigned j = 0; jlicznik = licznik + 1;

if (vtr [i] [0] == 9)
przerwa;

Cout << counter << endl;

Wyjście to 28, z maksymalnie 32.

Wniosek

Złożoność czasu BFS to:

O (| v | + | e |)

Gdzie | v | to liczba wierzchołków (węzłów) i | e | to liczba krawędzi.