I’m trying to put together an algorithm that will display the node degree for every node in a breadth first tree graph (assume BFS was called). Assume it’s an undirected graph. I’m not sure how to get the node degree of a node when going through the graph. I was thinking about adding up every occurrence of the node in every list, then adding up all the occurrences within that node’s list (all of them since it’s undirected), but I’m not sure not how to implement. Just answer with pseudocode. I just need the algorithm, then I’ll implement later in a language.
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]++
I think that’s on the right track. It’s definitely not right, but not sure where to go from there.
EDIT:
I came up with some better code. I think it runs in O(V+E) but not sure.
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
0
Well, just recall the definition of degree in undirected graphs:
A node’s degree in an undirected graph without multiple edges is equal to the count of its neighbor nodes (=its adjacent nodes).
Since the adjacence list’s count of each node is equal to its neigbor node count, the algorithm looks like this:
BFS-get-all-degrees
occurr[v] = 0
for each v in G.v
occurr[v] = adj[v].Count
print occurr[v]
2