溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
問題描述：有一串數字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]
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
