扫码订阅《 Go语言算法与数据结构》或入驻星球,即可阅读文章!

GOLANG ROADMAP

阅读模式

  • 沉浸
  • 自动
  • 日常
首页
Go学习
  • Go学院

    • Go小课
    • Go小考
    • Go实战
    • 精品课
  • Go宝典

    • 在线宝典
    • B站精选
    • 推荐图书
    • 精品博文
  • Go开源

    • Go仓库
    • Go月刊
  • Go下载

    • 视频资源
    • 文档资源
Go求职
  • 求职服务

    • 内推互助
    • 求职助力
  • 求职刷题

    • 企业题库
    • 面试宝典
    • 求职面经
Go友会
  • 城市
  • 校园
推广返利 🤑
实验区
  • Go周边
消息
更多
  • 用户中心

    • 我的信息
    • 推广返利
  • 玩转星球

    • 星球介绍
    • 角色体系
    • 星主权益
  • 支持与服务

    • 联系星主
    • 成长记录
    • 常见问题
    • 吐槽专区
  • 合作交流

    • 渠道合作
    • 课程入驻
    • 友情链接
author-avatar

GOLANG ROADMAP


首页
Go学习
  • Go学院

    • Go小课
    • Go小考
    • Go实战
    • 精品课
  • Go宝典

    • 在线宝典
    • B站精选
    • 推荐图书
    • 精品博文
  • Go开源

    • Go仓库
    • Go月刊
  • Go下载

    • 视频资源
    • 文档资源
Go求职
  • 求职服务

    • 内推互助
    • 求职助力
  • 求职刷题

    • 企业题库
    • 面试宝典
    • 求职面经
Go友会
  • 城市
  • 校园
推广返利 🤑
实验区
  • Go周边
消息
更多
  • 用户中心

    • 我的信息
    • 推广返利
  • 玩转星球

    • 星球介绍
    • 角色体系
    • 星主权益
  • 支持与服务

    • 联系星主
    • 成长记录
    • 常见问题
    • 吐槽专区
  • 合作交流

    • 渠道合作
    • 课程入驻
    • 友情链接
  • 课程介绍

    • 《Go语言算法与数据结构》
  • 算法

    • 快速排序算法
    • 堆排序算法
    • 冒泡排序算法
    • 二分查找方法
    • 选择排序算法
    • 基数排序算法
    • 拓扑排序
    • 插入排序算法
    • 字符串匹配
    • 二叉搜索树
  • 数据结构

    • 图
    • 散列表
    • 堆
    • 链表
    • 跳跃表
    • 字典树

扫码订阅《 Go语言算法与数据结构》或入驻星球,即可阅读文章!

图


GOLANG ROADMAP

# 图

  • 相对于树来说更复杂的非线性数据结构

# 图分类

  • 无向图
    • 表示顶点到顶点没有方向
  • 有向图
    • 表示顶点到顶点有方向
      • 入度:有多少个顶点进入
      • 出度:有多少个顶点出去
      • 六度分割理论
  • 带权图
    • 表示顶点到顶点有权重

# 图的存储方式

  • 邻接矩阵:
    • 缺点:对于无向图来说,用邻接矩阵存储是浪费空间的,因为邻接矩阵是对称的,并且对于大量顶点需要跟多的空间来存储
    • 优点:直观,并且可以利用矩阵计算,求最短路径
  • 邻接表:
  • 如何实现微博的关注关系
    • 用邻接表来实现用户的关注的人
      • 类似链表链表对缓存不友好,可以通过其他方式优化比如hash,跳表,红黑二叉树等来实现快速查询,B+树
      • 可以通过其他存储方式落地,比如mysql建立表。
    • 用逆邻接表来实现用户的粉丝
  • 搜索
    • 广度搜索:地毯式搜索
    • 深度搜索:深度优先式搜索
package main

import "fmt"

//无向图
type graph struct {
    vertex int
    list   map[int][]int
    found  bool
}

func main() {
    g := NewGraph(8)
    g.addVertex(1, 2)
    g.addVertex(1, 4)
    g.addVertex(2, 3)
    g.addVertex(2, 5)
    g.addVertex(4, 5)
    g.addVertex(3, 6)
    g.addVertex(5, 6)
    g.addVertex(5, 7)
    g.addVertex(6, 8)
    g.addVertex(7, 8)
    g.bfs(1, 7)
}

//创建图
func NewGraph(v int) *graph {
    g := new(graph)
    g.vertex = v
    g.found = false
    g.list = map[int][]int{}
    i := 0
    for i < v {
        g.list[i] = make([]int, 0)
        i++
    }
    return g
}

//添加边
func (g *graph) addVertex(t int, s int) {
    g.list[t] = push(g.list[t], s)
    g.list[s] = push(g.list[s], t)
}

//取出切片第一个
func pop(list []int) (int, []int) {
    if len(list) > 0 {
        a := list[0]
        b := list[1:]
        return a, b
    } else {
        return -1, list
    }
}

//推入切片
func push(list []int, value int) []int {
    result := append(list, value)
    return result
}

//广度优先搜索
func (g *graph) bfs(s int, t int) {
    if s == t {
        return
    }
    visited := make([]bool, g.vertex+1)
    var queue []int
    queue = append(queue, s)
    prev := make([]int, g.vertex+1)
    i := 0
    for i < len(prev) {
        prev[i] = -1
        i++
    }
    for len(queue) != 0 {
        var w int
        w, queue = pop(queue)
        for j := 0; j < len(g.list[w]); j++ {
            q := g.list[w][j]
            fmt.Println(q)
            if !visited[q] {
                prev[q] = w
                if q == t {
                    fmt.Println(prev)
                    printPath(prev, s, t)
                    return
                }
                visited[q] = true
                queue = append(queue, q)
            }
        }
    }
}

//深度优先搜索
func (g *graph) dfs(s int, t int) {
    prev := make([]int, g.vertex+1)
    for i := 0; i < len(prev); i++ {
        prev[i] = -1
    }
    visit := make([]bool, g.vertex+1)
    g.recurDsf(s, t, prev, visit)
    fmt.Println(prev)
    printPath(prev, s, t)
}

func (g *graph) recurDsf(w int, t int, prev []int, visited []bool) {
    if g.found {
        return
    }
    if w == t {
        g.found = true
        return
    }
    visited[w] = true
    for i := 0; i < len(g.list[w]); i++ {
        q := g.list[w][i]
        if !visited[q] {
            prev[q] = w
            g.recurDsf(g.list[w][i], t, prev, visited)
        }
    }
}

//深度优先搜做
func printPath(prev []int, s int, t int) {
    if prev[t] != -1 && s != t {
        printPath(prev, s, prev[t])
    }
    fmt.Println(t, "  ")
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
  • 图
  • 图分类
  • 图的存储方式