Jquery中文网 www.jquerycn.cn
Jquery中文网 >  后端编程  >  Go语言  >  正文 golang BFS DFS

golang BFS DFS

发布时间:2021-05-13   编辑:www.jquerycn.cn
jquery中文网为您提供golang BFS DFS等资源,欢迎您收藏本站,我们将为您提供最新的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文件)

[关闭]