Sto provando a mettere insieme un algoritmo che visualizzerà il grado di nodo per ogni nodo in un ampio albero grafico (supponiamo che sia stato chiamato BFS). Supponiamo che sia un grafo non orientato. Non sono sicuro di come ottenere il grado di nodo di un nodo quando si passa attraverso il grafico. Stavo pensando di sommare ogni occorrenza del nodo in ogni elenco, quindi sommando tutte le occorrenze all'interno dell'elenco di quel nodo (tutte da quando è non orientato), ma non sono sicuro di come implementarlo. Rispondi solo con uno pseudocodice. Ho solo bisogno dell'algoritmo, quindi implementerò più tardi in una lingua.
BFS-get-all-degrees
occurr[v] = 0
for each v in G.v
for each u in adj[v] //loop through each adjacency list
if v==u
occurr[v]++
print occurr[v]++
Penso che sia sulla strada giusta. Non è assolutamente giusto, ma non sono sicuro di dove andare da lì.
EDIT:
Ho trovato un codice migliore. Penso che funzioni in O (V + E) ma non sono sicuro.
BFS_Node_Degree
for each vertex v in V
count = 0
for each vertex u in adj[v]
count++
print "the node ",v," has degree ", count