代码之家 › 专栏 › 技术社区 › stevenpcurtis

快速广度优先搜索

algorithm swift

stevenpcurtis · 技术社区 · 6 年前

我对二叉树的BFS有点疯狂。

它返回正确的元素,但我似乎多次将同一节点插入队列中。

怎么了?算法不应该这么难,但我似乎做到了……

func breadthFirstSearch(_ data: Int) -> Node? {
    var queue = [Node]()
    if (self.data == data) { return self }
    queue.append(self)
    var tempNode = queue[0]

    while queue.count > 0 {
        if (tempNode.data == data) { return tempNode }

        if let lft = tempNode.left {
            queue.append(lft)
        }
        if let rht = tempNode.right {
            queue.append(rht)
        }
        tempNode = queue[0]
        queue.remove(at: 0)

    }
    return nil
}

树在哪里

class Node: CustomStringConvertible {
    var data : Int
    var left: Node?
    var right: Node?

    init(_ data : Int) {
        self.data = data
    }
    var description: String {
        return String(data) + ((left != nil) ? left!.description : "") + ((right != nil) ? right!.description : "")
    }

    func insert(_ data: Int) {
        if (self.data > data) {
            if let lft = self.left {
                lft.insert(data)
            } else {
                let left = Node(data)
                self.left = left
            }
        }
        else {
            if let rgt = self.right {
                rgt.insert(data)
            } else {
                let right = Node(data)
                self.right = right
            }
        }
    }
 }

插入

var binaryTree = Node(10)
binaryTree.insert(5)
binaryTree.insert(20)
binaryTree.insert(3)
binaryTree.insert(15)
binaryTree.breadthFirstSearch(4)

1 回复 | 直到 6 年前

Sulthan 6 年前

您只需要删除 tempNode 变量,并且总是使用队列的头部:

func breadthFirstSearch(_ data: Int) -> Node? {
    var queue = [self]

    while let head = queue.first {
        queue.remove(at: 0)

        if (head.data == data) {
          return head
        }

        if let lft = head.left {
            queue.append(lft)
        }

        if let rht = head.right {
            queue.append(rht)
        }
    }
    return nil
}

最初的实现实际上会在第一个(根)节点上迭代两次。我还从一开始就取消了不必要的重复检查。

现在,您还可以看到深度优先搜索的区别:

func depthFirstSearch(_ data: Int) -> Node? {
    var stack = [self]

    while let head = stack.popLast() {
        if (head.data == data) {
            return head
        }

        if let lft = head.left {
            stack.append(lft)
        }

        if let rht = head.right {
            stack.append(rht)
        }
    }
    return nil
}

推荐文章

sudoExclamationExclamation · iOS自动布局-高度不能小于ThanOrEqualTo

6 月前

Tom · SwiftUI.sheet导致背景白色闪烁

6 月前

Danil · 种子/填充核心数据的最佳实践?[关闭]

6 月前

Z S · SwiftUI:使用@FocusState。与视图初始化器绑定

6 月前

Robin · LazyVGrid项目预计不会击中测试区域

6 月前

Mahendra · Popover不是从SwiftUI中的项目列表中打开的[重复]

7 月前

Saurabh Saini · 结构下标

7 月前

Alex Smith · 移动到下一个视图控制器后如何显示警报?

7 月前

jnwjack · Swift:初始化不安全可变指针<CGImage?>不分配

7 月前

Moses Harding · 在SwiftUI的ForEach中以绑定和非绑定方式使用数组的单个成员,而不使用索引

7 月前