图顶点和边作为邻居的 BFS

Question

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

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

这是我运行在尝试实现我发现的 BFS 示例时遇到的问题示例 -

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

    }

我是否需要调用 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);
                }
            }
        }

}

图顶点和边作为邻居的 BFS

BFS on graph vertices and edges as neighbors

java

algorithm

graph

graph-algorithm