golang BFS DFS
突然想起一个面试题,用go实现不太好写,明天在想有什么好的方法实现图,暂时就想到这么实现,具体分析看代码注释
package main
import "fmt"
type list struct {
data string
next []*list //代表每个节点能够访问的节点,比如v0的next为v1,v2,v3
}
var m map[string]bool
func DFS(row []*list){
if len(row) == 0 {
return
}
//跟一个节点沿着一条路径走到头,走到头之后再进行下一个节点
for i := range row {
if ok,_ := m[row[i].data];!ok{
fmt.Print(row[i].data, " ")
m[row[i].data] = true
if len(row[i].next) > 0 {
DFS(row[i].next)
}
}
}
}
func BFS(row []*list){
if len(row) == 0 {
return
}
//下一层的点的集合
nextRow := make([]*list, 0)
//遍历当前层所有点,未被访问则输出并将该点能访问的点加到nextRow
for i := range row {
if ok, _ := m[row[i].data];!ok {
fmt.Print(row[i].data," ")
m[row[i].data] = true
if len(row[i].next) != 0 {
nextRow = append(nextRow, row[i].next...)
}
}
}
BFS(nextRow)
}
func main(){
m = make(map[string]bool)
v0 := &list{data : "v0"}
v1 := &list{data : "v1"}
v2 := &list{data : "v2"}
v3 := &list{data : "v3"}
v4 := &list{data : "v4"}
v5 := &list{data : "v5"}
v6 := &list{data : "v6"}
v0.next = append(v0.next, v1,v2,v3)
v2.next = append(v2.next, v4)
v1.next = append(v1.next, v4,v5)
v3.next = append(v3.next, v5)
v4.next = append(v4.next, v6)
v5.next = append(v5.next, v6)
fmt.Print("DFS : ")
DFS([]*list{v0})
m = make(map[string]bool)
fmt.Print("\nBFS : ")
BFS([]*list{v0})
}
肯定不是最好的实现方法,欢迎一起讨论
到此这篇关于“golang BFS DFS”的文章就介绍到这了,更多文章或继续浏览下面的相关文章,希望大家以后多多支持JQ教程网!您可能感兴趣的文章:
golang BFS DFS
一文了解Python中的递归
golang基础教程
golang url 收集
Golang 中 RSA 算法的使用
golang会取代php吗
php mb_chunk_split函数支持宽字符分割
golang通过空格切割字符串数组
Golang将IP转为整型int存储
golang读取配置文件(ini文件)