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

hellowoody · · 1072 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

问题描述:有一串数字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]

有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:hellowoody

查看原文:Golang实现拓扑排序-DFS算法版

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1072 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传