Zachary Carter - 8 months ago 51

Java Question

I have a graph data structure, that I copied from this article - http://www.dreamincode.net/forums/topic/377473-graph-data-structure-tutorial/

And I'd like to implement the BFS algorithm on it. I'm not entirely sure how - most articles I see / read about the algorithm use simpler data structures. This data structure stores a hash map of vertices with their string representation as keys, and then also stores a hashmap of edges, using integers as keys.

Here's an example of the problem I run into when trying to implement a BFS example I found -

`public void bfs(Vertex rootNode){`

Queue q = new LinkedList();

q.add(rootNode);

rootNode.visited=true;

while(!q.isEmpty()){

Vertex n = (Vertex)q.poll();

System.out.print(n.toString() + " ");

for(Vertex adj : n.getNeighbors()){ -- Here's my problem. Get neighbors doesn't return a list of verts, it returns a list of edges.

if(!adj.visited){

adj.visited=true;

q.add(adj);

}

}

}

}

Do I need to call getNeighbors and then iterate over each unique vertex in the neighborhood?

Thank you.

Answer

You do need to call `getNeighbors`

and iterate over each edge (hence each vertex).

```
public void bfs(Vertex rootNode){
Queue q = new LinkedList();
q.add(rootNode);
rootNode.visited=true;
while(!q.isEmpty()){
Vertex n = (Vertex)q.poll();
System.out.print(n.toString() + " ");
for(Edge edge : n.getNeighbors()){
Vertex adj = edge.getNeighbor(n);
if(!adj.visited){
adj.visited=true;
q.add(adj);
}
}
}
}
```

Source (Stackoverflow)