logo头像

待到风起时,扬帆济沧海

广度和深度搜索代码

无向矩阵图代码(DFS-BFS同有向矩阵)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package graph

import "fmt"

/**
邻接矩阵无向图
*/
type MatrixUDG struct {
mVexs []string //顶点集合
mMatrix [][]int //矩阵
vexnum int // 顶点数
edgnum int // 边数
}

/**
通过已存在的图创建

*/
func NewExisting(vexs []string, edges [][]string) *MatrixUDG {
vexsLeng := len(vexs)
edgesLeng := len(edges)
m := &MatrixUDG{
mVexs: vexs,
vexnum: vexsLeng,
edgnum: edgesLeng,
}
// 初始化"顶点"
mVexs := make([]string, vexsLeng)
for i := 0; i < len(vexs); i++ {
mVexs[i] = vexs[i]
}
//初始化二维切片
row, column := vexsLeng, vexsLeng
for i := 0; i < row; i++ {
inline := make([]int, column)
m.mMatrix = append(m.mMatrix, inline)
}
for i := 0; i < edgesLeng; i++ {
// 读取边的起始顶点和结束顶点
p1 := m.getPosition(edges[i][0])
p2 := m.getPosition(edges[i][1])
m.mMatrix[p1][p2] = 1
m.mMatrix[p2][p1] = 1
}
// 初始化"边"

return m

}

func (m *MatrixUDG) getPosition(s string) int {
for i := 0; i < len(m.mVexs); i++ {
if m.mVexs[i] == s {
return i
}
}
return -1
}

/*
* 打印矩阵队列图
*/
func (m *MatrixUDG) Print() {
fmt.Println("Martix Graph:\n")
for i := 0; i < len(m.mVexs); i++ {
for j := 0; j < len(m.mVexs); j++ {
fmt.Printf("%d ", m.mMatrix[i][j])
}
fmt.Println()
}
}

有向矩阵图代码-完整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
package graph

import "fmt"

/**
邻接矩阵有向图
*/
type MatrixDG struct {
mVexs []string //顶点集合
mMatrix [][]int //矩阵
vexnum int // 顶点数
edgnum int // 边数
}

/**
通过已存在的图创建

*/
func NewExistingDG(vexs []string, edges [][]string) *MatrixDG {
vexsLeng := len(vexs)
edgesLeng := len(edges)
m := &MatrixDG{
mVexs: vexs,
vexnum: vexsLeng,
edgnum: edgesLeng,
}
// 初始化"顶点"
mVexs := make([]string, vexsLeng)
for i := 0; i < len(vexs); i++ {
mVexs[i] = vexs[i]
}
//初始化二维切片
row, column := vexsLeng, vexsLeng
for i := 0; i < row; i++ {
inline := make([]int, column)
m.mMatrix = append(m.mMatrix, inline)
}
for i := 0; i < edgesLeng; i++ {
// 读取边的起始顶点和结束顶点
p1 := m.getPosition(edges[i][0])
p2 := m.getPosition(edges[i][1])
m.mMatrix[p1][p2] = 1
}
// 初始化"边"

return m

}

func (m *MatrixDG) getPosition(s string) int {
for i := 0; i < len(m.mVexs); i++ {
if m.mVexs[i] == s {
return i
}
}
return -1
}

/*
* 打印矩阵队列图
*/
func (m *MatrixDG) Print() {
fmt.Println("Martix Graph:\n")
for i := 0; i < len(m.mVexs); i++ {
for j := 0; j < len(m.mVexs); j++ {
fmt.Printf("%d ", m.mMatrix[i][j])
}
fmt.Println()
}
}

/*
深度搜索入口
*/
func (m *MatrixDG) DFS() {
visited := make([]bool, len(m.mVexs)) // 顶点访问标记
// 初始化所有顶点都没有被访问
for i := 0; i < len(m.mVexs); i++ {
visited[i] = false
}
fmt.Println("矩阵有向图深度搜索start:")
for i := 0; i < len(m.mVexs); i++ {
if !visited[i] {
m.doDFS(i, visited)
}
}
fmt.Println("\n矩阵有向图深度搜索end")
}

/**
深度搜索的递归方法
*/
func (m *MatrixDG) doDFS(i int, visited []bool) {
visited[i] = true
fmt.Printf("%s->", m.mVexs[i])
//从该顶点的第一个边开始,一直到最后一个边,对处于边另一端的顶点调用DFS函数
for w := m.firstVertex(i); w >= 0; w = m.nextVertex(i, w) {
//如果该顶点的标记位false,证明未被访问,调用深度优先搜索函数
if !visited[w] {
m.doDFS(w, visited)
}
}
}

/*
* 返回顶点v的第一个邻接顶点的索引,失败则返回-1
*/
func (m *MatrixDG) firstVertex(v int) int {
if v < 0 || v > m.vexnum-1 {
return -1
}
//查找与数组下标为v的顶点之间有边的顶点,返回它在数组中的下标
for i := 0; i < m.vexnum; i++ {
if m.mMatrix[v][i] == 1 {
return i
}

}
return -1
}

/*
* 返回顶点v相对于w的下一个邻接顶点的索引,失败则返回-1
*/
func (m *MatrixDG) nextVertex(v int, w int) int {
if v < 0 || v > m.vexnum-1 || w < 0 || w > m.vexnum-1 {
return -1
}
//从前一个访问位置w的下一个位置开始,查找之间有边的顶点
for i := w + 1; i < m.vexnum; i++ {
if m.mMatrix[v][i] == 1 {
return i
}
}

return -1
}

/**
广度优先搜索(类似于树的层次遍历)
*/
func (m *MatrixDG) BFS() {
head, rear := 0, 0
queue := make([]int, m.vexnum) // 辅组队列
visited := make([]bool, m.vexnum) //顶点访问标记
for i := 0; i < m.vexnum; i++ {
visited[i] = false
}
fmt.Printf("矩阵有向图广度搜索start:")
for i := 0; i < m.vexnum; i++ {
if !visited[i] {
visited[i] = true
fmt.Printf("%s", m.mVexs[i])

queue[rear] = i // 入队列
rear = rear + 1
}
for head != rear {
head = head + 1
j := queue[head] // 出队列

for k := m.firstVertex(j); k >= 0; k = m.nextVertex(j, k) { //k是为访问的邻接顶点
if !visited[k] {
visited[k] = true
fmt.Printf("%s", m.mVexs[k])
queue[rear] = k
rear = rear + 1
}
}

}

}

fmt.Printf("矩阵有向图广度搜索end")

}

无向链表图代码(DFS-BFS同有向链表)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
package graph

import "fmt"

/**
邻接链表无向图
*/
type ListUDG struct {
mVexs []VNode // 顶点数组
eNode *ENode
vNode *VNode
}

//邻接表中表对应的链表的顶点
type ENode struct {
ives int // 该边所指向的顶点的位置
nextEdge *ENode // 指向下一条弧的指针
}

// 邻接表中表的顶点
type VNode struct {
data string // 顶点信息
firstEdge *ENode // 指向第一条依附该顶点的弧
}

/*
* 创建图(用已提供的矩阵)
*
* 参数说明:
* vexs -- 顶点数组
* edges -- 边数组
*/
func NewListUDG(vexs []string, edges [][]string) *ListUDG {

// 初始化"顶点数"和"边数"
vlen := len(vexs)
elen := len(edges)
mVes := make([]VNode, vlen)
m := &ListUDG{mVexs: mVes}
for i := 0; i < vlen; i++ {
mm := &VNode{data: vexs[i], firstEdge: nil}
mVes[i] = *mm
}
//初始化边
for i := 0; i < elen; i++ {
// 读取边的起始顶点和结束顶点
p1 := m.getPosition(edges[i][0])
p2 := m.getPosition(edges[i][1])
// 初始化node1
node1 := &ENode{ives: p2}
// 将node1链接到"p1所在链表的末尾"
if mVes[p1].firstEdge == nil {
mVes[p1].firstEdge = node1
} else {
m.linkLast(mVes[p1].firstEdge, node1)
}
// 初始化node2
node2 := &ENode{ives: p1}
// 将node1链接到"p1所在链表的末尾"
if mVes[p2].firstEdge == nil {
mVes[p2].firstEdge = node2
} else {
m.linkLast(mVes[p2].firstEdge, node2)
}

}

return m

}

func (m *ListUDG) getPosition(s string) int {
for i := 0; i < len(m.mVexs); i++ {
if m.mVexs[i].data == s {
return i
}
}
return -1
}

func (m *ListUDG) linkLast(list *ENode, node *ENode) {
p := list
for p.nextEdge != nil {
p = p.nextEdge
}
p.nextEdge = node
}

func (m *ListUDG) Print() {
/*
* 打印矩阵队列图
*/
fmt.Printf("List Graph:\n")
for i := 0; i < len(m.mVexs); i++ {
fmt.Printf("%d(%s): ", i, m.mVexs[i].data)
node := m.mVexs[i].firstEdge
for node != nil {
fmt.Printf("%d(%s) ", node.ives, m.mVexs[node.ives].data)
node = node.nextEdge
}
fmt.Printf("\n")
}
}

有向链表图代码-完整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
package graph

import "fmt"

/**
邻接链表无向图
*/
type ListDG struct {
mVexs []VNode // 顶点数组
eNode *ENode
vNode *VNode
}

//邻接表中表对应的链表的顶点
type ENode struct {
ives int // 该边所指向的顶点的位置
nextEdge *ENode // 指向下一条弧的指针
}

// 邻接表中表的顶点
type VNode struct {
data string // 顶点信息
firstEdge *ENode // 指向第一条依附该顶点的弧
}

/*
* 创建图(用已提供的矩阵)
*
* 参数说明:
* vexs -- 顶点数组
* edges -- 边数组
*/
func NewListDG(vexs []string, edges [][]string) *ListDG {

// 初始化"顶点数"和"边数"
vlen := len(vexs)
elen := len(edges)
mVes := make([]VNode, vlen)
m := &ListDG{mVexs: mVes}
for i := 0; i < vlen; i++ {
mm := &VNode{data: vexs[i], firstEdge: nil}
mVes[i] = *mm
}
//初始化边
for i := 0; i < elen; i++ {
// 读取边的起始顶点和结束顶点
//c1 := edges[i][0]
//c2 := edges[i][1]
// 读取边的起始顶点和结束顶点
p1 := m.getPosition(edges[i][0])
p2 := m.getPosition(edges[i][1])
// 初始化node1
node1 := &ENode{ives: p2}
// 将node1链接到"p1所在链表的末尾"
if mVes[p1].firstEdge == nil {
mVes[p1].firstEdge = node1
} else {
m.linkLast(mVes[p1].firstEdge, node1)
}

}

return m

}

func (m *ListDG) getPosition(s string) int {
for i := 0; i < len(m.mVexs); i++ {
if m.mVexs[i].data == s {
return i
}
}
return -1
}

func (m *ListDG) linkLast(list *ENode, node *ENode) {
p := list

for p.nextEdge != nil {
p = p.nextEdge
p.nextEdge = node
}
}

func (m *ListDG) Print() {
/*
* 打印矩阵队列图
*/
fmt.Printf("List Graph:\n")
for i := 0; i < len(m.mVexs); i++ {
fmt.Printf("%d(%s): ", i, m.mVexs[i].data)
node := m.mVexs[i].firstEdge
for node != nil {
fmt.Printf("%d(%s) ", node.ives, m.mVexs[node.ives].data)
node = node.nextEdge
}
fmt.Printf("\n")
}
}

/*
* 深度优先搜索遍历图的递归实现
*/
func (m *ListDG) doDFS(i int, visited []bool) {
var node *ENode
visited[i] = true
fmt.Printf("%s ", m.mVexs[i].data)
node = m.mVexs[i].firstEdge
for node != nil {
if (!visited[node.ives]) {
m.doDFS(node.ives, visited)
}
node = node.nextEdge
}
}

/*
* 深度优先搜索遍历图
*/
func (m *ListDG) DFS() {
visited := make([]bool, len(m.mVexs))
// 初始化所有顶点都没有被访问
for i := 0; i < len(m.mVexs); i++ {
visited[i] = false
fmt.Printf("DFS: ")
for i := 0; i < len(m.mVexs); i++ {
if (!visited[i]) {
m.doDFS(i, visited)
}

}
fmt.Printf("\n")
}
}

/*
* 广度优先搜索(类似于树的层次遍历)
*/
func (m *ListDG) BFS() {
head, rear := 0, 0
queue := make([]int, len(m.mVexs)) // 辅组队列
visited := make([]bool, len(m.mVexs)) // 顶点访问标记

for i := 0; i < len(m.mVexs); i++ {
visited[i] = false
}

fmt.Printf("BFS: ")
for i := 0; i < len(m.mVexs); i++ {
if !visited[i] {
visited[i] = true
fmt.Printf("%s ", m.mVexs[i].data)
rear++
queue[rear] = i // 入队列
}

for head != rear {
head++
j := queue[head] // 出队列
node := m.mVexs[j].firstEdge
for node != nil {
k := node.ives
if !visited[k] {
visited[k] = true;
fmt.Printf("%s ", m.mVexs[k].data)
rear++
queue[rear] = k
}
node = node.nextEdge
}
}
}
fmt.Printf("\n")
}

评论系统未开启,无法评论!