邻接矩阵列表 O(m+n) 上的 BFS 如何实现？

发布于 2024-12-22 21:42:03 字数 828 浏览 2 评论 0原文

我试图弄清楚 BFS 的复杂度是 O(m+n)，其中 n 是顶点数，m 是边数。

算法是：

public void bfs()
{
    //BFS uses Queue data structure
    Queue q=new LinkedList();
    q.add(this.rootNode);
    printNode(this.rootNode);
    rootNode.visited=true;
    while(!q.isEmpty())
    {
        Node n=(Node)q.remove();
        Node child=null;
        while((child=getUnvisitedChildNode(n))!=null)
        {
            child.visited=true;
            printNode(child);
            q.add(child);
        }
    }
    //Clear visited property of nodes
    clearNodes();
}
//

在邻接表中，我们将顶点存储在数组/哈希表中，以及每个顶点与其他顶点形成的边的链表。

我的主要问题是：我们如何实现获取未访问的子节点？很明显，你将节点标记为已访问，但是在遍历时，你会遍历所有链表，因此你对每条边都计数两次，所以复杂度是 O(2m+n) 对吗？这会四舍五入到 O(m+n) 吗？

另外，我们可以对邻接矩阵采用类似的策略吗？如果给我一个大小为 nxn 的矩阵，并且我想知道是否存在特定元素，我可以通过 BFS 来解决这个问题吗？

谢谢。

原文

I'm trying to figure out how a BFS is O(m+n), where n is the number of vertices and m is the number of edges.

The algorithm is:

public void bfs()
{
    //BFS uses Queue data structure
    Queue q=new LinkedList();
    q.add(this.rootNode);
    printNode(this.rootNode);
    rootNode.visited=true;
    while(!q.isEmpty())
    {
        Node n=(Node)q.remove();
        Node child=null;
        while((child=getUnvisitedChildNode(n))!=null)
        {
            child.visited=true;
            printNode(child);
            q.add(child);
        }
    }
    //Clear visited property of nodes
    clearNodes();
}
//

In an adjacency list, we store the vertices in an array/hash table, and a linked list of the edges that each vertex forms with other vertices.

My main question is this: how do we implement get unvisited child node? It's clear that you mark nodes as visited, but when traversing, you go through all the linked lists, so you count every edge twice, so the complexity is O(2m+n) right? Does that just get rounded down to O(m+n)?

Also, can we employ a similar strategy for an adjacency matrix? If I'm given an matrix of size n x n, and I want to know if a specific element exists, can I do a BFS to figure that out?

Thanks.

分享到QQ

分享到微博