package main

import (
	"fmt"
)

func main() {

	g := graph{}
	n1, n2, n3, n4, n5 := node{1}, node{2}, node{3}, node{4}, node{5}

	g.addNode(&n1)
	g.addNode(&n2)
	g.addNode(&n3)
	g.addNode(&n4)
	g.addNode(&n5)

	g.addEdge(&n1, &n2)
	g.addEdge(&n1, &n5)
	g.addEdge(&n2, &n3)
	g.addEdge(&n2, &n4)
	g.addEdge(&n2, &n5)
	g.addEdge(&n3, &n4)
	g.addEdge(&n4, &n5)

	g.string()
	g.BFS()
	g.DFS()
}

type node struct {
	val int
}

type graph struct {
	nodes []*node
	//使用邻接表来存储关系
	edges map[node][]*node
}

func (g *graph) addNode(n *node) {
	g.nodes = append(g.nodes, n)
}

func (g *graph) addEdge(u, v *node) {
	if g.edges == nil {
		g.edges = map[node][]*node{}
	}
	g.edges[*u] = append(g.edges[*u], v)
	g.edges[*v] = append(g.edges[*v], u)
}

func (g *graph) string() {
	str := ""
	for _, v := range g.nodes {
		str += v.string() + "->"
		for _, val := range g.edges[*v] {
			str += val.string() + " "
		}
		str += "\n"
	}
	fmt.Println(str)
}

func (n *node) string() string {
	return fmt.Sprintf("%s", n.val)
}

//bfs遍历
func (g *graph) BFS() {
	//将第一个节点加入到队列中
	head := g.nodes[0]
	queue := []*node{head}
	visitedMap := map[*node]bool{}
	visitedMap[head] = true
	for len(queue) > 0 {
		//模拟出队列
		item := queue[len(queue)-1]
		queue = queue[:len(queue)-1]
		for _, v := range g.edges[*item] {
			if boolean, exist := visitedMap[v]; exist && boolean {
				continue
			}
			queue = append([]*node{v}, queue...)
			visitedMap[v] = true
		}
		//这个地方可以进行一些操作，例如拷贝等
		fmt.Println(item.val)
	}
}

//dfs遍历
func (g *graph) DFS() {
	//将第一个节点加入到栈中
	head := g.nodes[0]
	stack := []*node{head}
	visitMap := map[*node]bool{}
	visitMap[head] = true
	for len(stack) > 0 {
		item := stack[0]
		stack = stack[1:]
		for _, v := range g.edges[*item] {
			if boolean, exist := visitMap[v]; exist && boolean {
				continue
			}
			stack = append([]*node{v}, stack...)
			visitMap[v] = true
		}
		fmt.Println(item.val)
	}
}

type Node struct {
	val   int
	edges []*Node
}

//深度拷贝无向图
//dfs深度遍历, 同时维护一个新旧node的map表来拷贝edges
func cloneGraph(head *Node) *Node {
	nodeMap := map[*Node]*Node{}
	visitMap := map[*Node]bool{}
	nodeMap[head] = true
	nodeMap[head] = &Node{
		head.val,
		[]*Node{},
	}
	stack := []int{}
	for len(stack) > 0 {
		item := stack[0]
		stack = stack[1:]
		for _, v := range item.edeges {
			if boolean, exist := visitMap[v]; boolean && exist {
				continue
			}
			//入栈并且复制节点
			stack = append([]*Node{v}, stack...)
			nodeMap[v] = &Node{
				v.val,
				[]*Node{},
			}
			item.edges = append(item.edges, nodeMap[v])
			visitMap[v] = true
		}
	}
	return nodeMap[head]
}

//判断是否有环
dfs遍历时，如果存在两次访问一个点时，则有环