天枫庄资源网 Design By www.wosibo.com
问题描述:有一串数字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实现上述的问题。
package main import ( "fmt" "strconv" ) //edge 要求的顺序 var edge map[string]string = map[string]string{ "2": "5", "3": "2", "4": "1", "1": "3", } func main() { //结果数组 var q []string = make([]string, 0) //已访问数组 var visited []string = make([]string, 0) for i := 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 func tupusort(q *[]string, visited *[]string, element string) { if !isVisited(visited, element) { *visited = append(*visited, element) if edge[element] != "" { tupusort(q, visited, edge[element]) } *q = append(*q, element) } } //检查是否存在已访问的数组中 func isVisited(visited *[]string, element string) bool { var isVisited bool = false for _, item := range *visited { if item == element { isVisited = true break } } return isVisited } //反转数组顺序 func reverse(arr []string) { for i, j := 0, len(arr)-1; i < j; i, j = i+1, j-1 { arr[i], arr[j] = arr[j], arr[i] } }
最后输出结果为
topusort: [4 1 3 2 5 0]
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
天枫庄资源网 Design By www.wosibo.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
天枫庄资源网 Design By www.wosibo.com
暂无Golang实现拓扑排序(DFS算法版)的评论...
更新日志
2024年05月17日
2024年05月17日
- 白玛多吉《梦》限量1:1母盘直刻[低速原抓WAV+CUE][508M]
- 魏金栋-金歌新曲-梦里全是桂花香2CD[天凡之音][WAV+CUE]
- 鲛岛有美子-樱花赋HQCD[天龙][WAV+CUE]
- [In-Akustik7506]ReferenceSoundEdition-GreatWomenOfSong(2014)HQCD[WAV+CUE]
- 日本EMI超级名盘TOGE-11035-36BeethovenFidelio-Furtwngler
- 宝丽金50周年2010《古典篇》3CD限定盘[低速原抓WAV+CUE]
- 华纳群星.1992-永远新一天华纳15周年金钻群星演唱会2CD【华纳】【WAV+CUE】
- 原声《功夫熊猫4 OST》[FLAC][545M]
- 陈奕迅《酝酿》[WAV分轨][502M]
- Taylor Swift《THE TORTURED POETS DEPARTMENT- THE ANTHOLOGY》[320K/MP3][279.09MB]
- 崔健《85回顾+梦中的倾诉》2CD [WAV+CUE][771M]
- 群星《安桥试音碟》3CD[FLAC][1.1G]
- Taylor Swift《THE TORTURED POETS DEPARTMENT- THE ANTHOLOGY》][24bit 48kH][FLAC/分轨]
- 群星1995-阿诗玛·中国歌剧金曲[中唱][WAV+CUE]
- [JVC]吴文光-中国古琴:流水[FLAC分轨]