2016-03-24 4 views
2

Wie groß ist die Berechnungskomplexität der Breite-zuerst und der Tiefe-zuerst-Traversierung in Bezug auf die Anzahl der Ecken v und die Anzahl der Kanten e, wenn der Graph als Adjazenzmatrix dargestellt wird?Komplexität der Graph-Traversierung

Antwort

0

Die Komplexität ist O(v^2), da die Adjazenzmatrix durchsucht werden muss, um alle Nachbarn eines einzelnen Eckpunkts zu erhalten.