深广度优先遍历一般情况下我们都是用在复杂的图结构，以方便我们进行必要的检索操作。之前我用C++，Python写过图的深广度优先遍历，今天在这里想用go语言来实现这一操作，并希望对各位有帮助
邻接表
图的存贮结构很多，在这里我们选择中等难度的邻接表作为我们图的储存结构，下面的图是我模拟的一个图结构，是一个有向非连通图（F点未相连）来作为这次深广度遍历的实验图。
下面附上邻接表的代码（含注释）
package main
import "fmt"
//邻接表我们需要把顶点和边都看成是一个结构节点
//所以我们在下面创建这两种结构
//VertexNode 顶点节点结构体
type VertexNode struct {
data string //存放顶点数据
firstarc *ArcNode //顶点的第一条边
}
//ArcNode 边节点结构体
type ArcNode struct {
adjvex int //存放顶点的下标
next *ArcNode //存放下一条边节点
}
//GraphAdjacencyList 图的邻接表结构体
type GraphAdjacencyList struct {
vertexNode []VertexNode //存放顶点的数组
visted []bool //是否遍历过的bool类型数组
}
// 添加顶点
func (g *GraphAdjacencyList) addVertexNode(data string) bool {
//定义一个顶点节点实例，并储存顶点的数据
temp := VertexNode{}
temp.data = data
//判断这个顶点是否已经存在
for _, v := range g.vertexNode {
if v.data == data {
return false
}
}
//把顶点节点存入切片中，方便我们后面遍历使用
g.vertexNode = append(g.vertexNode, temp)
//初始化访问切片为false，代表这个顶点没有被访问过
g.visted = append(g.visted, false)
return true
}
//添加边节点
func (g *GraphAdjacencyList) addArcNode(verNode1, verNode2 string) bool {
//获得该边节点两头顶点在切片中的下标
index1 := g.verNodeIndex(verNode1)
index2 := g.verNodeIndex(verNode2)
//判断顶点是否存在或重复
if index1 == -1 || index2 == -1 || index1 == index2 {
return false
}
//进行顶点和边节点的逻辑连接
temp := new(ArcNode) //创建边节点实例
temp.adjvex = index2 //对边节点和顶点进行绑定
temp.next = g.vertexNode[index1].firstarc //设置该边指向的下一条边
g.vertexNode[index1].firstarc = temp
//同理设置另一个顶点
temp = new(ArcNode)
temp.adjvex = index1
temp.next = g.vertexNode[index2].firstarc
g.vertexNode[index2].firstarc = temp
return true
}
// 获得顶点的下标
func (g *GraphAdjacencyList) verNodeIndex(data string) int {
for i, v := range g.vertexNode {
if v.data == data {
return i
}
}
return -1
}
//初始化访问切片visted
func (g *GraphAdjacencyList) initVisted() {
for i, _ := range g.visted {
g.visted[i] = false
}
}
func main() {
g := GraphAdjacencyList{} //定义一个邻接表实例
//添加四个顶点
topData := [5]string{"A", "B", "C", "D", "E"}
for _, v := range topData {
if g.addVertexNode(v) == false {
fmt.Println("顶点数据重复")
}
}
//添加五条边
g.addArcNode("A", "B")
g.addArcNode("A", "C")
g.addArcNode("A", "D")
g.addArcNode("B", "D")
g.addArcNode("C", "D")
g.addArcNode("D", "E")
}深度优先遍历
深度优先遍历（Depth-First-Search），是搜索算法的一种，它沿着树的深度遍历树的节点，尽可能深地搜索树的分支。当节点v的所有边都已被探寻过，将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已探寻源节点到其他所有节点为止，如果还有未被发现的节点，则选择其中一个未被发现的节点为源节点并重复以上操作，直到所有节点都被探寻完成。
简单的说，DFS就是从图中的一个节点开始追溯，直到最后一个节点，然后回溯，继续追溯下一条路径，直到到达所有的节点，如此往复，直到没有路径为止。
例如上图，如果从A开始则会按照我标的数字顺序进行遍历：A->C(因为C点还有连通点，所以会去D而不返回A去B)->D(同上理)->E->B->F
深度优先遍历的代码
//开始DFS
func (g *GraphAdjacencyList) travelDFS(data string) bool {
index := g.verNodeIndex(data)
if index == -1 {
return false
}
g.DFS(index)
// 通过循环来达到遍历所有顶点的目的，防止非连同图无法充分遍历的情况
for i, _ := range g.vertexNode {
if g.visted[i] == false {
g.DFS(i)
}
}
g.initVisted() //初始化访问数组
return true
}
//DFS 深度优先遍历
func (g *GraphAdjacencyList) DFS(index int) {
fmt.Println(g.vertexNode[index].data)
g.visted[index] = true
//获得该顶点的第一条边节点，通过这个边节点找到另一头的顶点
p := g.vertexNode[index].firstarc
for p != nil {
u := p.adjvex
//如果顶点没有被访问，递归遍历
if g.visted[u] == false {
g.DFS(u)
}
//边节点后移
p = p.next
}
}广度优先遍历
广度优先遍历（Breadth-First-Search）是从根节点开始，沿着图的宽度遍历节点，如果所有节点均被访问过，则算法终止，BFS 同样属于盲目搜索，一般用队列数据结构来辅助实现BFS。
例如上图，如果从A开始则会按照我标的数字顺序进行遍历：A->C(因为A点还有连通点，所以会返回A去B而不通过C去D)->B(A的所有连通点都被访问过同所以通过B顶点继续访问)->D->E->F
广度优先遍历的代码
//因为我们要使用队列这个结构来辅助我们进行广度优先遍历
//所以在这里模拟一个队列出来
//QNode 队列节点结构体
type QNode struct {
data int //用来存放顶点的下标
next *QNode //指向下一个节点
}
//Queue 队列结构体
type Queue struct {
front *QNode //指向队列头的指针
rear *QNode //指向队列尾的指针
length int //队列的长度
}
//初始化队列
func (q *Queue) initQueue() {
q.front = new(QNode)
q.rear = new(QNode)
q.length = 0
q.front = q.rear
q.front.next = nil
}
//入队
func (q *Queue) enQueue(data int) {
p := new(QNode)
p.data = data
p.next = nil
q.rear.next = p
q.rear = p
q.length += 1
}
//出队
func (q *Queue) deQueue() int {
q.length -= 1
p := q.front.next
e := p.data
q.front.next = p.next
if q.rear == p {
q.rear = q.front
}
return e
}
//判断队列是否为空
func (q *Queue) judgeEmpty() bool {
if q.length == 0 {
return true
} else {
return false
}
}
//开始BFS
func (g *GraphAdjacencyList) travelBFS(data string) bool {
//获得开始访问顶点的下标
index := g.verNodeIndex(data)
if index == -1 {
return false
}
//开始BFS
g.BFS(index)
// 通过循环来达到遍历所有顶点的目的，防止非连同图无法充分遍历的情况
for i, _ := range g.vertexNode {
if g.visted[i] == false {
g.BFS(i)
}
}
g.initVisted() //初始化访问数组
return true
}
//BFS
func (g *GraphAdjacencyList) BFS(index int) {
//创建队列的实例
q := new(Queue)
//初始化队列
q.initQueue()
fmt.Println(g.vertexNode[index].data)
g.visted[index] = true
//访问过的顶点入队
q.enQueue(index)
//队列不为空
for q.judgeEmpty() == false {
//出队找未遍历的顶点
v := q.deQueue()
//创建边实例，找顶点
p := g.vertexNode[v].firstarc
for p != nil {
//如果未访问输出顶点值，入队
if g.visted[p.adjvex] == false {
fmt.Println(g.vertexNode[p.adjvex].data)
g.visted[p.adjvex] = true
q.enQueue(p.adjvex)
}
//边节点后移
p = p.next
}
}
}完整代码
详细注释在上面，这里只是一提供一个完整的深广度遍历代码
package main
import "fmt"
// //QNode 邻接表节点结构体
// type QNode struct {
// Data string //存放节点的数据
// Next *QNode //存放下一个节点的指针
// }
//QNode 队列节点结构体
type QNode struct {
data int //用来存放顶点的下标
next *QNode //指向下一个节点
}
//Queue 队列结构体
type Queue struct {
front *QNode //指向队列头的指针
rear *QNode //指向队列尾的指针
length int //队列的长度
}
//VertexNode 顶点结点结构体
type VertexNode struct {
data string //存放顶点数据
firstarc *ArcNode //顶点的第一条边
}
//ArcNode 边节点结构体
type ArcNode struct {
adjvex int //存放顶点的下标
next *ArcNode //存放下一条边节点
}
//GraphAdjacencyList 图的邻接表结构体
type GraphAdjacencyList struct {
vertexNode []VertexNode //存放顶点的数组
visted []bool //是否遍历过的bool类型数组
}
//初始化队列
func (q *Queue) initQueue() {
q.front = new(QNode)
q.rear = new(QNode)
q.length = 0
q.front = q.rear
q.front.next = nil
}
//入队
func (q *Queue) enQueue(data int) {
p := new(QNode)
p.data = data
p.next = nil
q.rear.next = p
q.rear = p
q.length += 1
}
//出队
func (q *Queue) deQueue() int {
q.length -= 1
p := q.front.next
e := p.data
q.front.next = p.next
if q.rear == p {
q.rear = q.front
}
return e
}
//判断队列是否为空
func (q *Queue) judgeEmpty() bool {
if q.length == 0 {
return true
} else {
return false
}
}
// 添加顶点
func (g *GraphAdjacencyList) addVertexNode(data string) bool {
temp := VertexNode{}
temp.data = data
for _, v := range g.vertexNode {
if v.data == data {
return false
}
}
g.vertexNode = append(g.vertexNode, temp)
g.visted = append(g.visted, false) //初始化为false代表该节点没有被访问
return true
}
//添加边节点
func (g *GraphAdjacencyList) addArcNode(verNode1, verNode2 string) bool {
index1 := g.verNodeIndex(verNode1)
index2 := g.verNodeIndex(verNode2)
if index1 == -1 || index2 == -1 || index1 == index2 {
return false
}
//进行顶点和边节点的逻辑连接
temp := new(ArcNode)
temp.adjvex = index2
temp.next = g.vertexNode[index1].firstarc
g.vertexNode[index1].firstarc = temp
temp = new(ArcNode)
temp.adjvex = index1
temp.next = g.vertexNode[index2].firstarc
g.vertexNode[index2].firstarc = temp
return true
}
// 获得顶点的下标
func (g *GraphAdjacencyList) verNodeIndex(data string) int {
for i, v := range g.vertexNode {
if v.data == data {
return i
}
}
return -1
}
//初始化访问切片visted
func (g *GraphAdjacencyList) initVisted() {
for i, _ := range g.visted {
g.visted[i] = false
}
}
//开始DFS
func (g *GraphAdjacencyList) travelDFS(data string) bool {
index := g.verNodeIndex(data)
if index == -1 {
return false
}
g.DFS(index)
// 通过循环来达到遍历所有顶点的目的
for i, _ := range g.vertexNode {
if g.visted[i] == false {
g.DFS(i)
}
}
g.initVisted() //初始化访问数组
return true
}
//DFS 深度优先遍历
func (g *GraphAdjacencyList) DFS(index int) {
fmt.Println(g.vertexNode[index].data)
g.visted[index] = true
p := g.vertexNode[index].firstarc
for p != nil {
u := p.adjvex
if g.visted[u] == false {
g.DFS(u)
}
p = p.next
}
}
//开始BFS
func (g *GraphAdjacencyList) travelBFS(data string) bool {
index := g.verNodeIndex(data)
if index == -1 {
return false
}
g.BFS(index)
for i, _ := range g.vertexNode {
if g.visted[i] == false {
g.BFS(i)
}
}
g.initVisted() //初始化访问数组
return true
}
//BFS
func (g *GraphAdjacencyList) BFS(index int) {
q := new(Queue)
q.initQueue()
fmt.Println(g.vertexNode[index].data)
g.visted[index] = true
q.enQueue(index)
for q.judgeEmpty() == false {
v := q.deQueue()
p := g.vertexNode[v].firstarc
for p != nil {
if g.visted[p.adjvex] == false {
fmt.Println(g.vertexNode[p.adjvex].data)
g.visted[p.adjvex] = true
q.enQueue(p.adjvex)
}
p = p.next
}
}
}
func main() {
g := GraphAdjacencyList{} //定义一个邻接表
//添加四个顶点
topData := [6]string{"A", "B", "C", "D", "E", "F"}
for _, v := range topData {
if g.addVertexNode(v) == false {
fmt.Println("顶点数据重复")
}
}
//添加五条边
g.addArcNode("A", "B")
g.addArcNode("A", "C")
g.addArcNode("B", "D")
g.addArcNode("C", "D")
g.addArcNode("D", "E")
//深度优先遍历
fmt.Println("深度优先遍历")
g.travelDFS("A")
//广度优先遍历
fmt.Println("广度优先遍历")
g.travelBFS("A")
}