无向图存储之邻接矩阵实现-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)
}