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(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。