图及其相关题目 | Go 语言实现
图
在离散数学中，图（Graph）是用于表示物体与物体之间存在某种关系的结构。数学抽象后的“物体”称作节点或顶点（英语：Vertex，node或point），节点间的相关关系则称作*边**。[1]在描绘一张图的时候，通常用一组点或小圆圈表示节点，其间的边则使用直线或曲线。 -----------维基百科*
上面这段话表明图就是由一个个的节点和节点间的关系（边）构成的。节点与节点的关系可以是单方向的也可以是双向的。比如 A 是 B 的朋友，那 B 也是 A 的朋友，这就是双向的，也有单向的，比如 A 欠 B 钱，但 B 不欠 A 钱，这就是单向的。双向边也可以看作是两条单向边，但是它们的起点和终点是相反的。每条边都是双向的图称为无向图，反之为有向图。
图的表示
图的表示有很多，只要能够正确表示出每一个节点和节点与节点之间的关系即可，常见的有邻接表法和邻接矩阵法
-
邻接表（adjacency list） 是表示了图中与每一个顶点相邻的边集的集合，这里的集合指的是无序集。
比如一个含有三个节点并成环的无向图就可以表示为：
node adjacent node A B, C B A, C C A, B -
邻接矩阵（adjacency matrix） 是一种方阵，用来表示有限图。它的每个元素代表各点之间是否有边相连。
这里给出一种存储图的方式，存储的信息非常全，在遇到一些问题不需要这么完整的信息时可以适当删除一些字段
type Edge struct {
Weight int
From *Node // edge's start node
To *Node // edge's end node
}
type Node struct {
Value int
In int // how many edges end at this node
Out int // how many edges start at this node
Nexts []*Node // adjacent nodes
Edges []*Edge // edges which associated with this node
}
type Graph struct {
Nodes map[int]*Node // key is the node number
Edges map[*Edge]struct{} // the set of edges
}
// GenerateGraph 提供一个表示边的矩阵来生成一个图
// 每条边由一个长度为3的一维数组表示，分别为权重，起始点，终点
func GenerateGraph(matrix [][]int) *Graph {
graph := new(Graph)
graph.Nodes = make(map[int]*Node)
graph.Edges = make(map[*Edge]struct{})
for i := 0; i < len(matrix); i++ {
weight, from, to := matrix[i][0], matrix[i][1], matrix[i][2]
if _, ok := graph.Nodes[from]; !ok {
graph.Nodes[from] = &Node{Value: from}
}
if _, ok := graph.Nodes[to]; !ok {
graph.Nodes[to] = &Node{Value: to}
}
fromNode, toNode := graph.Nodes[from], graph.Nodes[to]
edge := &Edge{Weight: weight, From: fromNode, To: toNode}
graph.Edges[edge] = struct{}{}
fromNode.Out++
fromNode.Nexts = append(fromNode.Nexts, toNode)
fromNode.Edges = append(fromNode.Edges, edge)
toNode.In++
toNode.Edges = append(toNode.Edges, edge)
}
return graph
}
遍历
宽度优先（BFS）
思路：利用队列，从给定节点开始按宽度入队列，然后弹出，每弹出一个节点，将该节点未入过队列的邻接节点入队列，直到队列为空
// BFS 宽度优先遍历
func BFS(head *Node) {
if head == nil {
return
}
queue := new(Queue)
// map used to store nodes which have been queued
nodes := make(map[*Node]struct{})
queue.Add(head)
nodes[head] = struct{}{}
for !queue.IsEmpty() {
cur := queue.Poll()
fmt.Println(cur.Value)
for _, v := range cur.Nexts {
if _, ok := nodes[v]; !ok {
queue.Add(v)
nodes[v] = struct{}{}
}
}
}
}
深度优先（DFS）
思路：利用栈，从给定节点开始入栈按深度入栈，然后弹出，每弹出一个节点，将下一个没进入过栈的节点入栈，直到栈为空
// DFS 深度优先遍历
func DFS(head *Node) {
if head == nil {
return
}
stack := new(Stack)
nodes := make(map[*Node]struct{})
stack.Push(head)
nodes[head] = struct{}{}
fmt.Println(head.Value)
for !stack.IsEmpty() {
cur := stack.Pop()
for _, v := range cur.Nexts {
if _, ok := nodes[v]; !ok {
stack.Push(cur)
stack.Push(v)
nodes[v] = struct{}{}
fmt.Println(v.Value)
break
}
}
}
}
map 用于存储已经处理过了的节点，每次对弹出节点的下一个没进过栈的节点处理时还要将弹出节点压入栈的是为了当一条路走到底时可以回溯。
拓扑排序
拓扑排序，是对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。 通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。
我们想象一下这个场景，我们现在有一个 Go 应用，由四个包构成，Package A，B，C 和 main，A 没有依赖，B 依赖 A，C 依赖 A，B，main 依赖 C，B。
编译这个应用时肯定是有一个编译的先后顺序的，那就有个问题是先编译哪个包，这里很明显顺序应该是 A, B, C, main，因为 A 没有依赖最先编译，B 和 C 都依赖 A，但是 C 还依赖 B，B 还没开始编译，所以要先编译 B，然后再编译 C，最后 main 包的依赖也全部编译完成，再编译 main，每个包都需要它所依赖的包全部编译完成才能开始编译，这也是包依赖不能成环的原因。
上面决定编译顺序的过程就是一个典型的拓扑排序。
如何实现拓扑排序
思路：在有向图中依次找到入度为0的点，输出到排序结果，然后在图中抹去这个点的影响（将这个点的邻接节点的入度减少1），这时就会出现下一个入度为0的点，如此往复直到图中所有节点都被排序
使用一个 inMap 表示所有节点当前入度，抹去入度为0的节点的影响的实现就是在 inMap 中将这一节点邻接点的 value - 1
// TopologicalSort 拓扑排序
func TopologicalSort(graph *Graph) []*Node {
if graph == nil {
return []*Node{}
}
result := make([]*Node, len(graph.Nodes))
inMap := make(map[*Node]int)
i := 0
for _, v := range graph.Nodes {
inMap[v] = v.In
if v.In == 0 {
result[i] = v
i++
}
}
for cur := 0; cur != len(graph.Nodes); cur++ {
curNode := result[cur]
for _, v := range curNode.Nexts {
inMap[v] = inMap[v] - 1
if inMap[v] == 0 {
result[i] = v
i++
}
}
}
return result
}
最小生成树
最小生成树（minimum spanning tree，MST）是最小权重生成树（minimum weight spanning tree）的简称，是一副连通加权无向图中一棵权值最小的生成树。
即既保证图是连通的，所有边的权值和又最小
找到一个图的最小生成树主要从两方面入手，节点或边。这两方面都各自有一个著名的算法：kruscal 算法和 prim 算法
kruscal 算法
假设图中所有的点都是孤立的，按权值大小排序，从权值小的边开始，如果在图中加入这条边，图中形成环了，就不加入此条边，未成环在图中加入此条边，如此往复。
判断当前图是否成环的方法：一开始为每一个节点生成一个集合，遍历边的时候查看边所连接的两个节点是否在同一个集合，如果在同一个集合，则代表此时加入这条边会成环，丢球这条边，反之则将这条边连接的两个节点加到同一个集合中去
// Kruscal 生成最小生成树
func Kruscal(graph *Graph) []*Edge {
edges := make([]*Edge, len(graph.Edges))
i := 0
for k, _ := range graph.Edges {
edges[i] = k
i++
}
sort.Slice(edges, func(i, j int) bool {
return edges[i].Weight < edges[j].Weight
})
// map used to simulate sets
// key is node, value is the number of set
sets := make(map[*Node]int, 0)
i = 1
for _, v := range graph.Nodes {
sets[v] = i
i++
}
result := make([]*Edge, 0)
for _, v := range edges {
if sets[v.From] != sets[v.To] {
// merge two sets
// set the 'To' node's set to 'From' node's set
sets[v.To] = sets[v.From]
result = append(result, v)
}
}
return result
}
prim 算法
将图中所有的点和边都看作待解锁的边。现在解锁任一节点，将跟这一节点相关的边全部解锁，然后选择权重最低边添加到 result 里面去，接下来解锁这条边连接的节点，重复此操作。如果出现权重最低的边所连接的节点已经被解锁，则从已解锁的边中按权重的升序开始选择，直到发现未解锁的节点，然后继续上述操作，直到所有节点全部被解锁。
// Prim 生成最小生成树
func Prim(graph *Graph) []*Edge {
// priorityQueue used to store unlock edge
priorityQueue := make(PriorityQueue, 0)
heap.Init(&priorityQueue)
sets := make(map[*Node]struct{})
result := make([]*Edge, 0)
for _, v := range graph.Nodes {
if _, ok := sets[v]; !ok {
sets[v] = struct{}{}
for _, edge := range v.Edges {
heap.Push(&priorityQueue, edge)
}
for len(priorityQueue) != 0 {
edge := heap.Pop(&priorityQueue).(*Edge)
node := edge.To
if _, exist := sets[node]; !exist {
sets[node] = struct{}{}
result = append(result, edge)
for _, nextEdge := range node.Edges {
heap.Push(&priorityQueue, nextEdge)
}
}
}
}
}
return result
}
这里用的是标准库的 container/heap 包的 heap
最短路径
dijkstra 算法是从一个顶点到其余各顶点的最短路径算法，使用与权值没有负数的情况
首先我们维护一个最短距离表 distanceMap ，记录了初始节点 A 到其他所有节点（包括本身）的最短距离，到本身的距离为0，将所有节点看作未解锁节点。查看 distanceMap 中与 A 距离最小的节点，记住 B（不能选择已经被解锁的节点），来到 B 节点，查看与 B 相关边的权重，此时这些边的权重加上当前 distanceMap 中 B 所对应的到 A 的最短距离就是 A 借助 B 这个跳板到与 B 连通节点的距离，更新 distanceMap，将 B 解锁。重复上述操作 ，直到所有节点都被解锁，此时的 distanceMap 就是 A 到图上所有节点的最短路径
// Dijkstra 求连通图中某一节点到其他所有节点的最短路径
func Dijkstra(head *Node) map[*Node]int {
distanceMap := make(map[*Node]int, 0)
distanceMap[head] = 0
unlockedSet := make(map[*Node]struct{})
minNode := GetMinDistanceNode(distanceMap, unlockedSet)
for minNode != nil {
for _, edge := range minNode.Edges {
distance := distanceMap[edge.To]
if _, exist := distanceMap[edge.To]; !exist {
distanceMap[edge.To] = distance + edge.Weight
} else {
distanceMap[edge.To] = int(math.Min(float64(distanceMap[edge.To]), float64(distance+edge.Weight)))
}
}
unlockedSet[minNode] = struct{}{}
minNode = GetMinDistanceNode(distanceMap, unlockedSet)
}
return distanceMap
}
func GetMinDistanceNode(distanceMap map[*Node]int, unlocked map[*Node]struct{}) *Node {
var minNode *Node = nil
minDistance := math.MaxInt
for k, v := range distanceMap {
if _, exist := unlocked[k]; !exist {
if v < minDistance {
minNode = k
}
}
}
return minNode
}