Golang實(shí)現(xiàn)拓?fù)渑判?DFS算法版)

發(fā)布時(shí)間：2020-10-14 19:41:51 來源：腳本之家閱讀：173 作者：hellowoody 欄目：編程語(yǔ)言

問題描述：有一串?dāng)?shù)字1到5，按照下面的關(guān)于順序的要求，重新排列并打印出來。要求如下：2在5前出現(xiàn)，3在2前出現(xiàn)，4在1前出現(xiàn)，1在3前出現(xiàn)。

該問題是一個(gè)非常典型的拓?fù)渑判虻膯栴}，一般解決拓?fù)渑判虻姆桨甘遣捎肈FS-深度優(yōu)先算法，對(duì)于DFS算法我的淺薄理解就是遞歸，因拓?fù)渑判騿栴}本身會(huì)有一些前置條件（本文不過多介紹拓?fù)渌惴ǖ亩x），所以解決該問題就有了以下思路。

先將排序要求聲明成map（把map的key，value看作對(duì)順序的要求，key應(yīng)在value前出現(xiàn)），然后遍歷1-5這幾個(gè)數(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實(shí)現(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)
}

//拓?fù)渑判?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]

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持億速云。

向AI問一下細(xì)節(jié)

Golang實(shí)現(xiàn)拓?fù)渑判?DFS算法版)

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽