有向无环图 邻接表实现

package main

import (
	"fmt"
	"github.com/eapache/queue"
)

// 邻接表
type Vertex struct {
	Key      string
	Parents  []*Vertex
	Children []*Vertex
	Value    interface{}
}

type DAG struct {
	Vertexes []*Vertex
}

func (dag *DAG) AddVertex(v *Vertex) {
	dag.Vertexes = append(dag.Vertexes, v)
}

func (dag *DAG) AddEdge(from, to *Vertex) {
	from.Children = append(from.Children, to)

	to.Parents = append(from.Parents, from)
}

func (dag *DAG) BFS(root *Vertex) {
	q := queue.New()

	visitMap := make(map[string]bool)
	visitMap[root.Key] = true

	q.Add(root)

	for {
		if q.Length() == 0 {
			fmt.Println("done")
			break
		}
		current := q.Remove().(*Vertex)

		fmt.Println("bfs key", current.Key)

		for _, v := range current.Children {
			fmt.Printf("from:%v to:%s\n", current.Key, v.Key)
			if v.Key == root.Key {
				panic("back root")
			}
			if _, ok := visitMap[v.Key]; !ok {
				visitMap[v.Key] = true
				//fmt.Println("add visit", v.Key)

				q.Add(v)
			}
		}
	}

}

func (dag *DAG) DFS(root *Vertex) {
	stack := []*Vertex{root}

	visitMap := make(map[string]bool)
	visitMap[root.Key] = true

	for i := 0; i < 10; i++ {
		if len(stack) == 0 {
			fmt.Println("done")
			break
		}
		if len(stack)-1 < 0 {
			panic("unexpected")
		}
		current := stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		fmt.Println("dfs key", current.Key)

		for _, v := range current.Children {
			fmt.Println("from:%v to:%s", current.Key, v.Key)
			if v.Key == root.Key {
				panic("back root")
			}
			if _, ok := visitMap[v.Key]; !ok {
				visitMap[v.Key] = true
				//fmt.Println("add visit", v.Key)
				if v.Key == root.Key {
					panic("back root")
				}
				stack = append(stack, v)
			}
		}
	}

}

func main() {

	dag := &DAG{}
	v1 := &Vertex{Key: "1"}
	v2 := &Vertex{Key: "2"}
	v3 := &Vertex{Key: "3"}
	v4 := &Vertex{Key: "4"}
	v5 := &Vertex{Key: "5"}

	// dag
	//     5
	//   >
	//  /
	// 1----->2
	//  \   >   \
	//   > /     >
	//   3-------->4

	dag.AddEdge(v1, v5)
	dag.AddEdge(v1, v2)
	//dag.AddEdge(v2, v1)
	dag.AddEdge(v1, v3)
	dag.AddEdge(v3, v4)
	dag.AddEdge(v3, v2)
	dag.AddEdge(v2, v4)
	dag.BFS(v1)
	//dag.DFS(v1)

	
}

这里要说明一下，对于邻接表的数据结构，千万不要用json来序列化，因为邻接表的实现是有pointer loop问题的，而json包不会检查pointer loop

判断是否有环

一般来说，如果root顶点随着遍历如果会回到自身，那么这个图就是有环的，上面的例子
稍微改动一下

package main

import (
	"fmt"
	"github.com/eapache/queue"
)

// 邻接表
type Vertex struct {
	Key      string
	Parents  []*Vertex
	Children []*Vertex
	Value    interface{}
}

type DAG struct {
	Vertexes []*Vertex
}

func (dag *DAG) AddVertex(v *Vertex) {
	dag.Vertexes = append(dag.Vertexes, v)
}

func (dag *DAG) AddEdge(from, to *Vertex) {
	from.Children = append(from.Children, to)

	to.Parents = append(from.Parents, from)
}

func (dag *DAG) BFS(root *Vertex) {
	q := queue.New()

	visitMap := make(map[string]bool)
	visitMap[root.Key] = true

	q.Add(root)

	for {
		if q.Length() == 0 {
			fmt.Println("done")
			break
		}
		current := q.Remove().(*Vertex)

		fmt.Println("bfs key", current.Key)

		for _, v := range current.Children {
			fmt.Printf("from:%v to:%s\n", current.Key, v.Key)
			if v.Key == root.Key {
				panic("back root")
			}
			if _, ok := visitMap[v.Key]; !ok {
				visitMap[v.Key] = true
				//fmt.Println("add visit", v.Key)

				q.Add(v)
			}
		}
	}

}

func (dag *DAG) DFS(root *Vertex) {
	stack := []*Vertex{root}

	visitMap := make(map[string]bool)
	visitMap[root.Key] = true

	for i := 0; i < 10; i++ {
		if len(stack) == 0 {
			fmt.Println("done")
			break
		}
		if len(stack)-1 < 0 {
			panic("unexpected")
		}
		current := stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		fmt.Println("dfs key", current.Key)

		for _, v := range current.Children {
			fmt.Println("from:%v to:%s", current.Key, v.Key)
			if v.Key == root.Key {
				panic("back root")
			}
			if _, ok := visitMap[v.Key]; !ok {
				visitMap[v.Key] = true
				//fmt.Println("add visit", v.Key)
				if v.Key == root.Key {
					panic("back root")
				}
				stack = append(stack, v)
			}
		}
	}

}

func main() {

	dag := &DAG{}
	v1 := &Vertex{Key: "1"}
	v2 := &Vertex{Key: "2"}
	v3 := &Vertex{Key: "3"}
	v4 := &Vertex{Key: "4"}
	v5 := &Vertex{Key: "5"}


	// 对于有环图，从root点出发，最终会回到root
	// non dag
	//    5
	//   >
	//  /
	// 1 <----2
	//  \   .>  \
	//   > /     >
	//    3----  >4
	dag.AddEdge(v1, v5)
	dag.AddEdge(v2, v1)
	dag.AddEdge(v1, v3)
	dag.AddEdge(v3, v4)
	dag.AddEdge(v3, v2)
	dag.AddEdge(v2, v4)
	dag.AddEdge(v2, v1)
	dag.BFS(v1)
	//dag.DFS(v1)
}

跟上面例子不一样，顶点2指向顶点1，也就是会有一个1->3->2>1的环
输出

bfs key 1
from:1 to:5
from:1 to:3
bfs key 5
bfs key 3
from:3 to:4
from:3 to:2
bfs key 4
bfs key 2
from:2 to:1
panic: back root

goroutine 1 [running]:
main.(*DAG).BFS(0xc00007cf38, 0xc0000ac000)
	/opt/go_work/src/mtest/dag/main.go:50 +0x4e3
main.main()
	/opt/go_work/src/mtest/dag/main.go:144 +0x53d
exit status 2