之前在项目中用 Golang 实现了一个图的数据结构,并且实现了相关的一些算法,比如 BFS, DFS以及检测是否有环等等。在这里就将实现的代码,过程和算法原理做一个总结。

基本数据结构

有好几种数据结构可以实现图,比如邻接矩阵,邻接表和十字链表等,我这里使用的就是最常见的邻接矩阵的方法。

Node

定义一个图需要定义图中节点(Node)的结构,节点是保存数据的最小部分,节点的定义基本上是需要根据实际情况来定,这里我定义的Node如下:

1
2
3
4
5
type Node struct {
Data interface{}
InputTags map[string]string
OutputTags map[string]string
}

其中Data是任意的数据类型,而InputTags和OutputTags是一个map对象,定义了该节点输入和输出信息,使用map而不是使用数组的原因是我需要查找某一个tag是否存在,因此map效率更高点。

Graph

在Graph数据结构中需要包含以下信息:Node节点列表,邻接矩阵,图的大小以及目前拥有的节点数量。定义的结构如下:

1
2
3
4
5
6
type Graph struct {
NodeCount int
Size int
NodeArray []Node
Matrix []int
}

邻接矩阵使用int数组实现,如果需要第row行,第col列的矩阵值(row和col从0开始,因此row=1,即第二行),则g.Matrix[row*g.Size+col]即可获得。

常用方法

图的常用方法有以下:

  • 创建一个图
  • 向图中添加节点
  • 设置邻接矩阵
  • 深度优先遍历
  • 广度优先遍历
  • 判断是否有环

创建图

创建图即为图数据结构的各个元素进行初始化,设定其size:

1
2
3
4
5
6
func MakeGraph(size int) Graph {
g := Graph{Size: size}
g.NodeArray = make([]Node, size)
g.Matrix = make([]int, size*size)
return g
}

添加节点

添加节点这里也比较简单,因为并没有在添加节点的时候定义各个节点的关系(即设置邻接矩阵),当然也可以在添加节点的时候做。

1
2
3
4
5
6
7
func (g *Graph) AddNode(node Node) {
if g.NodeCount >= g.Size {
return
}
g.NodeArray[g.NodeCount] = node
g.NodeCount++
}

这里只是简单的判断了是否超过图的size,然后将该节点放入图的节点数组里,然后节点总数值加一。

设置邻接矩阵

具体到不同情况,如何设置邻接矩阵也不同,这主要依赖的是图中各个节点之间的关系。我这里是等到将所有节点添加到图中之后,对图的所有节点进行一次遍历,可以想象就是迭代邻接矩阵的每一行(一个节点),然后去找对应其他节点的关系(可以包含当前节点,也可以不包含,看具体情况。我这里是包含的,因为如果有自身节点到自身的关系,则说明有环,那么这个节点就是非法的)。

具体代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func (g *Graph) SetValueToMatrixFromTags() bool {
if len(g.NodeArray) != g.Size {
return false
}
for row := 0; row < len(g.NodeArray); row++ {
for col := 0; col < len(g.NodeArray); col++ {
outputTagsRow := g.NodeArray[row].OutputTags
inputTagsCol := g.NodeArray[col].InputTags
for tag, _ := range outputTagsRow {
if _, ok := inputTagsCol[tag]; ok {
g.Matrix[row*g.Size+col] = 1
break
}
}
}
}
return true
}

在我这个场景里就是判断当前节点的输出tag,是哪个节点的输入tag,如果有一个是,则将矩阵对应的值设为1。当然也可以设为其他值,表示有权重的,是具体情况而定,我这里只需要有向图就行了。

深度优先遍历

深度优先遍历可以按照递归的方法,也可以按照迭代的方法实现。递归的话本身就有一个栈,这样可以获取到相关的信息,迭代放啊就得自己模拟一个栈,实现难度是高于递归方法的。

主要思想就是比如从一个节点a出发,找到了下一个节点b的路径,那么会继续从b去搜索下一层路径,直到最后无路可走。无路可走的时候就会返回上一层,以此类推就遍历完了。而且这里还涉及到一个检查是否有环的关键点,就是记录目前的路径上的节点,如果接下来搜索的下一个节点已经记录过了,那就说明有环。

下面的代码将深度优先和检测有环结合在一起:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func (g *Graph) Dfs(stack *list.List, onStack map[int]bool, visited map[int]bool) error {
indexEle := stack.Back()
nodePos := indexEle.Value.(int)
onStack[nodePos] = true
visited[nodePos] = true
for col := 0; col < g.NodeCount; col++ {
if g.Matrix[nodePos*g.Size+col] != 0 {
visit, ok := visited[col]
if !ok || !visit {
ele := stack.PushBack(col)
err := g.Dfs(stack, onStack, visited)
if err != nil {
return err
}
stack.Remove(ele)
} else if nodeOnStack, ok := onStack[col]; ok && nodeOnStack {
return errors.New("have Cycle")
}
}
}
onStack[nodePos] = false
return nil
}

这里stack是模拟出来的一个栈,用于记录目前遍历的路径上有哪些节点加入进来了,其实和onStack的意义是一样,但是List是有顺序的,因此代表的是调用节点的一个顺序。而onStack是一个map,更多的是判断某个节点是否存在于这个路径上。Golang是比较麻烦,如果对于Python,直接一个List即可,不过这样分开,效率也能高一点。visited表示的是对于全局来说有没有遍历过这个节点,如果遍历过,就不用再遍历了,要不然递归不完了。

下来就是一个循环,用于找下一个要遍历的节点,然后再调用DFS,同时这里还对onStack进行了判断,如果已经存在,说明有环,则返回一个error,之后这个error会递归的返回,那么就会返回一个error栈。同时stack这个链表也记录了当前出现环的路径。

检测是否有环

对于一个图,检测其是否有环,就需要从每个节点出发去DFS,因为图中可能会有子图是不联通的。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func (g *Graph) CheckCycle(checkEnd int) (bool, []int) {
visited := make(map[int]bool)
onStack := make(map[int]bool)
var processIds []int
for index := 0; index < checkEnd; index++ {
stack := list.New()
ele := stack.PushBack(index)
err := g.Dfs(stack, onStack, visited)
if err != nil {
for e := stack.Front(); e != nil; e = e.Next() {
nodePos := e.Value.(int)
process := g.NodeArray[nodePos].Data.(Process)
processIds = append(processIds, process.ID)
}
return true, processIds
}
stack.Remove(ele)
}
return false, nil
}

小结

其实根据上面这个简单的图定义可以解决很多问题,稳定而又效率高。