BFS广度优先算法-图

世界之树weight · · 1243 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

BFS主要解决两个问题
1.从A点出发,查看有没有到达B点的路径?
2.从A点出发,查找到达B的最短路径

有向图BFS用.png

DFS深度优先搜索是一条道走到黑其他的道路才能继续走
上图0-1-4,0-2-4,0-3-4的查找方式
BFS广度优先搜索是类似于雷达扫描一样的去查找
上图是0-(1,2,3)-4这种查找方式

BFS的算法原理:
假设我们的查找的起点是0,终点是4
1.首先会创建一个queue把0的邻居点全部入队列
2.用一个循环遍历出队这个队列
3.去检测出队的每个元素的值是不是终点4,如果不是就把出队的这个元素的邻接点再次入队,进入第4步。反之进入第5步
4.重复2、3步骤如果
5.找到终点4就结束了

上面只是原理
通过上面的原理我们可以看到上图的一个流程
1.首先0的邻居 1,2,3加入队列

微信图片_20200116193515.png

2、队列看是循环
拿出元素1不是终点,把他的邻接点4入队尾


微信图片_20200116193940.png

3、重复第2步一直到3也出队下一步就找到一个元素是4了其实下面是3个重复的4


微信图片_20200116194238.png

当然了这里4刚好是我们要查找的终点假设4还指向5,并且我们的终点是5的话岂不是4会被查找3次了,因此通常BFS都会用一个数组来记录所有被访问的元素防止重复查找。其实加入这个的条件还有一个重要的原因防止出现死循环

假设这样的1<----->2互相指向按照上面的原理先插如2,2不满足条件插入2的邻居1,也不满足查找条件就会出现死循环

所以从面的条件来讲需要两个数据结构 一个队列 一个数组就可以

下面的代码用golang、有向图、利用的就是上面第一幅图片

队列的实现,使用单向链表实现


// 队列
/*
队列的特性较为单一,基本操作即初始化、获取大小、添加元素、移除元素等。
最重要的特性就是满足先进先出
*/
type linkNode struct {
    value MapParent
    next  *linkNode
}

type linkedList struct {
    head  *linkNode
    tail  *linkNode
    count int
}

func NewLinkList() *linkedList {
    return &linkedList{head: nil, tail: nil, count: 0}
}

func (this *linkedList) IsEmpty() bool {
    return this.count == 0
}

func (this *linkedList) Add(value MapParent) {
    node := new(linkNode)
    node.value = value

    this.count++
    if this.tail == nil {
        this.head = node
        this.tail = node
        node.next = nil
        return
    }

    this.tail.next = node
    node.next = nil
    this.tail = node
}

func (this *linkedList) Delete() *linkNode {
    if this.head == nil {
        return nil
    }

    this.count--
    if this.head == this.tail {
        node := this.head
        this.head = nil
        this.tail = nil

        return node
    }

    node := this.head
    this.head = this.head.next

    return node
}

type Queue struct {
    link *linkedList
}

func NewQueue() *Queue {
    return &Queue{link: NewLinkList()}
}

//加入队列
func (this *Queue) Put(value MapParent) {
    this.link.Add(value)
}

//pop出队列
func (this *Queue) Pop() *linkNode {
    return this.link.Delete()
}

//获得队列的长度
func (this *Queue) GetSize() int {
    return this.link.count
}

func (this *Queue) IsEmpty() bool {
    return this.GetSize() == 0
}

有向图

package main

import (
    "fmt"
    "strconv"
)

// 逻辑不是很严谨  越界的没考虑-- scanf

// 边节点结构
type EdgeTableNode struct {
    index         int            // 顶点索引
    weight        int            // 权重
    edgeTableNode *EdgeTableNode // 下一个临界点的指针
}

// 顶点的数据信息
type VertInfo struct {
    value int
    name  string
}

// 顶点节点
type VertNode struct {
    vertInfo      VertInfo //  定点的数据信息
    edgeTableNode *EdgeTableNode
}

type Graph struct {
    vertNum  int
    grapType uint8
    edgeNum  int

    hasCircle bool
    allCircle [][]int
    visted    []int

    vertNode []*VertNode
}

var arrayList []int

func NewGraph(vertNum int, edgeNum int, grapType uint8) *Graph {
    return &Graph{vertNum: vertNum, hasCircle: false, allCircle: [][]int{},
        visted: make([]int, vertNum), grapType: grapType,
        edgeNum: edgeNum, vertNode: []*VertNode{}}
}

// 只做了有向图的初始化
// 没考虑无向图
func (this *Graph) InitGrap() {
    // 顶点初始化
    for i := 0; i < this.vertNum; i++ {
        vert := &VertNode{}

        vert.vertInfo.value = i
        vert.vertInfo.name = "V" + strconv.Itoa(i)

        fmt.Println(*vert)

        this.vertNode = append(this.vertNode, vert)
    }

    // 边初始化
    var startVert int
    var endVert int
    var weight int
    var n int
    for i := 0; i < this.edgeNum; i++ {
        n, _ = fmt.Scanf("%d %d %d", &startVert, &endVert, &weight)

        fmt.Printf("%d %d %d\n", startVert, endVert, n)

        var edgeNode = this.vertNode[startVert].edgeTableNode
        if edgeNode == nil {
            tempNode := new(EdgeTableNode)
            tempNode.weight = weight
            tempNode.index = endVert
            tempNode.edgeTableNode = nil
            this.vertNode[startVert].edgeTableNode = tempNode
            continue
        }

        for edgeNode != nil {
            // 单链表尾插节点
            if edgeNode.edgeTableNode == nil {
                tempNode := new(EdgeTableNode)
                tempNode.weight = weight
                tempNode.index = endVert
                tempNode.edgeTableNode = nil
                edgeNode.edgeTableNode = tempNode
                break
            }

            edgeNode = edgeNode.edgeTableNode
        }
    }
}


// 初始化队列
var queue *Queue = NewQueue()

type MapParent struct {
    parent int
    son    int
}

// 查找最短路径
func (this *Graph) BfsNearPath(start, end int) []int {
    if start == end {
        return []int{start}
    }

    // 用来存储的是找到终点之前所有出队列的元素
    mapParent := make([]MapParent, 0)

    // 根据初始节点 把他的邻接点放入队列
    node := this.vertNode[start]
    for node.edgeTableNode != nil {
        index := node.edgeTableNode.index

        queue.Put(MapParent{parent: start, son: index})
        node.edgeTableNode = node.edgeTableNode.edgeTableNode
    }

    var find = false
    for !queue.IsEmpty() {
        // 检测队列的元素
        node := queue.Pop()

        // 已经被查看过得元素不需要再次查询 防止出现死循环
        if this.visted[node.value.son] == 1 {
            continue
        }

        // 记录出队的元素
        mapParent = append(mapParent, node.value)

        if node.value.son == end {
            find = true
            break
        }

        // 节点的邻接点入队列
        grapNode := this.vertNode[node.value.son]
        for grapNode.edgeTableNode != nil {
            index := grapNode.edgeTableNode.index
            // 记录父节点与子节点的映射
            queue.Put(MapParent{parent: node.value.son, son: index})
            grapNode.edgeTableNode = grapNode.edgeTableNode.edgeTableNode
        }

        // 记录被查询过
        this.visted = append(this.visted, node.value.son)
    }

    // 逆序查找路径
    path := []int{}

    if find == true {
        path = append(path, end)
        son := end
        for i := len(mapParent) - 1; i >= 0; i-- {
            if son == mapParent[i].son {
                path = append(path, mapParent[i].parent)
                son = mapParent[i].parent
            }
        }
    }

    // 打印查找的路径
    fmt.Println(path)
    return path
}


func GrapBfs() {
    var grap = NewGraph(5, 6, 1)
    grap.InitGrap()

    grap.BfsNearPath(0, 4)
}

func main() {
    //GrapDfs()

    GrapBfs()
}

上面的代码是找出来最短路径的,加入一些额外数据
比如每个入队的元素是包含父节点和子节点
用来最后查找到逆序遍历到路径

BFS需要额外的空间队列和数组,如果图非常大就会需要很多的空间
空间复杂度O(vert(节点数目))
时间复杂度O(顶点数 + 边数)


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:世界之树weight

查看原文:BFS广度优先算法-图

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

1243 次点击  ∙  1 赞  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传