-
-
测试
package mm
import "testing"
func TestAdjacencyLists_Adjacent(t *testing.T) {
l := NewAdjacencyLists(10)
l.InsertEdge(&Vertex{index: 0},&Vertex{index: 1})
l.InsertEdge(&Vertex{index: 0},&Vertex{index: 2})
l.InsertEdge(&Vertex{index: 1},&Vertex{index: 3})
l.InsertEdge(&Vertex{index: 1},&Vertex{index: 4})
l.InsertEdge(&Vertex{index: 2},&Vertex{index: 5})
l.InsertEdge(&Vertex{index: 2},&Vertex{index: 6})
l.InsertEdge(&Vertex{index: 3},&Vertex{index: 7})
l.InsertEdge(&Vertex{index: 4},&Vertex{index: 7})
l.InsertEdge(&Vertex{index: 5},&Vertex{index: 7})
l.InsertEdge(&Vertex{index: 6},&Vertex{index: 7})
l.InsertEdge(&Vertex{index: 6},&Vertex{index: 7})
l.InsertEdge(&Vertex{index: 0},&Vertex{index: 8})
l.InsertEdge(&Vertex{index: 0},&Vertex{index: 9})
l.Print()
t.Log(l.dfs())
t.Log(l.dfsRecursion())
t.Log(l.bfs())
}
- 深度优先算法递归实现
- 从顶点v开始，依次对顶点v的邻接链表顶点做深度优先搜索
- [0 1 3 7 4 5 2 6 8 9]
func dfsRecursion(l *AdjacencyLists) []int {
var fRecv func(v *Vertex)
visited := make([]bool, len(l.vertexes))
var res []int
fRecv = func(v *Vertex) {
if !visited[v.index] {
res = append(res, v.index)
visited[v.index] = true
}
for v.next != nil {
if !visited[v.next.index] {
fRecv(l.vertexes[v.next.index])
}
v = v.next
}
}
fRecv(l.vertexes[0])
return res
}
- 深度优先算法非递归实现
- 1.随便把一个顶点推入栈中
- 2.从栈中弹出一个顶点或链表v，如果未访问，加入访问数组
- 3.从顶点v当前的邻接表（头结点不一定是v）依次选取一个未访问的顶点w1、w2，
对w1进行深度优先搜索，如果w2存在，先把w2入栈，再把以w1为头结点的顶点入栈。 - 4.当最终搜索到一个顶点u，且u的邻接表中的顶点全部被访问过，就从栈中取出一个链表继续上述步骤2，直到栈为空，搜索结束
- [0 1 3 7 4 5 2 6 8 9]
func dfs(l *AdjacencyLists) []int {
var result []int
var fStack func(index int)
s := stack()
fStack = func(index int) {
visited := make([]bool, len(l.vertexes))
s.stackPush(l.vertexes[index])
for !s.stackEmpty() {
temp, _ := s.stackPop()
if !visited[temp.index] {
result = append(result, temp.index)
visited[temp.index] = true
}
temp1 := temp.next
for temp1 != nil {
if !visited[temp1.index] {
if temp1.next != nil {
s.stackPush(temp1.next) // 链表先入栈
}
s.stackPush(l.vertexes[temp1.index]) // 头结点入栈
break
}
temp1 = temp1.next
}
}
}
fStack(0)
return result
}
- 广度优先算法
- 顶点v入队列
- 2.从队列弹出一个顶点w。依次访问w的所有节点wt，如果wt未访问，将其加入访问数组result，将其头结点链加入队列
- 3.重复2
- [0 1 2 8 9 3 4 5 6 7]
func bfs(l *AdjacencyLists) []int {
var result []int
var fQueue func(index int)
q := queue()
fQueue = func(index int) {
visited := make([]bool, len(l.vertexes))
q.addq(l.vertexes[index])
for !q.emptyq() {
temp, _ := q.deleteq()
for temp != nil {
if !visited[temp.index] {
result = append(result, temp.index)
visited[temp.index] = true
q.addq(l.vertexes[temp.index])
}
temp = temp.next
}
}
}
fQueue(0)
return result
}
- 栈
type stackArr struct {
stackArr []*Vertex
}
func stack() *stackArr {
return &stackArr{}
}
func (l *stackArr) stackEmpty() bool {
return len(l.stackArr) == 0
}
func (l *stackArr) stackClear() {
l.stackArr = nil
}
func (l *stackArr) stackPush(v *Vertex) {
l.stackArr = append(l.stackArr, v)
}
func (l *stackArr) stackPop() (v *Vertex, ok bool) {
if l.stackEmpty() {
return
}
v = l.stackArr[len(l.stackArr)-1]
l.stackArr = l.stackArr[:len(l.stackArr)-1]
return v, true
}
- 队列
type queueArr struct {
queueArr []*Vertex
}
func queue() *queueArr {
return &queueArr{}
}
func (l *queueArr) deleteq() (v *Vertex, ok bool) {
if l.emptyq() {
return
}
v = l.queueArr[0]
l.queueArr = l.queueArr[1:]
return v, true
}
func (l *queueArr) addq(v *Vertex) {
l.queueArr = append(l.queueArr, v)
}
func (l *queueArr) emptyq() bool {
return len(l.queueArr) == 0
}
func (l *queueArr) clearq() {
l.queueArr = nil
}
- 图的基本操作
package mm
import "fmt"
type Vertex struct {
index int
next *Vertex
}
type AdjacencyLists struct {
vertexes []*Vertex
}
func NewAdjacencyLists(size int) *AdjacencyLists {
return &AdjacencyLists{
vertexes: make([]*Vertex, size),
}
}
// InsertVertex 向图中插入没有关联边的新顶点v
func (l *AdjacencyLists) InsertVertex(v *Vertex) {
l.vertexes[v.index] = v
}
// DeleteVertex 删除图中的顶点v及其关联的所有边
func (l *AdjacencyLists) DeleteVertex(v *Vertex) {
list := l.vertexes[v.index]
for list.next != nil {
temp := l.vertexes[list.next.index]
for temp.next != nil {
if temp.next.index == v.index {
temp.next = temp.next.next
} else {
temp = temp.next
}
}
list = list.next
}
l.vertexes[v.index] = nil
}
// DeleteEdge 删除图中边(v1,v2),顶点v1，v2不删除
func (l *AdjacencyLists) DeleteEdge(v1, v2 *Vertex) {
temp1 := l.vertexes[v1.index]
for temp1.next != nil {
if temp1.next.index == v2.index {
temp1.next = temp1.next.next
} else {
temp1 = temp1.next
}
}
temp2 := l.vertexes[v2.index]
for temp2.next != nil {
if temp2.next.index == v1.index {
temp2.next = temp2.next.next
} else {
temp2 = temp2.next
}
}
}
func (l *AdjacencyLists) IsEmpty() bool {
result := true
for _, v := range l.vertexes {
if v != nil {
result = false
break
}
}
return result
}
// Adjacent 顶点v的所有邻接节点
func (l *AdjacencyLists) Adjacent(v *Vertex) []*Vertex {
return l.vertexes
}
func (l *AdjacencyLists) Print() {
fmt.Println("--------------------------------")
for k, v := range l.vertexes {
fmt.Printf("%d: ", k)
for v != nil {
if v.next != nil {
fmt.Printf("%d=>", v.index)
} else {
fmt.Printf("%d", v.index)
}
v = v.next
}
fmt.Println()
}
fmt.Println("--------------------------------")
}
// InsertEdge 向图的顶点v1和v2之间插入一条边
func (l *AdjacencyLists) InsertEdge(v1, v2 *Vertex) {
temp1 := l.vertexes[v1.index]
if temp1 == nil {
l.vertexes[v1.index] = &Vertex{index: v1.index}
temp1 = l.vertexes[v1.index]
}
for temp1.next != nil {
if temp1.next.index == v2.index { // 不添加重复节点
return
}
temp1 = temp1.next
}
temp1.next = v2
temp2 := l.vertexes[v2.index]
if temp2 == nil {
l.vertexes[v2.index] = &Vertex{index: v2.index}
temp2 = l.vertexes[v2.index]
}
for temp2.next != nil {
if temp2.next.index == v1.index { // 不添加重复节点
return
}
temp2 = temp2.next
}
temp2.next = v1
}