数据结构之实现拓扑排序

问题：编译器如何通过源文件两两之间的局部依赖关系，确定一个全局的编译顺序？

关键算法：拓扑排序算法【有向无环图算法】

数据结构：把源文件和源文件之间的依赖关系，抽象成一个有向图，每个源文件对应图中的一个顶点，源文件之间的依赖关系就是顶点之间的边，这要求必须是一个有向无环图

• 相关算法
  • Kahn算法
    • 先统计每个顶点的入度数量
    • 然后输出入度数量为0的顶点A
    • 之后将A顶点的后置顶点入度数量全部减一
    • 重复上述两个步骤，直到所有顶点入度数量均为0
    • 最终输出的顶点顺序就是文件的编译顺序
  • DFS算法
    • 深度优先遍历，遍历图中所有顶点，而非只是搜索一个顶点到另一个顶点的路径

概述

拓扑排序适合用来解决需要通过局部顺序来推导全局顺序的问题

拓扑排序还能检测图中环的存在，对于kahn算法来说，如果最后输出顶点个数少于图中顶点个数，图中还有入度不是0的顶点，就说明图中存在环

应用：推荐裂变活动中裂变环的检测

示例图

Kahn算法实现

package main

import (
	"fmt"
	"strings"
)

var deps = [][]string{
	{"b", "a"},
	{"c", "a"},
	{"d", "c"},
	{"e", "b"},
	{"e", "d"},
	{"f", "a"},
	{"e", "f"},
}

func main() {
	topoSortByKahn(deps)
}

func BuildGraph(deps [][]string) map[string][]string {
	g := map[string][]string{}

	for i := 0; i < len(deps); i++ {
		d := deps[i][0]
		s := deps[i][1]
		if g[d] != nil {
			g[d] = append(g[d], s)
		} else {
			g[d] = []string{s}
		}
	}

	return g
}

func topoSortByKahn(deps [][]string) {
	graph := BuildGraph(deps)

	t := map[string]int{}

	// 寻找每个节点的入度量
	for k, v := range graph {
		if _, ok := t[k]; !ok {
			t[k] = 0
		}
		for i := 0; i < len(v); i++ {
			vv := v[i]
			if _, ok := t[vv]; !ok {
				t[vv] = 1
			} else {
				t[vv]++
			}
		}
	}

	// 寻找入度为0的节点
	queue := []string{}
	for k, v := range t {
		if v == 0 {
			queue = append(queue, k)
		}
	}

	// 输出编译顺序
	steps := []string{}
	for i := 0; i < len(queue); i++ {
		k := queue[i]
		steps = append(steps, k)
		for j := 0; j < len(graph[k]); j++ {
			kk := graph[k][j]
			t[kk]--
			if t[kk] == 0 {
				queue = append(queue, kk)
			}
		}
	}
	fmt.Printf("编译顺序: %s\n", strings.Join(steps, " -> "))
}

DFS算法实现

package main

import (
	"fmt"
	"strings"
)

var deps = [][]string{
	{"b", "a"},
	{"c", "a"},
	{"d", "c"},
	{"e", "b"},
	{"e", "d"},
	{"f", "a"},
	{"e", "f"},
}

func main() {
	topoSortByDFS(deps)
}

func BuildGraph(deps [][]string) map[string][]string {
	g := map[string][]string{}

	for i := 0; i < len(deps); i++ {
		d := deps[i][1]
		s := deps[i][0]
		if g[d] != nil {
			g[d] = append(g[d], s)
		} else {
			g[d] = []string{s}
		}
	}

	return g
}

func topoSortByDFS(deps [][]string) {
	// 构建邻接表
	graph := BuildGraph(deps)

	fmt.Println(graph)

	t := map[string]bool{}

	steps := []string{}

	var dfs func(string, []string)

	// 深度遍历节点
	dfs = func(node string, adj []string) {
		for i := 0; i < len(adj); i++ {
			n := adj[i]
			if t[n] {
				continue
			}
			t[n] = true
			if graph[n] != nil {
				dfs(n, graph[n])
			} else {
				dfs(n, []string{})
			}
		}
		steps = append(steps, node)
	}

	for k, v := range graph {
		if !t[k] {
			t[k] = true
			dfs(k, v)
		}
	}

	fmt.Printf("编译顺序: %s\n", strings.Join(steps, " -> "))

}