Zachary Carter Zachary Carter - 1 month ago 17
Java Question

BFS on graph vertices and edges as neighbors

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);
                }
            }
        }

}
Comments