Golang实现拓扑排序(DFS算法版)
问题描述：有一串数字1到5，按照下面的关于顺序的要求，重新排列并打印出来。要求如下：2在5前出现，3在2前出现，4在1前出现，1在3前出现。
该问题是一个非常典型的拓扑排序的问题，一般解决拓扑排序的方案是采用DFS-深度优先算法，对于DFS算法我的浅薄理解就是递归，因拓扑排序问题本身会有一些前置条件（本文不过多介绍拓扑算法的定义），所以解决该问题就有了以下思路。
先将排序要求声明成map（把map的key，value看作对顺序的要求，key应在value前出现），然后遍历1-5这几个数，将每次遍历取出的数在map中key查找是否存在，如果存在就按map中key，value的关系，放入结果数组中。再用刚map[key]获取的value去map中的key查找是否存在，如果存在就将新的key和value放入结果数组的一头一尾，以此类推，最终打印结果数组，应满足本题的要求。下面就用Golang实现上述的问题。
packagemain
import(
"fmt"
"strconv"
)
//edge要求的顺序
varedgemap[string]string=map[string]string{
"2":"5",
"3":"2",
"4":"1",
"1":"3",
}
funcmain(){
//结果数组
varq[]string=make([]string,0)
//已访问数组
varvisited[]string=make([]string,0)
fori:=0;i<5;i++{
tupusort(&q,&visited,strconv.Itoa(i))
}
//fmt.Printf("visited:%v\n",visited)
reverse(q)
fmt.Printf("topusort:%v\n",q)
}
//拓扑排序-DFS
functupusort(q*[]string,visited*[]string,elementstring){
if!isVisited(visited,element){
*visited=append(*visited,element)
ifedge[element]!=""{
tupusort(q,visited,edge[element])
}
*q=append(*q,element)
}
}
//检查是否存在已访问的数组中
funcisVisited(visited*[]string,elementstring)bool{
varisVisitedbool=false
for_,item:=range*visited{
ifitem==element{
isVisited=true
break
}
}
returnisVisited
}
//反转数组顺序
funcreverse(arr[]string){
fori,j:=0,len(arr)-1;i
最后输出结果为
topusort:[413250]
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。