时间:2021-05-22
问题描述:有一串数字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 mainimport ( "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)}//拓扑排序-DFSfunc 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]
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
前言排序,对于每种编程语言都是要面对的。这里跟大家一起分享golang实现一些排序算法,并且说明如何生成随机数。下面话不多说了,来一起看看详细的介绍吧。经典排序
本文实例讲述了PHP实现深度优先搜索算法。分享给大家供大家参考,具体如下:深度优先搜索的实现原理:实现代码:dfs_save=array(array(0,1,1
本文实现了八个常用的排序算法:插入排序、冒泡排序、选择排序、希尔排序、快速排序、归并排序、堆排序和LST基数排序首先是算法实现文件Sort.h,代码如下:/**
一、概述: 本文给出常见的几种排序算法的原理以及Java实现,包括常见的简单排序和排序算法,以及其他常用的算法知识。简单排序:冒泡排序、选择排序、插入排序排序
我简单的绘制了一下排序算法的分类,蓝色字体的排序算法是我们用python3实现的,也是比较常用的排序算法。Python3常用排序算法1、Python3冒泡排序—