# Golang实现拓扑排序-DFS算法版

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]