无向图–go语言实现（持续更新）
在许多计算机应用中，由相连的结点所表示的模型起到了关键的作用。这些结点之间的连接很 自然地会让人们产生一连串的疑问:沿着这些连接能否从一个结点到达另一个结点?有多少个结点 和指定的结点相连?两个结点之间最短的连接是哪一条?
要描述这些问题，我们要使用一种抽象的数学对象，叫做图
摘自《算法》
图的数据结构和基本操作
package graph
import (
"container/list"
)
// 图的数据结构
type Graph struct {
v int // 顶点数
e int // 边数
adj []*list.List // 邻边链表切片
}
// 创建一个图
func New(v int, e [][2]int) *Graph {
graph := new(Graph)
graph.v = v
graph.e = len(e)
var adj []*list.List
for i := 0; i < v; i++ {
adj = append(adj, list.New())
}
graph.adj = adj
for _, val := range e {
graph.AddEdge(val[0], val[1])
}
return graph
}
// 获取图的定点数量
func (g *Graph) V() int {
return g.v
}
// 获取图中边的数量
func (g *Graph) E() int {
return g.e
}
// 向图中添加一条边
func (g *Graph) AddEdge(v int, w int) {
g.adj[v].PushFront(w)
g.adj[w].PushFront(v)
}
// 获取与顶点相通的其他顶点 返回一个链表
func (g *Graph) Adj(v int) *list.List {
return g.adj[v]
}
`</pre>
#### 深度优先搜索
<pre class="line-numbers prism-highlight" data-start="1">`package graph
/**
深度优先搜索算法
*/
type depth struct {
marked []bool
count int
}
func NewDepth(g *Graph, s int) *depth {
depth := &depth{
marked: make([]bool, g.v),
count: 0,
}
depth.dfs(g, s)
return depth
}
// 利用递归实现图深度优先搜索
func (d *depth) dfs(g *Graph, v int) {
d.marked[v] = true
d.count++
for e := g.Adj(v).Front(); e != nil; e = e.Next() {
w, _ := e.Value.(int)
if !d.marked[w] {
d.dfs(g, w)
}
}
}
// 判断传入的顶点是否与初始顶点相通
func (d *depth) Marked(w int) bool {
return d.marked[w]
}
// 和初始顶点相通的顶点数量
func (d *depth) Count() int {
return d.count
}
`</pre>
#### 深度优先搜索路径
<pre class="line-numbers prism-highlight" data-start="1">`package graph
type Paths struct {
marked []bool
edgeTo []int
final int
}
func NewPaths(graph *Graph, s int) *Paths {
paths := &Paths{
marked: make([]bool, graph.V()),
edgeTo: make([]int, graph.V()),
final: s,
}
paths.dfs(graph, s)
return paths
}
func (p *Paths) dfs(graph *Graph, v int) {
p.marked[v] = true
for e := graph.Adj(v).Front(); e != nil; e = e.Next() {
w, _ := e.Value.(int)
if !p.marked[w] {
p.edgeTo[w] = v
p.dfs(graph, w)
}
}
}
func (p *Paths) HasPathTo(v int) bool {
return p.marked[v]
}
func (p *Paths) PathTo(v int) []int {
if !p.HasPathTo(v) {
return nil
}
path := make([]int, 0)
var x int
for x = v; x != p.final; x = p.edgeTo[x] {
path = append(path, x)
}
path = append(path, x)
return path
}
`</pre>
#### 广度优先搜索最短路径
<pre class="line-numbers prism-highlight" data-start="1">`package graph
import "container/list"
/**
*广度优先搜索
*/
type Breadth struct {
marked []bool
edgeTo []int
final int
}
func NewBreadth(graph *Graph, s int) *Breadth {
breadth := &Breadth{
marked: make([]bool, graph.v),
edgeTo: make([]int, graph.v),
final: s,
}
breadth.bfs(graph, s)
return breadth
}
func (b *Breadth) bfs(graph *Graph, s int) {
queue := list.New()
b.marked[s] = true
queue.PushBack(s)
for queue.Len() != 0 {
element := queue.Front()
v, _ := queue.Remove(element).(int)
for e := graph.Adj(v).Front(); e != nil; e = e.Next() {
val, _ := e.Value.(int)
if b.marked[val] == false {
b.marked[val] = true
b.edgeTo[val] = v
queue.PushBack(e.Value)
}
}
}
}
func (b *Breadth) HasPathTo(v int) bool {
return b.marked[v]
}
func (b *Breadth) Path(v int) []int {
if !b.HasPathTo(v) {
return nil
}
path := make([]int, 0)
for p := v; p != b.final;p = b.edgeTo[p] {
path = append(path,p)
}
path = append(path,b.final)
return path
}
`</pre>
#### 最后测试
<pre class="line-numbers prism-highlight" data-start="1">`package main
import (
"graph"
"fmt"
)
func main() {
data := [][2]int{
{0, 1},
{1, 3},
{0, 3},
}
g := graph.New(4, data)
//depth := graph.NewDepth(g, 1)
//fmt.Println(depth.Marked(3))
//paths := graph.NewPaths(g, 0)
//fmt.Println(paths.PathTo(3))
paths := graph.NewBreadth(g, 0)
fmt.Println(paths.Path(3))
}