Mengapa mengatakan bahwa pencarian pertama kali berjalan dalam waktu

Sering dinyatakan (misalnya, dalam Wikipedia ) bahwa waktu berjalan pencarian pertama kali (BFS) pada grafik $G=(V,E)$ adalah $O(|V|+|E|)$ . Namun, setiap grafik yang terhubung memiliki $|V|\leq |E|+1$ dan, bahkan dalam grafik non-terhubung, BFS tidak akan pernah melihat sebuah titik di luar komponen yang berisi awal vertex. Komponen itu paling banyak memuat $|E|$ tepi, sehingga mengandung paling banyak $|E|+1$ simpul, dan mereka adalah satu-satunya yang algoritma akan mengunjungi.

Ini berarti bahwa $|V|+|E|\leq 2|E|+1$ , jadi mengapa tidak kita katakan bahwa waktu berjalan hanya $O(|E|)$ ?

_{Ini muncul dalam komentar pada pertanyaan tentang waktu berjalan algoritma Disjkstra .}

BFS biasanya menggambarkan sesuatu seperti yang berikut ini (dari Wikipedia ).

 1  procedure BFS(G,start_v):
 2      let Q be a queue
 3      label start_v as discovered
 4      Q.enqueue(start_v)
 5      while Q is not empty
 6          v = Q.dequeue()
 7          if v is the goal:
 8              return v
 9          for all edges from v to w in G.adjacentEdges(v) do
10             if w is not labeled as discovered:
11                 label w as discovered
12                 w.parent = v
13                 Q.enqueue(w)

Masalahnya agak rumit: bersembunyi di baris 3! Pertanyaannya adalah, struktur data apa yang akan kita gunakan untuk menyimpan simpul mana yang telah ditemukan?

false$\Theta(|V|)$$|V|$$|E|$$O(|V|+|E|)$

$\Theta(|V|)$$O(|V|\,|E|)$$O(|E|^2)$$|V|^4$$|V|\,|E|\leq |V|^3$

$O(\log|V|)$$O(|E|\log|V|)$

$c$$|E|+1$$c + 2c + 4c + \dots + 2|E|\leq 4|E|$ $O(1)$$O(|E|)$

$O(|E|)$$4|E|$$O(|E|)$$O(|V|+|E|)$