图顶点和边作为邻域的BFS

Question

我有一个图数据结构，它是我从本文中复制的-http://www.dreamincode.net/forums/topic/377473-graph-data-structure-tutorial/

我想在上面实现BFS算法。我不完全确定如何--我看到/读到的大多数关于该算法的文章都使用了更简单的数据结构。该数据结构存储顶点的散列映射，并将其字符串表示形式作为键，然后还存储边的散列映射，使用整数作为键。

这是一个我在尝试实现BFS示例时遇到的问题的例子-

null

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

    }

null

我需要调用getNeighbors然后迭代邻域中的每个唯一顶点吗？

谢谢.

Answer 1

您确实需要调用getneighbors并在每个边（因此是每个顶点）上迭代。

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

}