Java BFS

[kenshinu]

Hi was wondering if someone could describe the BFS search to me. I've looked on the web but it doesn't really help me understand what I'm doing.

I have a graph that has two Hashtable<String, HashSet<String> that contains the data. One contains movies with sets of actors, the other has actors and sets of movies. I'm not sure which one I need to use.

So, would you be able to help me?

Thanks =]

 

[Nimble]

Hi was wondering if someone could describe the BFS search to me. I've looked on the web but it doesn't really help me understand what I'm doing.

I have a graph that has two Hashtable<String, HashSet<String> that contains the data. One contains movies with sets of actors, the other has actors and sets of movies. I'm not sure which one I need to use.

So, would you be able to help me?

Thanks =]

The Wikipedia page looks pretty good to me, particularly the animated example.

 

[drak3]

Pick root node, expand it and add children at the end of the queue. Dispose of root, now queue has [Child 1, Child 2, ..., Child n]

Pick head of queue (child 1) and expand it and add children at the end of the queue. Dispose of child 1, now queue has [Child 2, Child 1-1, Child 1-2, ..., Child n]

As you can see by taking the head, expanding it and then adding at the end of the queue you traverse breadth first. The new children go at the back so the next-in-line node is at the same level.

The queue can be an ArrayList since you are in java. remove(0) and add(Node) will give you the head and add at the end.

Note: Here I assume yours graph is acyclic. Else we need to keep track of nodes-visited.


Regarding your specific problem, the description does not make any sense sorry. You have 2 graphs? If you are dealing with actors and movies why are these stored as a graph anyway? What it is you are trying to achieve?