（28）Go邻接矩阵和邻接表实现有权图

继上一篇《（27）Go实现邻接矩阵和邻接表无权图》后续：
https://www.jianshu.com/p/ad9fed1836d9

邻接矩阵实现有权图
// 边类
type Edge struct {
    a      int     //a节点
    b      int     //b节点
    weight float64 //权值
}

func newEdge(a, b int, weight float64) *Edge {
    return &Edge{
        a:      a,
        b:      b,
        weight: weight,
    }
}

// 比较两个边的权值
func lessWeight(a, b *Edge) bool {
    return a.weight <= b.weight
}

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

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

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

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

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

    // 包含两种情况:有边则覆盖原先的边,无边则新添加边
    d.graph[v1][v2] = newEdge(v1, v2, weight)
    if !d.directed {
        // 如果是无向图,v2 -> v1也要表示有边
        d.graph[v2][v1] = newEdge(v2, v1, weight)
    }
    // 如果本来没有边,边数量+1
    if !b {
        d.m++
    }
    return nil
}

// 判断v1,v2是否已经有边
func (d *weightedDenseGraph) 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, nil
}

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

    var buf []*Edge
    for _, j := range d.graph[v] {
        if j != nil {
            buf = append(buf, j)
        }
    }
    return buf
}

// 打印边
func PrintEdge(e []*Edge) {
    buf := make([]Edge, len(e))
    for i1, i2 := range e {
        if i2 != nil {
            buf[i1] = *i2
        }
    }
    fmt.Println(buf)
}

邻接表实现有权图
// 边类
type Edge struct {
    a      int     //a节点
    b      int     //b节点
    weight float64 //权值
}

func newEdge(a, b int, weight float64) *Edge {
    return &Edge{
        a:      a,
        b:      b,
        weight: weight,
    }
}

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

func NewWeightSparseGraph(n int, directed bool) *sparseGraph {
    buf := make([][]*Edge, 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, weight float64) 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], newEdge(v1, v2, weight))
    if v1 != v2 && !s.directed {
        s.graph[v2] = append(s.graph[v2], newEdge(v2, v1, weight))
    }
    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 _, v := range s.graph[v1] {
        if v.b == v2 {
            return true, nil
        }
    }
    return false, nil
}

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

func PrintEdge(e []*Edge) {
    buf := []Edge{}
    for _, i2 := range e {
        buf = append(buf, *i2)
    }
    fmt.Println(buf)
}

测试
func d_Test() {
    rand.Seed(time.Now().UnixNano())

    d := weightDenseGraph.NewWeightDenseGraph(10, false)
    for i := 0; i < 20; i++ {
        d.AddEdge(rand.Intn(10), rand.Intn(10), 0)
    }

    for i := 0; i < 10; i++ {
        a := d.Iterator(i)
        weightDenseGraph.PrintEdge(a)
    }
}

func s_Test() {
    rand.Seed(time.Now().UnixNano())

    d := weightSparseGraph1.NewWeightSparseGraph(10, false)
    for i := 0; i < 20; i++ {
        d.AddEdge(rand.Intn(10), rand.Intn(10), 0)
    }

    for i := 0; i < 10; i++ {
        a := d.Iterator(i)
        weightSparseGraph1.PrintEdge(a)
    }
}
func main() {
    fmt.Println("邻接表有权图")
    s_Test()
    fmt.Println("========")
    fmt.Println("邻接矩阵无权图")
    d_Test()
}

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

总结：邻接矩阵有序，邻接表无序，邻接矩阵遍历时间复杂度O(n)，邻接表遍时间复杂度O(1) //

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