map.go

package data_struct

import (
    "fmt"
)

//数据结构，图 的存储和遍历， 1，邻接矩阵
//图的概念：顶点，有向图（弧（弧头，弧尾），权值），无向图（边，权值）
/* 图示
        A
       / 
      B   D
     /  / 
    C  F G-H
     /
     E
矩阵示例
  A B C D E F G H
A 0 1 0 1 0 0 0 0
B 1 0 1 0 0 1 0 0
C 0 1 0 0 1 0 0 0
D 1 0 0 0 0 0 1 1
E 0 0 1 0 0 1 0 0
F 0 1 0 0 1 0 0 0
G 0 0 0 1 0 0 0 1
H 0 0 0 1 0 0 1 0
*/
type MNode struct {
    Data      interface{} //顶点数据
    isVisited bool        //是否被访问过
}
type MMap struct {
    Capacity  int     //最多容纳的顶点个数
    nodeCount int     //已添加顶点数
    nodeArray []MNode //顶点数组
    matrix    []int   //邻接矩阵的数组
}

//初始化一个图
func MakeMap(size int) MMap {
    m := MMap{
        Capacity: size,
    }
    m.nodeArray = make([]MNode, size)
    m.matrix = make([]int, size*size)
    return m
}

//添加节点
func (t *MMap) AddNode(node MNode) bool {
    t.nodeArray[t.nodeCount].Data = node.Data
    t.nodeCount++
    return true
}

//重置节点状态为未访问
func (t *MMap) ResetNode() {
    for i := t.nodeCount - 1; i >= 0; i-- {
        t.nodeArray[i].isVisited = false
    }
}

//为有向图设置邻接矩阵
func (t *MMap) SetValutToMatrix2DirectedGraph(row int, col int, val int) bool {
    if row = t.Capacity || col  t.Capacity {
        return false
    }
    t.matrix[row*t.Capacity+col] = val
    return true
}

//为无向图设置邻接矩阵. （双向，对角线对称）
func (t *MMap) SetValutToMatrix2UnDirectedGraph(row int, col int, val int) bool {
    if row = t.Capacity || col  t.Capacity {
        return false
    }
    t.matrix[row*t.Capacity+col] = val
    t.matrix[col*t.Capacity+row] = val
    return true
}

//从邻接矩阵中取值
func (t *MMap) getMatrixValue(row int, col int) int {
    return t.matrix[row*t.Capacity+col]
}

//深度优先访问。给一个节点，向一个方向一直向下遍历，直到没有下一个点，或形成回环。再向另一个方向继续
// ABCEFDGH
func (t *MMap) DepthTraverse(nodeIndex int) {
    node := &(t.nodeArray[nodeIndex])
    node.isVisited = true

    fmt.Print(node.Data)
    for i := 0; i  0 {
            breadthHelp(currIndexs)
        }
    }
    breadthHelp([]int{nodeIndex})
}

//打印邻接矩阵
func (t *MMap) PrintMatrix(helper bool) {
    if helper {
        fmt.Print("  ")
        for i := 0; i 

map_test.go

package data_struct

import (
    "fmt"
    "testing"
)

func getMMap() MMap {
    size := 8
    m := MakeMap(size)
    for i := 65; i