CODEWITHSUNDEEP
for-loopgraphlinked-listpseudocodeadjacency-list
notamathwiz
notamathwiz

Reputation: 235

understanding the finer detail of my pseudocode graph algorithm

here is my algorithm pseudocode:

input: a  directed graph G=(V,E)
output: all source nodes of G
function sources(G)
  for all u in V: in[u]=0
  for all u in V:
    for all edges (u,w) in E
    in[w]=in[w]+1

  L = empty linked list
  for all u in V
    if in[u] is 0: add u to L
  return L

what i am having trouble with is truly understanding this pseudocode, if it was written in c++ or java syntax i think i would have an easier time grasping the code. I understand the logic behind this code and how it generally works however i am still having problems understanding the finer detail of this pseudocode specifically how the in[w]=in[w]+1 works i understand that this code represents counting the indegrees and storing it in a in[] array but how is constantly adding one to in[w] supposed to represent the exploration of all edges and thus all nodes in a graph. can someone please explain in layman's terms the lines 4-7 of this pseudocode from the beginning of the first for loop to the in[w]=in[w]+1. also how should i think about u and w, is u the source node of the whole graph or is it just representing a non specific node that comes before another non specific node (w) that we are supposed to walk through in order to process the whole graph?

Upvotes: 0

Views: 363

Answers (1)

Brian Stinar
Brian Stinar

Reputation: 1109

Line 1 - Specify your input
Line 2 - Specify your output
Line 3 - define a function that takes G
Line 4 - set the array in to have all zero values for the number of vertices
Lines 5-7 - This looks like it's counting the number of times an edge goes TO a vertice.
Line 8 - empty
Line 9 - Initialize an empty linked list
Line 10-11 - for all vertices, if you don't have an an inbound node (since you're in in[u]) add you to the linked list L. 
Line 12 - return the linked list L.

I think what this psuedo-code is doing is trying to return a linked list with all nodes that are NOT RECEIVING an inbound edge. However, I'm not positive. Do you have any more context (like a book, page number, or URL that this came from?)

Good luck!

-Brian J. Stinar-

Upvotes: 1

Related Questions