问题描述：有一串数字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实现上述的问题。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
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]
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://segmentfault.com/a/1190000020895337
