无向图存储之邻接矩阵实现-Golang版本

实现一个无向图存储使用邻接矩阵的方式实现,实现语言Golang。

什么是邻接矩阵存储方式 ?

邻接矩阵存储通过一个一维数组,以及一个二维数组完成图的构建。一维数组用于存储图中的每一个顶点,二维数组用于存储图中边或弧的信息。

下图是文章后面将要使用邻接矩阵存储方式实现的图

图

顶点数组为

{'A', 'B', 'C', 'D'}

边数组(二维数组)是个矩阵形式

 // A B C D
 //A [65536 5 3 6 ]
 //B [ 5 65536 7 65536]
 //C [ 3 7 65536 9 ]
 //D [ 6 65536 9 65536]

一维数组存储每一个顶点,而二维数组以矩阵的形式展现出来就是上面的那个矩阵。 比如第1行第2列,为array[0][1] = 5
表示的就是A到B的边,且该边的权值为5。而因为是无向图,则该矩阵其实是个对称矩阵。另外矩阵中的65536其实就是一个不可能取到的一个权值,因为权值有可能出现为0的情况,所以要用一个绝对不可能是权值的值来作为一个不可能的取值。比如array[0][0] = 65536 即代表A到A的边不存在。

接下来是代码实现

package main
import "fmt"
type VertexType rune // 顶点数值类型
const (
 INFINITY int32 = 65536 // 不可能值
)
//无向图
type AdjacencyMatrix struct {
 Vers []VertexType
 Edges [][]int32
 NumEdges int32
 NumVers int32
}
//用于记录每一条边的两个顶点和权值
type edgeWeightInfo struct {
 v0 int32
 v1 int32
 weight int32
}
//初始化邻接矩阵
//versC 顶点个数
//vers代表顶点集合
//ewi 代表邻接矩阵的每一条边
func (this *AdjacencyMatrix) Init(versC int32, vers []VertexType, ewis []edgeWeightInfo) {
 this.Edges = make([][]int32, versC)
 for i := 0; i < len(this.Edges); i++ {
 this.Edges[i] = make([]int32, versC)
 for index, _ := range this.Edges[i] {
 this.Edges[i][index] = INFINITY //一开始全部初始化为不可能值
 }
 }
 this.Vers = vers
 for _, ewi := range ewis {
 this.Edges[ewi.v0][ewi.v1] = ewi.weight
 //因为是无向图所以是对称矩阵
 this.Edges[ewi.v1][ewi.v0] = ewi.weight
 }
 fmt.Println(this.Edges)
 // A B C D
 //A [65536 5 3 6 ]
 //B [ 5 65536 7 65536]
 //C [ 3 7 65536 9 ]
 //D [ 6 65536 9 65536]
}
func main() {
 var am *AdjacencyMatrix = new(AdjacencyMatrix)
 var vers []VertexType = []VertexType{'A', 'B', 'C', 'D'}
 var ewis []edgeWeightInfo = []edgeWeightInfo{
 edgeWeightInfo{0, 1, 5},
 edgeWeightInfo{0, 2, 3},
 edgeWeightInfo{0, 3, 6},
 edgeWeightInfo{1, 2, 7},
 edgeWeightInfo{2, 3, 9},
 }
 am.Init(4, vers, ewis)
}

有疑问加站长微信联系(非本文作者)

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
• 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传