# Golang通过邻接表实现有向图

Bryce · · 2367 次点击 · · 开始浏览

《数学之美》第九章——《图论和网络爬虫》，就浅显易懂的介绍了图的实际用途。搜索引擎里面的网络爬虫抓取网络数据，就是把互联网抽象成有向图这种数据结构，通过遍历这张图实现的互联网抓取。

``````type Graph struct {
edgnum int
vexnum int
}

type Vertex struct {
Data string
e    *Edge
}

type Edge struct {
ivex int
next *Edge
}
``````

``````func (this *Graph) InsertVertex(v Vertex) {
}
``````

``````func (this *Graph) InsertEdge(v1, v2 Vertex) {
if p == nil {
// fmt.Println("nil...", v1.Data, v2.Data)
} else {
for ; p.next != nil; p = p.next {
}
p.next = NewEdge(this.get_position(v2.Data))
// fmt.Println("append...", v1.Data, v2.Data)
}
}
``````

``````func (this *Graph) Adjacent(v Vertex) []Vertex {
res := make([]Vertex, 0)
for ; p != nil; p = p.next {
}
return res
}

func (this *Graph) OutDegree(v Vertex) int {
res := 0
for p != nil {
res++
p = p.next
}
return res
}
``````

``````func (this *Graph) InDegree(v Vertex) int {
res := 0
pos := this.get_position(v.Data)
for _, a := range this.adj {
p := a.e
for p != nil {
if pos == p.ivex {
res++
}
p = p.next
}
}
return res
}
``````

``````func (this *Graph) Bfs() {
res := map[int]Vertex{}
for _, a := range this.adj {
Q := []Vertex{a}
for len(Q) != 0 {
u := Q[0]
Q = Q[1:]
if _, ok := res[this.get_position(u.Data)]; !ok {
res[this.get_position(u.Data)] = u
fmt.Printf("%s ", u.Data)
}
}
}
fmt.Printf("\n")
}
``````

``````func (this *Graph) Dfs() {
res := map[int]Vertex{}
for _, a := range this.adj {
this.dfs(a, res)
}
fmt.Printf("\n")
}

func (this *Graph) dfs(u Vertex, res map[int]Vertex) {
if _, ok := res[this.get_position(u.Data)]; !ok {
res[this.get_position(u.Data)] = u
fmt.Printf("%s ", u.Data)
p := u.e
for p != nil {
if _, ok := res[p.ivex]; !ok {
}
p = p.next
}
}
}
``````

``````func TestMain(t *testing.T) {
g := create_example_lgraph()
g.Print()
println("Bfs.............")
g.Bfs()
println("Dfs.............")
g.Dfs()
if g.InDegree(Vertex{Data: "E"}) != 2 {
t.Error("indegree of E wanted 2 bug got", g.InDegree(Vertex{Data: "E"}))
}
if g.OutDegree(Vertex{Data: "E"}) != 2 {
t.Error("outdegree of E wanted 2 bug got", g.OutDegree(Vertex{Data: "E"}))
}
}

func create_example_lgraph() *Graph {
vexs := []string{"A", "B", "C", "D", "E", "F", "G"}
edges := [][2]string{
{"A", "B"},
{"B", "C"},
{"B", "E"},
{"B", "F"},
{"C", "E"},
{"D", "C"},
{"E", "B"},
{"E", "D"},
{"F", "G"}}
vlen := len(vexs)
elen := len(edges)

pG := Create()
// 初始化"顶点数"和"边数"
pG.vexnum = vlen
pG.edgnum = elen
// 初始化"邻接表"的顶点
for i := 0; i < pG.vexnum; i++ {
pG.InsertVertex(*NewVertex(vexs[i]))
}
// 初始化"邻接表"的边
for i := 0; i < pG.edgnum; i++ {
// 读取边的起始顶点和结束顶点
pG.InsertEdge(*NewVertex(edges[i][0]), *NewVertex(edges[i][1]))
}
return pG
}
``````

######参考文献 + 【1】wangkuiwu/datastructs_and_algorithm - GitHub + 【2】《数据结构与算法——C语言描述》，Mark Allen Weiss著 + 【3】《算法导论》Thomas H. Cormen等著 + 【4】《数学之美》吴军著

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

《数学之美》第九章——《图论和网络爬虫》，就浅显易懂的介绍了图的实际用途。搜索引擎里面的网络爬虫抓取网络数据，就是把互联网抽象成有向图这种数据结构，通过遍历这张图实现的互联网抓取。

``````type Graph struct {
edgnum int
vexnum int
}

type Vertex struct {
Data string
e    *Edge
}

type Edge struct {
ivex int
next *Edge
}
``````

``````func (this *Graph) InsertVertex(v Vertex) {
}
``````

``````func (this *Graph) InsertEdge(v1, v2 Vertex) {
if p == nil {
// fmt.Println("nil...", v1.Data, v2.Data)
} else {
for ; p.next != nil; p = p.next {
}
p.next = NewEdge(this.get_position(v2.Data))
// fmt.Println("append...", v1.Data, v2.Data)
}
}
``````

``````func (this *Graph) Adjacent(v Vertex) []Vertex {
res := make([]Vertex, 0)
for ; p != nil; p = p.next {
}
return res
}

func (this *Graph) OutDegree(v Vertex) int {
res := 0
for p != nil {
res++
p = p.next
}
return res
}
``````

``````func (this *Graph) InDegree(v Vertex) int {
res := 0
pos := this.get_position(v.Data)
for _, a := range this.adj {
p := a.e
for p != nil {
if pos == p.ivex {
res++
}
p = p.next
}
}
return res
}
``````

``````func (this *Graph) Bfs() {
res := map[int]Vertex{}
for _, a := range this.adj {
Q := []Vertex{a}
for len(Q) != 0 {
u := Q[0]
Q = Q[1:]
if _, ok := res[this.get_position(u.Data)]; !ok {
res[this.get_position(u.Data)] = u
fmt.Printf("%s ", u.Data)
}
}
}
fmt.Printf("\n")
}
``````

``````func (this *Graph) Dfs() {
res := map[int]Vertex{}
for _, a := range this.adj {
this.dfs(a, res)
}
fmt.Printf("\n")
}

func (this *Graph) dfs(u Vertex, res map[int]Vertex) {
if _, ok := res[this.get_position(u.Data)]; !ok {
res[this.get_position(u.Data)] = u
fmt.Printf("%s ", u.Data)
p := u.e
for p != nil {
if _, ok := res[p.ivex]; !ok {
}
p = p.next
}
}
}
``````

``````func TestMain(t *testing.T) {
g := create_example_lgraph()
g.Print()
println("Bfs.............")
g.Bfs()
println("Dfs.............")
g.Dfs()
if g.InDegree(Vertex{Data: "E"}) != 2 {
t.Error("indegree of E wanted 2 bug got", g.InDegree(Vertex{Data: "E"}))
}
if g.OutDegree(Vertex{Data: "E"}) != 2 {
t.Error("outdegree of E wanted 2 bug got", g.OutDegree(Vertex{Data: "E"}))
}
}

func create_example_lgraph() *Graph {
vexs := []string{"A", "B", "C", "D", "E", "F", "G"}
edges := [][2]string{
{"A", "B"},
{"B", "C"},
{"B", "E"},
{"B", "F"},
{"C", "E"},
{"D", "C"},
{"E", "B"},
{"E", "D"},
{"F", "G"}}
vlen := len(vexs)
elen := len(edges)

pG := Create()
// 初始化"顶点数"和"边数"
pG.vexnum = vlen
pG.edgnum = elen
// 初始化"邻接表"的顶点
for i := 0; i < pG.vexnum; i++ {
pG.InsertVertex(*NewVertex(vexs[i]))
}
// 初始化"邻接表"的边
for i := 0; i < pG.edgnum; i++ {
// 读取边的起始顶点和结束顶点
pG.InsertEdge(*NewVertex(edges[i][0]), *NewVertex(edges[i][1]))
}
return pG
}
``````

######参考文献 + 【1】wangkuiwu/datastructs_and_algorithm - GitHub + 【2】《数据结构与算法——C语言描述》，Mark Allen Weiss著 + 【3】《算法导论》Thomas H. Cormen等著 + 【4】《数学之美》吴军著