Pourquoi la complexité temporelle de DFS et BFS O (V + E)

L'algorithme de base pour BFS:

set start vertex to visited

load it into queue

while queue not empty

   for each edge incident to vertex

        if its not visited

            load into queue

            mark vertex

Je pense donc que la complexité du temps serait:

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges) 

où vest le sommet 1àn

Premièrement, ce que j'ai dit est-il correct? Deuxièmement, comment est-ce O(N + E), et l'intuition de savoir pourquoi ce serait vraiment bien. Merci

Votre somme

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)

peut être réécrit comme

(v1 + v2 + ... + vn) + [(incident_edges v1) + (incident_edges v2) + ... + (incident_edges vn)]

et le premier groupe est O(N)tandis que l'autre est O(E).

DFS (analyse):

• La définition / l'obtention d'une étiquette de sommet / d'arête prend du O(1)temps
• Chaque sommet est étiqueté deux fois
  • une fois comme INEXPLORÉ
  • une fois comme VISITE
• Chaque arête est étiquetée deux fois
  • une fois comme INEXPLORÉ
  • une fois comme DISCOVERY ou BACK
• La méthode incidentEdges est appelée une fois pour chaque sommet
• DFS s'exécute dans le O(n + m)temps à condition que le graphique soit représenté par la structure de liste de contiguïté
• Rappeler que Σv deg(v) = 2m

BFS (analyse):

• La définition / l'obtention d'une étiquette de sommet / d'arête prend O (1) temps
• Chaque sommet est étiqueté deux fois
  • une fois comme INEXPLORÉ
  • une fois comme VISITE
• Chaque arête est étiquetée deux fois
  • une fois comme INEXPLORÉ
  • une fois comme DISCOVERY ou CROSS
• Chaque sommet est inséré une fois dans une séquence Li
• La méthode incidentEdges est appelée une fois pour chaque sommet
• BFS s'exécute dans le O(n + m)temps à condition que le graphique soit représenté par la structure de liste de contiguïté
• Rappeler que Σv deg(v) = 2m

Très simplifié sans trop de formalité: chaque arête est considérée exactement deux fois, et chaque nœud est traité exactement une fois, donc la complexité doit être un multiple constant du nombre d'arêtes ainsi que du nombre de sommets.

La complexité temporelle est O(E+V)au lieu de O(2E+V)parce que si la complexité temporelle est n ^ 2 + 2n + 7 alors elle s'écrit O (n ^ 2).

Par conséquent, O (2E + V) s'écrit O (E + V)

parce que la différence entre n ^ 2 et n importe mais pas entre n et 2n.

Je pense que chaque arête a été considérée deux fois et chaque nœud a été visité une fois, donc la complexité temporelle totale devrait être O (2E + V).

Une explication intuitive à cela consiste simplement à analyser une seule boucle:

1. visiter un sommet -> O (1)
2. une boucle for sur toutes les arêtes incidentes -> O (e) où e est un nombre d'arêtes incidentes sur un sommet v donné.

Ainsi, le temps total pour une seule boucle est O (1) + O (e). Maintenant, additionnez-le pour chaque sommet car chaque sommet est visité une fois. Cela donne

For every V
=> 

    O(1)
    +

    O(e)

=> O(V) + O(E)

Explication courte mais simple:

Dans le pire des cas, vous auriez besoin de visiter tous les sommets et arêtes, d'où la complexité temporelle dans le pire des cas est O (V + E)