// 图的广度优先搜索和深度优先搜索
// https://blog.csdn.net/rxbook/article/details/131025774
package main

import (
	"container/list"
	"fmt"
)

// 使用邻接链表存储无向图
type Graph struct {
	data  []*list.List
	value int
}

// 根据设定的容量初始化一个图
func newGraph(v int) *Graph {
	graph := &Graph{
		data:  make([]*list.List, v),
		value: v,
	}
	for i := range graph.data {
		graph.data[i] = list.New()
	}
	return graph
}

// 给图添加边,每条边都添加进去
func (self *Graph) addEdge(start int, end int) {
	//无向图的一条边需要添加两次
	self.data[start].PushBack(end)
	self.data[end].PushBack(start)
}

// 广度优先搜索:start起始点,end结束点
// 搜索一条从start到end的最短路径
func (self *Graph) BFS(start int, end int) {
	if start == end {
		return
	}

	//visited记录已经被访问的顶点，避免顶点被重复访问。如果顶点 q 被访问，那相应的 visited[q] 设置为 true。
	visited := make([]bool, self.value)
	visited[start] = true

	//queue是一个队列，用来存储已经被访问、但相连的顶点还没有被访问的顶点。
	//因为广度优先搜索是逐层访问的，只有把第 k 层的顶点都访问完成之后，才能访问第 k+1 层的顶点。
	//当访问到第 k 层顶点的时候，需要把第 k 层的顶点记录下来，稍后才能通过第 k 层的顶点来找第 k+1 层的顶点。
	var queue []int
	queue = append(queue, start)

	//path用来记录搜索路径,从顶点start开始，广度优先搜索到顶点end后，path数组中存储的就是搜索的路径。
	//不过，这个路径是反向存储的, path[x] 存储的是顶点x是从哪个前驱顶点遍历过来的。
	//比如，通过顶点2的邻接表访问到顶点3，那 path[3] 就等于2。
	//为了正向打印出路径，需要递归地打印，可以看下 printPath() 函数的实现方式。
	path := make([]int, self.value)
	for index := range path {
		path[index] = -1
	}

	//标记是否已找到
	isFound := false
	for len(queue) > 0 && !isFound {
		top := queue[0]
		queue = queue[1:]
		linkedlist := self.data[top]
		for e := linkedlist.Front(); e != nil; e = e.Next() {
			k := e.Value.(int)
			if !visited[k] {
				path[k] = top
				if k == end {
					isFound = true
					break
				}
				queue = append(queue, k)
				visited[k] = true
			}
		}
	}
	if isFound {
		printPath(path, start, end)
	} else {
		fmt.Printf("从 %d 到 %d 的路径没有找到\n", start, end)
	}
}

// 广度优先搜索:start起始点,end结束点
func (self *Graph) DFS(start int, end int) {
	path := make([]int, self.value)
	for i := range path {
		path[i] = -1
	}
	visited := make([]bool, self.value)
	visited[start] = true

	isFound := false
	self.DFSRecurse(start, end, path, visited, isFound)
	printPath(path, start, end)
}

// 广度优先:递归搜索路径
func (self *Graph) DFSRecurse(start int, end int, path []int, visited []bool, isFound bool) {
	if isFound {
		return
	}
	visited[start] = true
	if start == end {
		isFound = true
		return
	}
	linkedlist := self.data[start]
	for e := linkedlist.Front(); e != nil; e = e.Next() {
		k := e.Value.(int)
		if !visited[k] {
			path[k] = start
			self.DFSRecurse(k, end, path, visited, false)
		}
	}
}

// 递归打印路径
func printPath(path []int, s int, t int) {
	if t == s || path[t] == -1 {
		fmt.Printf("%d ", t)
	} else {
		printPath(path, s, path[t])
		fmt.Printf("%d ", t)
	}
}

func main() {
	graph := newGraph(8)
	//把图的所有边都添加进去
	graph.addEdge(0, 1)
	graph.addEdge(1, 2)
	graph.addEdge(0, 3)
	graph.addEdge(1, 4)
	graph.addEdge(3, 4)
	graph.addEdge(4, 5)
	graph.addEdge(2, 5)
	graph.addEdge(5, 7)
	graph.addEdge(4, 6)
	graph.addEdge(6, 7)

	//广度优先搜索从0到6的路径
	graph.BFS(0, 6) //0 1 4 6
	fmt.Println()
	//广度优先搜索从3到7的路径
	graph.BFS(3, 7) //3 4 5 7
	fmt.Println()

	//深度优先搜索从0到6的路径
	graph.DFS(0, 6) //0 1 2 5 4 6
	fmt.Println()
	//深度优先搜索从3到7的路径
	graph.DFS(3, 7) //3 0 1 2 5 4 6 7
	fmt.Println()
}