3

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
2

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]
  • New users are allowed to upvote, so maybe someone else will help you out there for the good answer. I came up with something that runs in O(V+E) do you think it will still work or do you think this won't work? I added the code to the original post. What do you think is the time-complexity of your code? – stackuser Jun 18 '13 at 1:24
  • My algorithm runs in O(V). Your last algorithm does exactly the same in O(V+E). – McMannus Jun 18 '13 at 7:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.