Golang實現(xiàn)拓撲排序(DFS算法版)
更新時間：2019年11月04日 10:33:46 作者：hellowoody
這篇文章主要介紹了Golang實現(xiàn)拓撲排序(DFS算法版)，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
問題描述：有一串數(shù)字1到5，按照下面的關(guān)于順序的要求，重新排列并打印出來。要求如下：2在5前出現(xiàn)，3在2前出現(xiàn)，4在1前出現(xiàn)，1在3前出現(xiàn)。
該問題是一個非常典型的拓撲排序的問題，一般解決拓撲排序的方案是采用DFS-深度優(yōu)先算法，對于DFS算法我的淺薄理解就是遞歸，因拓撲排序問題本身會有一些前置條件（本文不過多介紹拓撲算法的定義），所以解決該問題就有了以下思路。
先將排序要求聲明成map（把map的key，value看作對順序的要求，key應(yīng)在value前出現(xiàn)），然后遍歷1-5這幾個數(shù)，將每次遍歷取出的數(shù)在map中key查找是否存在，如果存在就按map中key，value的關(guān)系，放入結(jié)果數(shù)組中。再用剛map[key]獲取的value去map中的key查找是否存在，如果存在就將新的key和value放入結(jié)果數(shù)組的一頭一尾，以此類推，最終打印結(jié)果數(shù)組，應(yīng)滿足本題的要求。下面就用Golang實現(xiàn)上述的問題。
package main
import (
"fmt"
"strconv"
)
//edge 要求的順序
var edge map[string]string = map[string]string{
"2": "5",
"3": "2",
"4": "1",
"1": "3",
}
func main() {
//結(jié)果數(shù)組
var q []string = make([]string, 0)
//已訪問數(shù)組
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)
}
}
//檢查是否存在已訪問的數(shù)組中
func isVisited(visited *[]string, element string) bool {
var isVisited bool = false
for _, item := range *visited {
if item == element {
isVisited = true
break
}
}
return isVisited
}
//反轉(zhuǎn)數(shù)組順序
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]
}
}
最后輸出結(jié)果為
topusort: [4 1 3 2 5 0]
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
平時在項目開發(fā)過程中少不了對錯誤的處理,一個好用的系統(tǒng)首先要確保其健壯性,不能經(jīng)常發(fā)生錯誤就卡死之類的情況,為了讓我們的程序更加健壯,我們就需要知道golang里的錯誤處理機制是怎么樣的,這篇文章帶大家一起學(xué)習(xí),需要的朋友跟著小編一起來看看吧2024-05-05
這篇文章主要介紹了如何go語言比較兩個對象是否深度相同，文章圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-05-05
Go語言題解LeetCode1266訪問所有點的最小時間示例
這篇文章主要為大家介紹了Go語言題解LeetCode1266訪問所有點的最小時間示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-01-01
分布式鎖是一種在分布式系統(tǒng)中用于控制并發(fā)訪問的機制,ZooKeeper?和?Redis?都是常用的實現(xiàn)分布式鎖的工具,本文就來使用Zookeeper實現(xiàn)分布式鎖,希望對大家有所幫助2024-02-02
Go語言編程中判斷文件是否存在是創(chuàng)建目錄的方法
這篇文章主要介紹了Go語言編程中判斷文件是否存在是創(chuàng)建目錄的方法,示例都是使用os包下的函數(shù),需要的朋友可以參考下2015-10-10
這篇文章主要介紹了golang正則之命名分組方式，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-04-04
這篇文章主要介紹了golang切片原理詳細解析，切片在編譯時定義為Slice結(jié)構(gòu)體，并通過NewSlice()函數(shù)進行創(chuàng)建，更多相關(guān)內(nèi)容感興趣的小伙伴可以參考一下下面文章內(nèi)容2022-06-06
golang接口實現(xiàn)調(diào)用修改(值接收者指針接收者)場景詳解
這篇文章主要為大家介紹了golang接口實現(xiàn)調(diào)用修改值接收者指針接收者示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-08-08
Golang報“import cycle not allowed”錯誤的2種解決方法
這篇文章主要給大家介紹了關(guān)于Golang報"import cycle not allowed"錯誤的2種解決方法，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友可以們下面隨著小編來一起看看吧2018-08-08
這篇文章主要為大家介紹了Go語言實現(xiàn)彩色輸出示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-09-09