golang BFS DFS
突然想起一个面试题，用go实现不太好写，明天在想有什么好的方法实现图，暂时就想到这么实现，具体分析看代码注释
package mainimport "fmt"type list struct {data stringnext []*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] = trueif len(row[i].next) > 0 {DFS(row[i].next)} } }
}func BFS(row []*list){if len(row) == 0 {return}//下一层的点的集合nextRow := make([]*list, 0)//遍历当前层所有点，未被访问则输出并将该点能访问的点加到nextRowfor i := range row {if ok, _ := m[row[i].data];!ok {fmt.Print(row[i].data," ")m[row[i].data] = trueif 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
突然想起一个面试题，用go实现不太好写，明天在想有什么好的方法实现图，暂时就想到这么实现，具体分析看代码注释
package mainimport "fmt"type list struct {data stringnext []*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] = trueif len(row[i].next) > 0 {DFS(row[i].next)} } }
}func BFS(row []*list){if len(row) == 0 {return}//下一层的点的集合nextRow := make([]*list, 0)//遍历当前层所有点，未被访问则输出并将该点能访问的点加到nextRowfor i := range row {if ok, _ := m[row[i].data];!ok {fmt.Print(row[i].data," ")m[row[i].data] = trueif 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})
}肯定不是最好的实现方法，欢迎一起讨论
发布评论