BFS tidskompleksitet

BFS står for å puste førstesøk. Breath-First Search er en algoritme for å søke i en bestemt node i et tre. En node eller toppunkt betyr det samme for et tre. Målet med denne artikkelen er å forklare BFS -algoritmen, gi en kort merknad om tidskompleksitet og lære hvordan tidskompleksiteten er aktuelt for BFS -algoritmen. C ++ brukes til kodingen.

Artikkelinnhold

• • INNLEDNING - Se ovenfor
  • Puste første søk
  • Kort merknad om tidskompleksitet
  • Søker etter et toppunkt ved å puste første søk
  • Konklusjon

Puste første søk

Treet
Et trediagram for å illustrere puste-første-søket er som følger:

For å se etter en node, starter algoritmen med rotnoden 1 og deretter til node 2, node 3, etc. Nivå etter nivå, topp til bunn, fra venstre til høyre, til den oppfyller noden den leter etter.

Lagre treet
Et tre er som en enkel graf. I denne artikkelen lagres treet ved hjelp av en adjacency -liste. En adjacency -liste indikerer en node (Vertex) og alle dens tilstøtende noder (hjørner), som følger, i forrige diagram:

1 ved siden av 2, 3, 4
2 ved siden av 1, 5, 6
3 ved siden av 1
4 ved siden av 1, 7, 8
5 ved siden av 2, 9, 10
6 ved siden av 2
7 ved siden av 4, 11, 12
8 ved siden av 4
9 ved siden av 5
10 ved siden av 5
11 ved siden av 7
12 ved siden av 7

En kant
En kant er linjen som går sammen med et toppunkt og et tilstøtende toppunkt. Det kan også betraktes som et par, bestående av en toppunkt (node) og en tilstøtende toppunkt (tilstøtende node). Så det forrige treet har følgende kanter for de tilsvarende toppunktene:

3 kanter: 1 ved siden av 2, 3, 4
3 kanter: 2 ved siden av 1, 5, 6
1 kant: 3 ved siden av 1
3 kanter: 4 ved siden av 1, 7, 8
3 kanter: 5 ved siden av 2, 9, 10
1 kant: 6 ved siden av 2
3 kanter: 7 ved siden av 4, 11, 12
1 kant: 8 ved siden av 4
1 kant: 9 ved siden av 5
1 kant: 10 ved siden av 5
1 kant: 11 ved siden av 7

C ++ struktur
Den forrige informasjonen kan lagres i en C ++ vektor av vektorer. Hver rad begynner med en node, etterfulgt av tilstøtende noder. C ++ vektor-av-vektorene, for det forrige treet er som følger:

vektor 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;

Kort merknad om tidskompleksitet

Tenk på følgende kode:

int n = 10;
for (int i = 0; icout << i << ", ";

Utgangen er:

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

Forutsatt at cout-uttalelsen er en enkel operasjon, sies tidskompleksiteten (hastigheten) for dette for-loop å være o (n), der n i dette tilfellet er 10. The Big O etterfulgt av parentes med N er notasjonen for tidskompleksitet (hastighet). Tenk på følgende kode:

int n = 10;
for (int i = 0; i<7; i++)
cout << i << ", ";

Utgangen er:

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

Selv om N er 10, er ikke opptil 10 elementer trykt (7 elementer er skrevet ut). Tidskompleksiteten sies fortsatt å være o (n). Det er maksimalt mulig antall operasjoner som tas i betraktning.

Tenk på følgende kode:

int n = 10;
int m = 10;
for (int i = 0; icout << i << ", ";

cout << endl;
for (int i = 0; icout << i << ", ";

cout << endl;

Utgangen er:

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

Det er to for-løkker for 10 variabler hver, for n og m. Tidskompleksiteten (hastigheten) her sies å være: o (n + m). Selv om utgangen er:

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

Tidskompleksiteten er fortsatt gitt som O (N + M). Det er maksimalt mulig antall operasjoner som tas i betraktning. Også hvis utgangen er:

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,

Etter stevne er tidskompleksiteten fortsatt gitt som O (N + M).

Søker etter et toppunkt ved å puste første søk

Wikipedia.ORG gir algoritmen som følger:

• Bruk en kø (først inn først ut).
• Sjekk om et toppunkt er blitt utforsket før du har fått toppunktet.

Det fortsetter med å si at tidskompleksiteten er:

O (| v | + | e |)

Hvor | v | er antall hjørner (noder) og | e | er antallet kanter.

Hvis strukturen for treet er gitt som vektor-av-vektorer, som i forrige tilfelle, vil det ikke være behov for å bruke kø. Bare skann vektor-av-vektorene, fra topp til bunn, til toppunktet som ser etter blir sett. Denne prosedyren gir fortsatt samme tidskompleksitet av O (| V | + | E |).

Anta at for det forrige treet skal Vertex 9 søkes etter. Fra kantene/node-tabellen som ble avkortet i det følgende, for enkel tilgang, er antallet kanter 19 og antall noder er 9:

3 kanter: 1 ved siden av 2, 3, 4
3 kanter: 2 ved siden av 1, 5, 6
1 kant: 3 ved siden av 1
3 kanter: 4 ved siden av 1, 7, 8
3 kanter: 5 ved siden av 2, 9, 10
1 kant: 6 ved siden av 2
3 kanter: 7 ved siden av 4, 11, 12
1 kant: 8 ved siden av 4
1 kant: 9 ved siden av 5
1 kant: 10 ved siden av 5
1 kant: 11 ved siden av 7

Operasjonene er 9 + 19 = 28. I denne tabellen er kantene sitert til venstre og toppunktene er sitert til høyre. Igjen, det er den maksimale mulige summen som blir vurdert, det vil si: 11 + 21 = 32. Det betyr at det er elleve hjørner pluss 21 kanter, som er O (11 + 21), skrevet generelt som O (| V | + | E |).

C ++ -koden for å søke etter Vertex 9 er:

int teller = 0;
for (usignert i = 0; ifor (usignert j = 0; jteller = teller + 1;

if (vtr [i] [0] == 9)
gå i stykker;

cout << counter << endl;

Utgangen er 28, med maksimalt 32.

Konklusjon

BFS tidskompleksitet er:

O (| v | + | e |)

Hvor | v | er antall hjørner (noder) og | e | er antallet kanter.