```go
package main
import (
"container/list"
"fmt"
)
const MAX_SIZE int = 5
//为了看上去 好一些
const MAX_VALUE int = 9
func main() {
fmt.Println("Prim")
var gg Graph
var vexs = []string{"B", "A", "C", "D", "E"}
gg.vexnum = 5
gg.vexs = vexs
for i := 0; i < len(vexs); i++ {
for j := 0; j < len(vexs); j++ {
gg.matrix[i][j] = MAX_VALUE
}
}
initGG(&gg)
fmt.Println(gg.vexs)
fBFS(&gg)
fDFS(&gg)
//listgg := list.New()
prim(&gg, 0)
PrintG(gg, len(vexs))
}
func PrintG(gg Graph, l int) {
for i := 0; i < l; i++ {
fmt.Println(gg.matrix[i])
}
}
type Graph struct {
vexs []string //定点集合
vexnum int //定点数量
edgnum int //边数量
matrix [MAX_SIZE][MAX_SIZE]int //邻接矩阵
}
func initGG(gg *Graph) {
gg.matrix[0][1] = 5
gg.matrix[0][2] = 3
gg.matrix[1][0] = 5
gg.matrix[1][3] = 7
gg.matrix[1][4] = 4
gg.matrix[2][0] = 3
gg.matrix[2][3] = 6
gg.matrix[3][1] = 7
gg.matrix[3][2] = 6
gg.matrix[3][4] = 1
gg.matrix[4][1] = 4
gg.matrix[4][3] = 1
gg.edgnum = 12 / 2
}
//深度遍历
func DFS(gg *Graph, visit *[]bool, i int) {
fmt.Println(gg.vexs[i])
for j := 0; j < gg.vexnum; j++ {
if gg.matrix[i][j] != MAX_VALUE && !(*visit)[j] {
(*visit)[j] = true
DFS(gg, visit, j)
}
}
}
func fDFS(gg *Graph) {
visit := make([]bool, 10, 10)
fmt.Println(visit)
visit[0] = true
DFS(gg, &visit, 0)
}
//广度遍历
func fBFS(gg *Graph) {
listq := list.New()
visit := make([]bool, 10, 10)
//first push
visit[0] = true
listq.PushBack(0)
for listq.Len() > 0 {
index := listq.Front()
fmt.Println(gg.vexs[index.Value.(int)])
for i := 0; i < gg.vexnum; i++ {
if !visit[i] && gg.matrix[index.Value.(int)][i] != MAX_VALUE {
visit[i] = true
listq.PushBack(i)
}
}
listq.Remove(index)
}
}
func prim(gg *Graph, start int) {
index := 0
sum := 0
prims := make([]string, 10, 10)
var weights [5][2]int //[[0 0] [0 5] [0 3] [0 9] [0 9]]
prims[index] = gg.vexs[start]
index++
//next vex
for i := 0; i < gg.vexnum; i++ {
weights[i][0] = start //k
weights[i][1] = gg.matrix[start][i] //v
}
//delete vex
weights[start][1] = 0
for i := 0; i < gg.vexnum; i++ {
//fmt.Println(weights)
if start == i {
continue
}
min := MAX_VALUE
next := 0
for j := 0; j < gg.vexnum; j++ {
if weights[j][1] != 0 && weights[j][1] < min {
min = weights[j][1]
next = j
}
}
fmt.Println(gg.vexs[weights[next][0]], gg.vexs[next], "权重", weights[next][1])
sum += weights[next][1]
prims[index] = gg.vexs[next]
index++
//delete vex
weights[next][1] = 0
//update
for j := 0; j < gg.vexnum; j++ {
if weights[j][1] != 0 && gg.matrix[next][j] < weights[j][1] {
weights[j][1] = gg.matrix[next][j]
weights[j][0] = next
}
}
}
fmt.Println("sum:", sum)
fmt.Println(prims)
}
func get_position(gg *Graph, ch string) int {
for i := 0; i < gg.vexnum; i++ {
if gg.vexs[i] == ch {
return i
}
}
return -1
}
```
所有代码地址
https://github.com/godla/golang-sort-data-structures-study.git
每天撸一点gopher
有疑问加站长微信联系（非本文作者）
