041.建图、链式前向星、拓扑排序

前置知识：数组实现队列、算法笔试更推荐静态空间的方式、堆结构

建图 §

有向 VS. 无向（无向可以理解为双向）

不带权 VS. 带权

入参一般为节点数量和所有的边或者直接给图

建图的三种方式，我们图解一下

邻接矩阵 §

适合点的数量不多的图

需要的空间：$n^2$，$n$ 为节点数量

matrix[a][b] 表示 a 指向 b 的路

• 无向：将 matrix[a][b] 和 matrix[b][a] 都设置上值，相当于双向
  • 沿正对角线（左上-右下）对称
• 不带权：可以用 1 或 true 代表有路，0 或 false 代表无路
• 带权：用权值代表有路，math.MaxInt 或 math.MinInt 或 0 代表无路

package main
 
import "fmt"
 
const (
	MAXN = 11
)
 
var (
	// 邻接矩阵方式建图
	graph = [MAXN][MAXN]int{}
)
 
func main() {
	// 有向有权
	// 点的编号为 1~n
	n := 4
	// [from, to, 权]
	edges1 := [][]int{
		{1, 3, 6},
		{4, 3, 4},
		{2, 4, 2},
		{1, 2, 7},
		{2, 3, 5},
		{3, 1, 1},
	}
	build(n)
	directGraph(edges1)
	print(n)
	fmt.Println("-----------")
 
	// 无向无权
	// [from, to]
	edges2 := [][]int{
		{1, 3},
		{4, 3},
		{2, 4},
		{1, 2},
		{2, 3},
	}
	build(n)
	undirectGraph(edges2)
	print(n)
}
 
// 邻接矩阵清空
func build(n int) {
	for i := 1; i <= n; i++ {
		for j := 1; j <= n; j++ {
			graph[i][j] = 0
		}
	}
}
 
// 有向图
func directGraph(edges [][]int) {
	for _, edge := range edges {
		graph[edge[0]][edge[1]] = edge[2]
	}
}
 
// 无向图
func undirectGraph(edges [][]int) {
	for _, edge := range edges {
		graph[edge[0]][edge[1]] = 1
		graph[edge[1]][edge[0]] = 1
	}
}
 
func print(n int) {
	for i := 1; i <= n; i++ {
		for j := 1; j <= n; j++ {
			fmt.Printf("%d ", graph[i][j])
		}
		fmt.Println()
	}
}

0 7 6 0 
0 0 5 2 
1 0 0 0 
0 0 4 0 
-----------
0 1 1 0 
1 0 1 1 
1 1 0 1 
0 1 1 0 

邻接表 §

最常用的方式

需要的空间：$m$，$m$ 为边的数量

table[a][b] 表示 a 指向 b 的路

• 无向：将 table[a][b] 和 table[b][a] 都设置上值，相当于双向
• 不带权：b 为下标，table[a] 中有 b 代表有路，没 b 代表没路
• 带权：b 为下标 + 权重

package main
 
import "fmt"
 
var (
	// 邻接表方式建图
	graph = [][][2]int{}
)
 
func main() {
	// 有向有权
	// 点的编号为 1~n
	n := 4
	// [from, to, 权]
	edges1 := [][]int{
		{1, 3, 6},
		{4, 3, 4},
		{2, 4, 2},
		{1, 2, 7},
		{2, 3, 5},
		{3, 1, 1},
	}
	build(n)
	directGraph(edges1)
	print(n)
 
	// 无向、无权：略
}
 
// 邻接表重建
func build(n int) {
	graph = make([][][2]int, n+1)
	for i := 1; i <= n; i++ {
		graph[i] = [][2]int{}
	}
}
 
// 有向图
func directGraph(edges [][]int) {
	for _, edge := range edges {
		graph[edge[0]] = append(graph[edge[0]], [2]int{edge[1], edge[2]})
	}
}
 
func print(n int) {
	for i := 1; i <= n; i++ {
		fmt.Printf("%d: ", i)
		for _, v := range graph[i] {
			fmt.Printf("(%d,%d), ", v[0], v[1])
		}
		fmt.Println()
	}
}

1: (3,6), (2,7), 
2: (4,2), (3,5), 
3: (1,1), 
4: (3,4), 

链式前向星 §

邻接表 使用动态结构，空间要求严苛情况下使用链式前向星。比赛必用，大厂笔试、面试不常用

链式前向星：给定最大数据量，再静态数组上实现邻接表

• head：数组，长度是点的数量 +1，下标：点；值：头边编号
  • 值为 0：代表无边
• next：数组，长度是边的数量 +1，下标：边的编号；值：下一条边的编号
• to：数组，长度是边的数量 +1，下标：边的编号；值：去往的点
• cnt：int，下一条边应该的编号，从 1 开始
• weight：有权的话，加上权值数组，长度是边的数量 +1

package main
 
import "fmt"
 
const (
	// 点的最大数量
	MAXN = 11
	// 边的最大数量
	// 注意如果无向图的最大数量是 m 条边，数量要准备 m * 2
	// 因为一条无向边要加两条有向边
	MAXM = 21
)
 
var (
	// 链式前向星方式建图
	head = [MAXN]int{}
	next = [MAXM]int{}
	to   = [MAXM]int{}
	// 如果边有权重，那么需要这个数组
	weight = [MAXM]int{}
	cnt    = 1
)
 
func main() {
	// 有向有权
	// 点的编号为 1~n
	n := 4
	// [from, to, 权]
	edges1 := [][]int{
		{1, 3, 6},
		{4, 3, 4},
		{2, 4, 2},
		{1, 2, 7},
		{2, 3, 5},
		{3, 1, 1},
	}
	build(n)
	directGraph(edges1)
	print(n)
	fmt.Println("-----------")
 
	// 无向无权
	// [from, to]
	edges2 := [][]int{
		{1, 3},
		{4, 3},
		{2, 4},
		{1, 2},
		{2, 3},
	}
	build(n)
	undirectGraph(edges2)
	print(n)
}
 
// 链式前向星清空
func build(n int) {
	cnt = 1
	for i := 1; i <= n; i++ {
		head[i] = 0
	}
}
 
// 链式前向星加边
func addEdge(from, _to, _weight int) {
	next[cnt] = head[from]
	to[cnt] = _to
	weight[cnt] = _weight
	head[from] = cnt
	cnt++
}
 
// 有向图
func directGraph(edges [][]int) {
	for _, edge := range edges {
		addEdge(edge[0], edge[1], edge[2])
	}
}
 
// 无向图
func undirectGraph(edges [][]int) {
	for _, edge := range edges {
		addEdge(edge[0], edge[1], 1)
		addEdge(edge[1], edge[0], 1)
	}
}
 
func print(n int) {
	for i := 1; i <= n; i++ {
		fmt.Printf("%d: ", i)
		for j := head[i]; j > 0; j = next[j] {
			fmt.Printf("(%d,%d), ", to[j], weight[j])
		}
		fmt.Println()
	}
}

1: (2,7), (3,6), 
2: (3,5), (4,2), 
3: (1,1), 
4: (3,4), 
-----------
1: (2,1), (3,1), 
2: (3,1), (1,1), (4,1), 
3: (2,1), (4,1), (1,1), 
4: (2,1), (3,1), 

备注 §

【必备】课程里涉及图的内容：

建图、链式前向星、拓扑排序、最小生成树、bfs、双向广搜

最短路（Dijkstra、A*、Floyd、Bellman-Ford、SPFA）

【挺难】课程里涉及图的内容：

基环树、欧拉回路、割点和桥、强连通分量、双连通分量、最大流、费用流、二分图的最大匹配

拓扑排序 §

每个节点的前置节点都在这个节点之前

要求：有向图、没有环

拓扑排序的顺序可能不只一种。拓扑排序也可以用来判断有没有环。

拓扑排序表明了点之间的依赖性：

• 做完 A 事情，才能做 B 事情
• A 代码的编译完，才能编译 B 代码

怎么求 §

入度为零法：

1. 在图中找到所有入度为 0 的点
2. 把所有入度为 0 的点在图中删掉，重点是删掉影响！继续找到入度为 0 的点并删掉影响
3. 直到所有点都被删掉，依次删除的顺序就是正确的拓扑排序结果
4. 如果无法把所有的点都删掉，说明有向图里有环

备注 §

本节课讲解拓扑排序直接使用解决的题目，下节课会讲拓扑排序扩展技巧解决的题目

拓扑排序可能用到强连通分量，将在【挺难】课程里讲述

题目1.拓扑排序模版 §

测试链接 §

• ACM 模式：【模板】拓扑排序
• 核心代码模式：210.课程表 II

邻接表（动态结构） §

package main
 
import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)
 
const (
	MAXN = 2e5 + 1
)
 
var (
	n int // 点的个数
	m int // 边的个数
	// 邻接表
	// 动态建图，比赛肯定不行，但是一般大厂笔试、面试允许
	graph [][]int
	// 拓扑排序，入度表
	indegree = [MAXN]int{}
	// 拓扑排序，用到队列
	queue      = [MAXN]int{}
	head, tail = 0, 0
	// 收集拓扑排序的结果
	ans = [MAXN]int{}
)
 
func main() {
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		n, _ = strconv.Atoi(in.Text())
		in.Scan()
		m, _ = strconv.Atoi(in.Text())
		build()
		from, to := 0, 0
		for i := 0; i < m; i++ {
			in.Scan()
			from, _ = strconv.Atoi(in.Text())
			in.Scan()
			to, _ = strconv.Atoi(in.Text())
			graph[from] = append(graph[from], to)
			indegree[to]++
		}
		if !topoSort() {
			fmt.Fprintln(out, -1)
		} else {
			fmt.Fprintf(out, "%d", ans[0])
			for i := 1; i < n; i++ {
				fmt.Fprintf(out, " %d", ans[i])
			}
			fmt.Fprintln(out)
		}
	}
	out.Flush()
}
 
func build() {
	graph = make([][]int, n+1)
	for i := 1; i <= n; i++ {
		graph[i] = []int{}
		indegree[i] = 0
	}
}
 
// 拓扑排序
// 返回：是否可以拓扑排序（有向无环）
func topoSort() bool {
	head, tail = 0, 0
	for i := 1; i <= n; i++ {
		if indegree[i] == 0 {
			queue[tail] = i
			tail++
		}
	}
	idx := 0
	for head < tail {
		cur := queue[head]
		head++
		ans[idx] = cur
		idx++
		for _, to := range graph[cur] {
			indegree[to]--
			if indegree[to] == 0 {
				queue[tail] = to
				tail++
			}
		}
	}
	return idx == n
}

链式前向星（静态结构） §

package main
 
import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)
 
const (
	MAXN = 2e5 + 1
	MAXM = 2e5 + 1
)
 
var (
	n int // 点的个数
	m int // 边的个数
	// 链式前向星，静态结构
	head = [MAXN]int{}
	next = [MAXM]int{}
	to   = [MAXM]int{}
	cnt  = 1
	// 拓扑排序，入度表
	indegree = [MAXN]int{}
	// 拓扑排序，用到队列
	queue = [MAXN]int{}
	h, t  = 0, 0
	// 收集拓扑排序的结果
	ans = [MAXN]int{}
)
 
func main() {
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		n, _ = strconv.Atoi(in.Text())
		in.Scan()
		m, _ = strconv.Atoi(in.Text())
		build()
		from, to := 0, 0
		for i := 0; i < m; i++ {
			in.Scan()
			from, _ = strconv.Atoi(in.Text())
			in.Scan()
			to, _ = strconv.Atoi(in.Text())
			addEdge(from, to)
			indegree[to]++
		}
		if !topoSort() {
			fmt.Fprintln(out, -1)
		} else {
			fmt.Fprintf(out, "%d", ans[0])
			for i := 1; i < n; i++ {
				fmt.Fprintf(out, " %d", ans[i])
			}
			fmt.Fprintln(out)
		}
	}
	out.Flush()
}
 
func build() {
	cnt = 1
	for i := 1; i <= n; i++ {
		head[i] = 0
		indegree[i] = 0
	}
}
 
func addEdge(f, t int) {
	next[cnt] = head[f]
	to[cnt] = t
	head[f] = cnt
	cnt++
}
 
// 拓扑排序
// 返回：是否可以拓扑排序（有向无环）
func topoSort() bool {
	h, t = 0, 0
	for i := 1; i <= n; i++ {
		if indegree[i] == 0 {
			queue[t] = i
			t++
		}
	}
	idx := 0
	for h < t {
		cur := queue[h]
		h++
		ans[idx] = cur
		idx++
		for i := head[cur]; i > 0; i = next[i] {
			indegree[to[i]]--
			if indegree[to[i]] == 0 {
				queue[t] = to[i]
				t++
			}
		}
	}
	return idx == n
}

复杂度 §

• 时间复杂度：$O(n+m)$
• 空间复杂度：$O(n+m)$

题目2.字典序最小的拓扑排序 §

题目描述 §

要求返回所有正确的拓扑排序中字典序最小的结果

测试链接 §

U107394 拓扑排序模板

思路 §

将队列换成小根堆即可

答案 §

package main
 
import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
)
 
const (
	MAXN = 1e5 + 1
	MAXM = 1e5 + 1
)
 
var (
	n int // 点的数量
	m int // 边的数量
	// 链式前向星，静态结构
	head = [MAXN]int{}
	next = [MAXM]int{}
	to   = [MAXM]int{}
	cnt  = 1
	// 拓扑排序，小根堆，代替队列，实现字典序最小的拓扑排序
	minHeap  = MinHeap{}
	heapSize = 0
	// 拓扑排序，入度表
	indegree = [MAXM]int{}
	// 收集拓扑排序的结果
	ans = [MAXN]int{}
)
 
func build() {
	cnt = 1
	heapSize = 0
	for i := 1; i <= n; i++ {
		head[i] = 0
		indegree[i] = 0
	}
}
 
func addEdge(f, t int) {
	next[cnt] = head[f]
	to[cnt] = t
	head[f] = cnt
	cnt++
}
 
func topoSort() {
	for i := 1; i <= n; i++ {
		if indegree[i] == 0 {
			heap.Push(&minHeap, i)
		}
	}
	idx := 0
	for heapSize > 0 {
		cur := heap.Pop(&minHeap).(int)
		ans[idx] = cur
		idx++
		for i := head[cur]; i > 0; i = next[i] {
			indegree[to[i]]--
			if indegree[to[i]] == 0 {
				heap.Push(&minHeap, to[i])
			}
		}
	}
}
 
type MinHeap [MAXN]int
 
func (*MinHeap) Len() int {
	return heapSize
}
 
func (h *MinHeap) Less(i, j int) bool {
	return h[i] < h[j]
}
 
func (h *MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}
 
func (h *MinHeap) Push(v any) {
	h[heapSize] = v.(int)
	heapSize++
}
 
func (h *MinHeap) Pop() any {
	heapSize--
	return h[heapSize]
}
 
func main() {
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		n, _ = strconv.Atoi(in.Text())
		in.Scan()
		m, _ = strconv.Atoi(in.Text())
		from, to := 0, 0
		build()
		for i := 0; i < m; i++ {
			in.Scan()
			from, _ = strconv.Atoi(in.Text())
			in.Scan()
			to, _ = strconv.Atoi(in.Text())
			addEdge(from, to)
			indegree[to]++
		}
		topoSort()
		fmt.Fprintf(out, "%d", ans[0])
		for i := 1; i < n; i++ {
			fmt.Fprintf(out, " %d", ans[i])
		}
		fmt.Fprintln(out)
	}
	out.Flush()
}

复杂度 §

• 时间复杂度：$O(n+m)+O(n\ast lo{g}^n)$，$n$ 个边弹出，每次从小根堆弹出：$lo{g}^n$
• 空间复杂度：$O(n+m)$

题目3.火星词典 §

题目描述 §

现有一种使用英语字母的火星语言，这门语言的字母顺序对你来说是未知的。

给你一个来自这种外星语言字典的字符串列表 words，words 中的字符串已经按这门新语言的字母顺序进行了排序 。

如果这种说法是错误的，并且给出的 words 不能对应任何字母的顺序，则返回 ""

否则，返回一个按新语言规则的字典递增顺序排序的独特字符串

如果有多个解决方案，则返回其中任意一个

words 中的单词一定都是小写英文字母组成的

示例 1：

输入：words = ["wrt", "wrf", "er", "ett", "rftt"]

输出："wertf"

示例 2：

输入：words = ["z", "x"]

输出："zx"

示例 1：

输入：words = ["z", "x", "z"]

输出：""

解释：不存在合法字母顺序，因此返回 ""

测试链接 §

269.火星词典

答案 §

package main
 
import (
	"fmt"
	"strings"
)
 
const (
	MAXN = 26
)
 
func alienOrder(words []string) string {
	n := len(words)
	// 入度表，26 种字符
	// -1: 没出现的字符
	indegree := [MAXN]int{}
	// 邻接表
	graph := [MAXN][]int{}
	for i := 0; i < MAXN; i++ {
		indegree[i] = -1
		graph[i] = []int{}
	}
	for _, word := range words {
		for i := 0; i < len(word); i++ {
			indegree[word[i]-'a'] = 0
		}
	}
 
	for i := 0; i < n-1; i++ {
		cur, next := words[i], words[i+1]
		curLen, nextLen := len(cur), len(next)
		length := min(curLen, nextLen)
		j := 0
		for ; j < length; j++ {
			if cur[j] != next[j] {
				graph[cur[j]-'a'] = append(graph[cur[j]-'a'], int(next[j]-'a'))
				indegree[int(next[j]-'a')]++
				break
			}
		}
		// 排错了
		if j < curLen && j == nextLen {
			return ""
		}
	}
 
	queue := [MAXN]int{}
	head, tail := 0, 0
	kinds := 0
	for i := 0; i < MAXN; i++ {
		if indegree[i] != -1 {
			kinds++
		}
		if indegree[i] == 0 {
			queue[tail] = i
			tail++
		}
	}
 
	var ans strings.Builder
	for head < tail {
		cur := queue[head]
		head++
		ans.WriteByte(byte(cur + 'a'))
		for _, to := range graph[cur] {
			indegree[to]--
			if indegree[to] == 0 {
				queue[tail] = to
				tail++
			}
		}
	}
 
	if ans.Len() == kinds {
		return ans.String()
	}
	return ""
}
 
type Test struct {
	in  []string
	out string
}
 
func main() {
	tests := []Test{
		{[]string{"wrt", "wrf", "er", "ett", "rftt"}, "wertf"},
		{[]string{"z", "x"}, "zx"},
		{[]string{"z", "x", "z"}, ""},
	}
 
	for _, t := range tests {
		if alienOrder(t.in) != t.out {
			panic("error")
		}
	}
	fmt.Println("success")
}

题目4.戳印序列 §

题目描述 §

你想要用小写字母组成一个目标字符串 target。 

开始的时候，序列由 target.length 个 '?' 记号组成。而你有一个小写字母印章 stamp。

在每个回合，你可以将印章放在序列上，并将序列中的每个字母替换为印章上的相应字母。你最多可以进行 10 * target.length  个回合。

举个例子，如果初始序列为 ”?????”，而你的印章 stamp 是 "abc"，那么在第一回合，你可以得到 “abc??”、“?abc?”、“??abc”。（请注意，印章必须完全包含在序列的边界内才能盖下去。）

如果可以印出序列，那么返回一个数组，该数组由每个回合中被印下的最左边字母的索引组成。如果不能印出序列，就返回一个空数组。

例如，如果序列是 “ababc”，印章是 "abc"，那么我们就可以返回与操作 ”?????” -> “abc??” -> “ababc” 相对应的答案 [0, 2]；

另外，如果可以印出序列，那么需要保证可以在 10 * target.length 个回合内完成。任何超过此数字的答案将不被接受。

提示：

1. 1 <= stamp.length <= target.length <= 1000
2. stamp 和 target 只包含小写字母。

测试链接 §

936.戳印序列

答案 §

func movesToStamp(stamp string, target string) []int {
	n := len(target)
	m := len(stamp)
	// indegree[i]: 以 i 位置盖印章，有几个错误？
	indegree := make([]int, n-m+1)
	for i := range indegree {
		indegree[i] = m // 一开始认为都错
	}
	graph := make([][]int, n)
	for i := range graph {
		graph[i] = []int{}
	}
	queue := make([]int, n-m+1)
	head, tail := 0, 0
	// O(n*m)
	for i := 0; i < n-m+1; i++ {
		// 以 i 开头长度为 m 的印章位置
		for j := 0; j < m; j++ {
			if target[i+j] == stamp[j] {
				indegree[i]--
				// 都对
				if indegree[i] == 0 {
					queue[tail] = i
					tail++
				}
			} else {
				// from: 错误的位置
				// to: 印章开始位置
				graph[i+j] = append(graph[i+j], i)
			}
		}
	}
 
	// 同一个位置取消错误不要重复统计
	visited := make([]bool, n)
	ans := make([]int, n-m+1)
	size := 0
	for head < tail {
		cur := queue[head]
		head++
		ans[size] = cur
		size++
		// cur: 印章开始位置
		// cur 位置盖章，可以修正如下位置
		for i := 0; i < m; i++ {
			if !visited[cur+i] {
				visited[cur+i] = true
				for _, start := range graph[cur+i] {
					indegree[start]--
					if indegree[start] == 0 {
						queue[tail] = start
						tail++
					}
				}
			}
		}
	}
 
	if size != n-m+1 {
		return []int{}
	}
	reverse(ans)
	return ans
}
 
// 逆序
func reverse(arr []int) {
	l, r := 0, len(arr)-1
	for l < r {
		arr[l], arr[r] = arr[r], arr[l]
		l++
		r--
	}
}

复杂度 §

• 时间复杂度：$O(n\ast m)$
• 空间复杂度：$O(n)$