Drucken-in-degree und out-degree von jedem vertex

Hinweis: Für die Kürze, ich bin mit "O" an Stelle von theta.

Keine Notwendigkeit für BFS.

In dem Fall, wo Sie Ihre Nachbarschaft-Listen bestehen aus einer Liste von gerichteten Kanten, warten zwei vertex-count-mappings, die man für in-Grad und eins für out-Grad. Jeder Knoten sollte zunächst abgebildet auf null. Iteriere durch jede Kante, u,v - und Inkrement-out-Diplom(u) und Grad(v). Nach Durchlaufen aller Kanten, die Sie Durchlaufen können jeden Scheitelpunkt, und drucken Sie Ihr Ergebnis aus dem mapping. Durchlaufen jede Kante ist in O(m), das Durchlaufen jeder Knoten (einmal initialisiert die mapping-und einmal, um tatsächlich drucken), ist O(n). Ihre Summe ist O(m+n).

Beispiel-codes:

#python-ish, untested

V = set([1,2,3,4,5])
#{(u,v}
E = set([(1,2),(1,3),(2,3)])

in_degree_count = {}
out_degree_count = {}

#initialize the mappings to 0
#O(n)
for u in V:
  in_degree_count[u] = 0
  out_degree_count[u] = 0

#iterate through each edge, incrementing the respective mappings for u,v
#O(m)
for u,v in E:
  out_degree_count[u] += 1
  in_degree_count[v] += 1

#iterate through each vertex to print them
#O(n)
for u in V:
  print 'out_degree({0}):'.format(u), out_degree_count[u]
  print 'in_degree({0}):'.format(u), in_degree_count[u]

Können Sie beliebige assoziative Karte für die vertex-Anzahl Zuordnungen. Wenn du eine hashmap, erhalten Sie amortisiert konstanter Zeit Operationen, und es wird keinen Einfluss haben auf den gesamten Algorithmus die Komplexität. Allerdings, wenn Sie wissen, dass die Eckpunkte sind in einer Reihe ohne Lücken, wie [1,n], dann können Sie verwenden eine Reihe von Grafen, mit dem index repräsentiert den vertex, der hat seinen Wert. Also:

in_degrees = [0] * (n + 1) #array/list of zeros, of size n,
                           # index 0 is disregarded since there is no vertex named 0
in_degree[1] = 0 # will mean that vertex `1` has an in-degree of zero.
etc.

Diese einfach gibt Sie konstant time-mapping-Operationen.

InformationsquelleAutor Realz Slaw