上一篇《（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欢迎指出，转载请注明出处。
