（27）Go邻接矩阵和邻接表实现无权图

上一篇《（26）Go-什么是图，图怎么实现？》后续：https://www.jianshu.com/p/e373ded1fd97

邻接矩阵实现无权图 //
// 稠密图 - 邻接矩阵
type denseGraph struct {
    n        int  //节点数
    m        int  //边数
    directed bool //有向图 or 无向图
    graph    [][]bool
}

// 构造函数:有n个顶点,有向 or 无向图
func NewDenseGraph(n int, directed bool) *denseGraph {
    // 初始化 n*n 的二维切片矩阵
    buf := make([][]bool, n)
    for i := 0; i < n; i++ {
        buf[i] = make([]bool, n)
    }
    return &denseGraph{
        n:        n,
        m:        0,
        directed: directed,
        graph:    buf,
    }
}

// 获取顶点数量
func (d denseGraph) GetVertex() int {
    return d.n
}

// 获取边数量
func (d denseGraph) GetEdge() int {
    return d.m
}

// 添加边: v1,v2均表示顶点相应的索引
func (d *denseGraph) AddEdge(v1, v2 int) error {
    b, err := d.HasEdge(v1, v2)
    if err != nil {
        return err
    }

    // 不要平行边
    if !b {
        // 表示v1 -> v2有条边
        d.graph[v1][v2] = true
        if !d.directed {
            // 如果是无向图,v2 -> v1也要表示有边
            d.graph[v2][v1] = true
        }

        d.m++
    }
    return nil
}

// 判断v1,v2是否已经有边
func (d *denseGraph) HasEdge(v1, v2 int) (bool, error) {
    // 判断索引是否越界
    if v1 < 0 || v2 < 0 || v1 >= d.n || v2 >= d.n {
        return false, errors.New("index is illegal.")
    }

    return d.graph[v1][v2], nil
}

// 迭代器: 输出节点v所连接的节点,时间复杂度为O(n)
func (d *denseGraph) Iterator(v int) []int {
    // 判断索引是否越界
    if v < 0 || v >= d.n {
        fmt.Println("index is illegal.")
        return nil
    }

    buf := []int{}
    for i, j := range d.graph[v] {
        if j {
            buf = append(buf, i)
        }
    }
    return buf
}

邻接表实现无权图 
// 稀疏图 - 邻接表
type sparseGraph struct {
    n        int  // 节点数
    m        int  // 边数量
    directed bool //有向 or 无向图
    graph    [][]int
}

func NewSparseGraph(n int, directed bool) *sparseGraph {
    buf := make([][]int, n)

    return &sparseGraph{
        n:        n,
        m:        0,
        directed: directed,
        graph:    buf,
    }
}

// 获取顶点数量
func (s *sparseGraph) GetVertex() int {
    return s.n
}

// 获取边数量
func (s *sparseGraph) GetEdge() int {
    return s.m
}

// 添加边: v1,v2表示顶点相应的索引
func (s *sparseGraph) AddEdge(v1, v2 int) error {
    // 判断索引是否越界
    if v1 < 0 || v2 < 0 || v1 >= s.n || v2 >= s.n {
        return errors.New("index is illegal.")
    }

    // 没有处理平行边的情况
    s.graph[v1] = append(s.graph[v1], v2)
    if v1 != v2 && !s.directed {
        s.graph[v2] = append(s.graph[v2], v1)
    }
    s.m++
    return nil
}

// 判断v1,v2是否已经有边
func (s *sparseGraph) HasEdge(v1, v2 int) (bool, error) {
    // 判断索引是否越界
    if v1 < 0 || v2 < 0 || v1 >= s.n || v2 >= s.n {
        return false, errors.New("index is illegal.")
    }

    for i := 0; i < len(s.graph[v1]); i++ {
        if s.graph[v1][i] == v2 {
            return true, nil
        }
    }
    return false, nil
}

// 迭代器: 输出节点v所连接的节点,时间复杂度为O(1)
func (s *sparseGraph) Iterator(v int) []int {
    // 判断索引是否越界
    if v < 0 || v >= s.n {
        fmt.Println("index is illegal.")
        return nil
    }
    return s.graph[v]
}

测试代码
func s_Test() {
    rand.Seed(time.Now().UnixNano())
    s := sparseGraph1.NewSparseGraph(10, false)
    for i := 0; i < 50; i++ {
        s.AddEdge(rand.Intn(10), rand.Intn(10))
    }

    for i := 0; i < 10; i++ {
        fmt.Println(i, ": ", s.Iterator(i))
    }
}

func d_Test() {
    rand.Seed(time.Now().UnixNano())
    d := graph1.NewDenseGraph(10, false)
    for i := 0; i < 50; i++ {
        d.AddEdge(rand.Intn(10), rand.Intn(10))
    }

    for i := 0; i < 10; i++ {
        fmt.Println(i, ": ", d.Iterator(i))
    }
}

func main() {
    fmt.Println("邻接表图")
    s_Test()
    fmt.Println("========")
    fmt.Println("邻接矩阵图")
    d_Test()
}

测试结果 //
邻接表图
0 :  [6 7 2 8 5 0 5 6 0]
1 :  [2 2 4 4 7 1 3 3 6 9]
2 :  [1 1 5 8 0 2 4 2 9 4 4 3 5 6]
3 :  [4 5 6 1 5 2 1]
4 :  [3 1 8 1 9 2 2 2 4]
5 :  [2 7 3 9 5 6 3 0 2 0 8]
6 :  [0 7 3 7 8 5 2 0 1 7]
7 :  [6 0 5 1 6 9 6]
8 :  [4 8 2 8 0 6 5]
9 :  [5 9 4 7 2 1]
========
邻接矩阵图
0 :  [1 2 3 4 5 6 7 8 9]
1 :  [0 2 3 4 5 8]
2 :  [0 1 3 5 6 8]
3 :  [0 1 2 3 5 8 9]
4 :  [0 1 5 6 7 9]
5 :  [0 1 2 3 4 6 7 8 9]
6 :  [0 2 4 5 6 8 9]
7 :  [0 4 5 7 9]
8 :  [0 1 2 3 5 6]
9 :  [0 3 4 5 6 7]

接下一篇《（28）Go邻接矩阵和邻接表实现有权图》：
https://www.jianshu.com/p/7d3f0bbbc83c

有bug欢迎指出，转载请注明出处。